在python中，如何测试一条线是否与任意数量的其他未知行相交？

Question

我想测试一个点是否在多边形内，为此我使用ray-casting algorithm，在这里我将一条线从该点发送到屏幕的原点，并测试它有多少个交点（如果它有奇数个交点，则该点在多边形内，否则它在外）。问题在于计算光线是否相交。只有知道屏幕上每一条线段的起点和终点坐标，并计算出与这些直线的交点，这是计算交点的唯一方法吗？或者有其他方法（不管它的复杂性如何）吗？在

如果这是求线交点的唯一方法，那么计算交点的最快方法是什么？在

有时屏幕上可能有500行左右，所有这些行都需要检查是否有碰撞。一个算法要实时测试与所有这些线路的碰撞会对系统造成多大的负担？在

Answer 1

then what would be the fastest way of calculating intersections?

您需要从this answer here开始。它描述了一种使用向量叉积测试二维情况下线段相交的通用快速方法。在

要使用上面的方法，你需要用点加向量的形式来表示直线。对于光线，你需要从感兴趣的点开始p，向量将指向原点，即-p（负p）。在

ray: p - sp (s >= 0)

如果线段的端点是a和b，则取点a并将从a到b的方向作为向量（这是b—a，我们称之为w）。在

w = b - a
line segment: a + tw (0 <= t <= 1)

现在使用上述方法：

p - sp = a + tw
(p - sp) × -p = (a + tw) × -p - cross both sides by -p
0 = - a × p - tw × p - since a vector crossed with itself is zero (p × p = 0)

t = p × a / w × p - solving for t (remember a × b = -(b × a))

我们可以在这里进行前两个测试：

1. 如果w×p=0，则光线和直线平行（或共线），因此它们永远不会相交（如果共线，则在所有点相交），因此我们可以提前退出测试（场景3）。在
2. 如果t<；0或t>；1，交点位于a和b之间的线段之外（场景2）。在

继续使用叉积法求解s

s = (a - p) × w / w × p

现在，我们的最后一个检查：如果s<；0，相交发生在点之后p（远离原点，场景4），因此不会增加光线投射计数。在

---

在python中快速计算这个问题仍然是一个挑战，我要说的是，最好的方法是尝试将这500个检查向量化为更大的矩阵操作，并使用numpy实现它。在

Answer 2

您可能需要使用Shapely包。manual记录了一个名为的方法contains（）（向下滚动到“二进制谓词”部分），它似乎适合您的需要。在

关于性能注意事项，请参阅手册章节：“性能”和“准备好的几何图形”。在