Is there an easy and fast way of checking if a 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

• Easy, slow, low memory footprint: compare each segment against all others and check for intersections. Complexity O(n²).

• Slightly faster, medium memory footprint (modified version of above): store edges in spatial "buckets", then perform above algorithm on per-bucket basis. Complexity O(n² / m) for m buckets (assuming uniform distribution).

• Fast & high memory footprint: use a spatial hash function to split edges into buckets. Check for collisions. Complexity O(n).

• Fast & low memory footprint: use a sweep-line algorithm, such as the one described here (or here). Complexity O(n log n)

The last is my favorite as it has good speed - memory balance, especially the Bentley-Ottmann algorithm. Implementation isn't too complicated either.

Answer 2

Check if any pair of non-contiguous line segments intersects.

Answer 3

For the sake of completeness i add another algorithm to this discussion.

Assuming the reader knows about axis aligned bounding boxes(Google it if not) It can be very efficient to quickly find pairs of edges that have theirs AABB's clashing using the "Sweep and Prune Algorithm". (google it). Intersection routines are then called on these pairs.

The advantage here is that you may even intersect a non straight edge(circles and splines) and the approach is more general albeit almost similarly efficient.

Answer 4

I am a new bee here and this question is old enough. However, here is my Java code for determining if any pair of sides of a polygon defined by an ordered set of points crossover. You can remove the print statements used for debugging. I have also not included the code for returning the first point of crossover found. I am using the Line2D class from the standard java library.

/**
 * Checks if any two sides of a polygon cross-over.
 * If so, returns that Point.
 * 
 * The polygon is determined by the ordered sequence
 * of Points P 
 * 
 * If not returns null
 * 
 * @param V vertices of the Polygon
 * 
 * @return
 */
public static Point verify(Point[] V)
{
    if (V == null)
    {
        return null;
    }
    
    int len = V.length;
    
    /*
     * No cross-over if len < 4
     */
    if (len < 4)
    {
        return null;
    }
    
    System.out.printf("\nChecking %d Sided Polygon\n\n", len);
    
    for (int i = 0; i < len-1; i++)
    {
        for (int j = i+2; j < len; j++)
        {
            /*
             * Eliminate combinations already checked
             * or not valid
             */
            
            if ((i == 0) && ( j == (len-1)))
            {
                continue;
            }
            
            System.out.printf("\nChecking if Side %3d cuts Side %3d: ", i, j);
            
            boolean cut = Line2D.linesIntersect(
                    V[i].X,
                    V[i].Y,
                    V[i+1].X,
                    V[i+1].Y,
                    V[j].X,
                    V[j].Y,
                    V[(j+1) % len].X,
                    V[(j+1) % len].Y);
            
            if (cut)
            {
                System.out.printf("\nSide %3d CUTS Side %3d. Returning\n", i, j);
                return ( ... some point or the point of intersection....)
            }
            else
            {
                System.out.printf("NO\n");
            }
        }
    }
    
    return null;
}