使用点光源查找二维曲线中的阴影顶点

Question

我有一组顶点，它们在 x 和 y 方向上形成一条曲线。曲线平滑、不凸、不相交、不存在垂直或超出垂直的部分。 x 值是唯一的整数。下图展示了一条示例性曲线。您还可以看到曲线上方的点光源。该光始终远高于曲线。

现在我想计算哪些顶点被网格遮挡。如果可能的话，我想避免投射光线并计算它们可能与网格相交的位置。由于网格是一条简单的线，我猜有一种更简单的方法来找到阴影顶点。

我尝试用

angle = arctan((y_point - y[i]), (x_point - x[i]))

计算 y 轴和从光线到每个顶点的光线之间的角度。这表示光源左侧的光线与每个顶点之间的角度。我在下图中绘制了光线。正如你所看到的，

x==[3,5,21,22,23]

处的点应该是阴影的，这就是为什么我手动将它们着色为绿色。 现在，如果曲线是平坦的，对于增加 x 的每个点，上面计算的角度也应该增加。然而，如果它与前一个点相比有所下降，则该点或前一个点处于阴影中。结果如下所示： 正如您所看到的，它正确检测到

x==[21,22]

处的顶点，但它错过了

x==23

，并且仅检测左侧阴影顶点的邻居。

对于

x==23

我想我可以计算每个点的

cummax(angle)

并将该点的角度与该 cummax 角度进行比较。

If angle < cummax(angle)

那么该点就会被遮挡。现在，这也捕获了

x==23

处的顶点，但在左侧仍然失败。

如何修复左侧？

我正在使用 python，但这应该适用于任何语言。如果可能的话，我想避免投射光线并计算光线可能与曲线相交的每个边缘。如果你想复制曲线，坐标是

"x": [ 1, 2,  3, 4, 5,6,7,8,13,18,19,20,21,22,23,24,]
"y": [-2,-3,-10,-1,-2,2,3,4, 7, 5, 5, 5, 3, 1, 1, 1,]
"point": (11, 16)

Answer 1

如果一个点和光源之间的曲线上的任何其他点位于从光源到该点的光线上方，则该点“在阴影中”。因此你可以找到阴影点：

import matplotlib.pyplot as plt

x = [ 1, 2,  3, 4, 5,6,7,8,13,18,19,20,21,22,23,24,]
y = [-2,-3,-10,-1,-2,2,3,4, 7, 5, 5, 5, 3, 1, 1, 1,]
point = (11, 16)

xp, yp = point
n = len(x)
for ip in range(n):
    if x[ip] >= xp:
        break

def in_shadow(i):
    xi = x[i]
    yi = y[i]
    r = range(i+1, ip) if i < ip else range(ip+1, i)
    for j in r:
        if y[j] > yi + (x[j]-xi)/(xp-xi)*(yp-yi):
            return True
    return False

plt.figure(1).clf()
plt.plot(x, y, 'o-b')
plt.plot(*point, 'o')
for i in range(n):
    c = 'r' if in_shadow(i) else 'g'
    plt.plot([x[i],xp], [y[i],yp], c)