视线算法

Question

对于地形上点的数组

X[i,j]

和有关太阳位置的 n 个信息，确定每个点是否处于阳光照射或阴影中。视线问题。

输入：

Y[i, j]

是一个 n x n 浮点数数组（以米为单位）。太阳角度 θ ≤ 90°。太阳方位角，Φ。相邻点之间的水平距离（以米为单位），

d

（分辨率或比例）。

输出：

S[i, j]

n x n 布尔值数组。如果

[i,j]

在阴影中，则

S[i,j]

为 1 n，否则为 0。

要写的算法：

使用谓词逻辑和一些简单的推理。请记住，我们只查看第 i 行。

j

处的点处于阴影中，如果其西边的某个点在其上投下阴影，即 S[j]= some(k) 0≤k

第一个算法将其实现为循环（每行的二次时间）。我需要有关第一个算法的帮助。

def naive(array,d,angle,len,returnArray):

    for i in range(len):
        for j in range(len):

            if compare(array[i][j],array[i][j-1]) == True:
                if compare(math.tan(angle),((array[i][j-1] - array[i][j])/(d))) == True:
                    returnArray[i][j] = True

    return returnArray

对于 5x5 阵列：

4,3,5,3,4,
4,1,1,2,1,
2,3,3,4,2,
1,4,3,1,3,
1,2,1,5,2,

预期如下：

0    0    0    *    0

0    *    *    0    0

0    0    0    0    *

0    0    0    *    0

0    0    0    0    *

有 50 次比较。但我的返回数组 [1][2] 为 0。

Answer 1

您的代码永远不会寻找超出一个单元格之外的阴影。要使用问题描述中的变量，您只需测试

k=j-1

，而不是其余的

k

值降至零。

如果您想坚持使用简单的算法，请尝试这样的事情：

def naive(array, d, angle, n, returnArray): # len is the name of a builtin, don't reuse it
    for i in range(n):
        for j in range(n):
            for k in range(j):  # add an extra loop from 0 to j-1
                if compare(math.tan(angle), (array[i][k]-array[i][j]) / (d*(j-k))):
                    returnArray[i][j] = True
    return returnArray

请注意，我删除了您在

== True

语句中所做的

if

测试。您已经获得了布尔值，因此不需要比较运算符。

更有效的算法可以通过在您穿过行时跟踪最高阴影的高度来跳过

k

循环。当你移动时，阴影高度会变小，因为它是一个角度。如果当前值高于其所在位置的阴影高度，则您知道当前单元格位于阳光下，并且您有一个新的最高阴影。这种方法只需要您计算正切并将其乘以

d

一次，即可获得在迭代时从阴影高度中减去的偏移量。