Check if Polygon is Self-Intersecting?

Question

I have a System.Windows.Shapes.Polygon object, whose layout is determined completely by a series of Points. I need to determine if this Polygon is self intersecting; i.e., if any of the sides of the polygon intersect any of the other sides at a point which is not a vertex. Is there an easy/fast way to compute this?

Answer 1

This is an interesting problem, which I address below in pseudocode form. Unfortunately, there is a character limit for these answers, so I am not able to also include actual C# code. Perhaps it will be possible to attach a code sample as a comment.

We can make a couple of preliminary observations:

1. Only polygons with four or more sides can have sides that cross each other.
2. No two neighboring sides on the path defining the polygon can cross.

Consider the general case for an n-sided polygon. At a high level, a workable algorithm could go something like this:

1. Establish an empty list, SidePairs.
2. For each side S in the polygon:
3. For each other side S_other in the polygon:
4. Determine whether S_other is a neighbor of S along the point path.
5. If S and S_other are not neighbors, AND if SidePairs does not already contain the pair (S, S_other), add the pair to SidePairs.
6. For each side pair in SidePairs:
7. Execute a function HasIntersection(Side1, Side2), to see if the two sides in the pair intersect
8. If the side pair intersects, either return immediately, or flag the side pair and continue.
9. Report out the result as a boolean, or as a list of all intersecting side pairs.

Now let's look at the function HasIntersection. Comparing two line segments to see if they intersect is somewhat like asking whether two geometric lines intersect, except that unlike geometric lines, line segments are defined only on a restricted domain:

x_{lower bound} <= x <= x_{upper bound}

This restricted domain is the "shadow" a line segment casts on the x-axis.

Two line segments can only intersect if their shadows overlap, because only then can there be an x-value for which both share the same y-value. This test should be the first step in HasIntersection.

Each line segment has two (x, y) endpoints. We need only look at the four endpoint x-coordinate values to determine whether there is overlap, and if so what the overlapping domain is:

1. For each pair of line segments S₁, S₂, where S₁ has lower and upper endpoint x-values x_S1Low and x_S1High, and S₂ has lower and upper endpoint x-values x_S2Low and x_S2High:
2. Find the maximum lower x- value: x_LowerMax = MAX(x_S1Min, x_S2Min)
3. Find the minimum upper x-value: x_upperMin = MIN(x_S1Min, x_S2Min)
4. Execute the following CASE logic:
5. If x_LowerMax < x_upperMin the domains overlap, and the overlapping includes all x values between x_LowerMax and x_upperMin. An intersection of line segments is possible.
6. Determine whether the segments actually intersect by calling another function, LinesIntersectOnSharedDomain. More about that later.
7. If x_LowerMax > x_upperMin, the two line segment have no domain overlap, so there can be no intersection. No further analysis is needed.
8. If x_LowerMax = x_upperMin, the two line segment domains overlap at a single point on the x-axis. If the y-values there are equal, the line segments touch to form a vertex. Since we have already excluded immediate neighbors, this happens when a line segment "re-contacts" an earlier-defined vertex point. This is not a true crossing, so no further analysis is needed.

Finally, here is the pseudocode for LinesIntersectOnSharedDomain:

1. For the line segments S₁, S₂, obtain the equation of the lines passing through their endpoints.
2. Determine the (x, y) intersection point of the two lines if they are not parallel.
3. If the x-value in the (x, y) intersection point lies inside the overlapping domain x_LowerMax <= x <= x_upperMin, the line segments intersect. Otherwise, they do not.