算法找到一个极性面的交点 [英] Algorithm to find intersections in a polar plane

问题描述

我有极性面相对于基准点（下图中的颜色为绿色）一个。该分段再这样presented：

I have a polar plane relative to a base point (colored green in the diagram below). The points and segments are represented thus:

class Node {
    int theta;
    double radius;
}

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

我想弄清楚，如果红线从基点到各段的节点会相交的任何其他段。在这个例子中，红色线不相交。

I want to figure out if the red line going from the base point to each segment node intersects any other segment. In this example, the red line does intersect.

我应该申请什么算法的方法呢？计算复杂性比实施简单不太重要。

What algorithmic approach should I apply? Computational complexity is less important than simplicity of implementation.

推荐答案

如果你正在追求简约而不表现，你可以做到以下几点：

If you are striving for simplicity rather than performance, you could do the following:

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)

交叉的产品，你可以计算它很容易直接在极坐标适应笛卡尔式或

The cross-product you can compute it easily adapting the cartesian equations or directly on polar coordinates.

此外，我相信你能，其中N为段数，由极角分拣点，并利用扫描线算法遍历段适应此过程运行在O（N LG N）（和分）列表。

Moreover, I believe you can adapt this procedure to run in O(N lg N), with N being the number of segments, by sorting the points by polar angle and using a sweep line algorithm to traverse the segment (and points) list.

这篇关于算法找到一个极性面的交点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！