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

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

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

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 是线段的数量，通过按极角对点进行排序并使用扫掠线算法遍历线段(和点) 列表。