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?

Lenzi

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.

Fascista

I'm trying to get my head around the last algorithm as we speak; particularly, I'm having trouble tracking on the meaning/purpose of structure T. – Lenzi

T is a structure, which contains the line segments that cross the sweep line L. The most efficient structure would be a binary search tree (see also the Bentley–Ottmann algorithm). – Fascista

I added another link where the Bentley-Ottmann algorithm is described with illustrations. – Fascista

So C(p) is all the line segments (found in T) where p is a point that is colinear with the line segment, then. – Lenzi

Yes; but by definition of T, that point p will always be inside the line segments. – Fascista

I'll take a stab at implementing Bentley-Ottmann; Shamos-Hoey blew up in my face because, of course, they all intersect at their vertices :\ – Lenzi

It worked, though I had to modify the algorithm a bit. Specifically, instead of finding a given line segment that point P belonged to, I had to find the set of line segments (because I knew I had some legitimate intersections) and then, once given my list of intersections, I had to filter out the expected intersections and return a count of the remainder (>0 => Non-simple polygon). All in all, a fun little exercise. – Lenzi

Both of the sweep-line algorithm links are down :*( – Tisiphone

Even the slowest version is trivial to make O(n!) by only checking each line segment against those that has already been checked. – Scharff

Answer 2

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

Enamel

They should all intersect at the vertexes; the question then becomes what the fastest way to check for a non-vertex intersection among an arbitrary set of line segments is. – Lenzi

Good point, edited it to check if non-contiguous segments intersect. I don't think there's a built-in method, you'll have to write a method. Start by getting the Polygon.Points – Enamel

Don't you mean open line segments? I've never heard of non-contiguous line segments. – Scharff

Answer 3

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;
}

Katalin

I disagree with Peter Duniho. This code is useful because it is the algorithm that is important, not the programming language. Also, Java and C# are extremely similar, and anyone interested in this problem can easily port the code to their target language. – Shabby

@Shabby maybe you can vote up so I get some points? I can also re-do this in C# if you think that is critical. – Katalin

@ParaParasolian, I did up-vote. You had -1; Now you have 0. I think you should have a lot more. – Shabby

I agree that in theory the language does not matter if you where focusing on an effective algorithm. But this is not an effective way to solve the problem. – Grandfather

@Grandfather Could you kindly provide (or point to) a more effective way? – Katalin

@ParaParasolian, there are pointers in the accepted answer. You should use a Sweep-Line algorithm. Take a look at this repo – Grandfather

agree with lwallent (n² time is not very effective), plus the real interesting part is Line2D.linesIntersect() which is not provided. – Indict

Answer 4

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.

Recreant