在极平面中查找交点的算法

Question

我有一个相对于基点的极平面（下图中的绿色）。点和线段表示如下：

class Node {
    int theta;
    double radius;
}

class Segment {
    //each segment must have node that is northern relative to other
    Node northern;
    Node southern;
}

我想弄清楚从基点到每个线段节点的红线是否与任何其他线段相交。在此示例中，红线确实相交。

我应该应用什么算法方法？计算复杂性不如实现简单重要。

Answer 1

如果每条黑色线段的端点不同，则它们uniquely define a line。同样，非退化的红色线段的端点定义了一条唯一的线。对于每条可能的红线，计算与每条黑线的交点。

如果直线相交的点既落在红色线段上又落在黑色线段上，则线段相交。否则他们不会。

在笛卡尔平面中执行所有这些计算最简单，因此首先将极坐标转换为笛卡尔坐标。

给定每条线段的端点，在two-point form中建立一个线性方程。

要找到两条直线的交点，求解两个线性方程组。

要确定线上的点是否落在该线上的线段内，请获取该点的 x 坐标并检查它是否落在线段端点的 x 坐标之间。

Answer 2

如果您追求简单而不是性能，您可以执行以下操作：

For each Segment S (consisting of points P1 and P2)
  For each Point P not belonging to S, if P.theta between P1.theta and P2.theta
    If (cross-product(P1,P,P2) is convex) Then Return(Intersect)
Return (NoIntersect)

您可以轻松地通过笛卡尔方程或直接在极坐标上计算叉积。

此外，我相信您可以将此过程调整为 O(N lg N) 中的 运行，其中 N 是段数，通过按极角对点进行排序并使用扫描线算法来遍历线段（和点）列表。