首页 文章

在极地平面中寻找交叉点的算法

提问于
浏览 次
2

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

class Node {
    int theta;
    double radius;
}

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

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

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

enter image description here

algorithm graph geometry computational-geometry graph-algorithm

2 回答

  • 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)

    您可以计算出的交叉乘积很容易适应笛卡尔方程或直接在极坐标上 .

    enter image description here

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

    回复于
  • 1

    如果每个黑色线段的 endpoints 不同，则为uniquely define a line . 同样，非简并红线段的 endpoints 定义了唯一的线 . 对于每条可能的红线，计算每条黑线的交点 .

    如果线相交的点落在红色段和黑色段上，则段相交 . 否则他们没有 .

    最简单的方法是在笛卡尔平面上执行所有这些计算，因此首先将极坐标转换为笛卡尔坐标 .

    给定每个线段的 endpoints ，在two-point form中创建一个线性方程 .

    要找到两条线的交点，求解两个线性方程组的系统 .

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

    回复于

相关问题