Algorithm to find intersections in a polar plane

问题:

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.

回答1:

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.

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.

回答2:

If the endpoints of each black line segment are distinct, they uniquely define a line. Likewise, the endpoints of a non-degenerate red line segment define a unique line. For every possible red line, calculate the intersection with every black line.

If the point where the lines intersect falls both on the red segment and on the black segment, the segments intersect. Otherwise they do not.

It's easiest to perform all of these calculations in the Cartesian plane, so begin by converting the polar coordinates into Cartesian coordinates.

Given the endpoints of each line segment, make a linear equation in two-point form.

To find the intersection of two lines, solve the system of two linear equations.

To determine whether a point on a line falls within a segment on that line, take the x coordinate of the point and check whether it falls between the x coordinates of the segment's endpoints.