Detecting invalid polygons (self-intersecting or touching)

Question

An invalid polygon can be defined as one that intersects itself, or one where the lines make contact, ie, the two shapes at the top of this picture.

Given the XYPoints of a polygon, what logic (using C# preferably, but as long as I see logic, I can translate) could be implemented to detect these situations?

I've looked at the Bentley-Ottmann_algorithm, however this detects if lines intersect and not if they touch. Not to mention, it says in the wikipedia article that it's slow.

The Wikipedia article asserts the opposite of slow! Yes, there are improvements that assume special conditions on the polygons: see the Faster Algorithms section in the same Wikipedia article. — whuber, Aug 19 '13 at 15:01
Which GIS system are you wishing to implement such code? If you are using ESRI software then the check geometry tool as suggested below is a good start. If you want to call existing ArcObjects then have a look at the ITopologicalOperator interface? — Hornbydd, Aug 19 '13 at 16:23
ArcGIS. However I'm writing a C# library that does this for me. — Evan Parsons, Aug 19 '13 at 16:44

score 1 · Answer 1 · edited Jun 22 '23 at 07:18

1

If you don't want to write something from scratch, you could possibly call Check Geometry from ArcToolbox. I've used it a few times for certain geometries. Not sure if all of the above cases will be returned as bad geometry. You may want to test the tool on a test dataset.

edited Jun 22 '23 at 07:18

PolyGeo

65,136
29
109
338

answered Aug 19 '13 at 14:55

Garima V

128
1
7

score 1 · Accepted Answer · edited Apr 13 '17 at 12:41

I ended up going with the Hoey-Shamos algorithm. I'm in the middle of implementing (code works, but is too slow, I'm optimizing it)

I can't post my exact code since this is for a private organization, but I can post a link to the Java code I based my code off of

https://codereview.stackexchange.com/questions/69/is-this-implementation-of-shamos-hoey-algorithm-ok

Line2D as mentioned in the above link, is a Java class. I created a C# version of that class. TreeSets are not available in C#, so I used a List, but I will have to find a way to optimize that, since I'm pretty sure that's where my bottleneck is. I can share the Line2D class, but that's it I'm afraid :(

public class Line2D
{
    public double X1 = 0;
    public double X2 = 0;
    public double Y1 = 0;
    public double Y2 = 0;

    public XYPoints P1;
    public XYPoints P2;

    public Line2D(XYPoints p1, XYPoints p2)
    {
        P1 = p1; 
        P2 = p2;
        X1 = p1.X;
        X2 = p2.X;
        Y1 = p1.Y;
        Y2 = p2.Y;
    }

    public double getX1()
    {
        return X1;
    }
    public double getX2()
    {
        return X2;
    }
    public double getY1()
    {
        return Y1;
    }
    public double getY2()
    {
        return Y2;
    }

    public XYPoints getP1()
    {
        return P1;
    }

    public XYPoints getP2()
    {
        return P2;
    }

    public bool intersectsLine(Line2D comparedLine)
    {
        if (X2 == comparedLine.X1 && Y2 == comparedLine.Y1)
        {
            return false;
        }

        if (X1 == comparedLine.X2 && Y1 == comparedLine.Y2)
        {
            return false;
        }
        double firstLineSlopeX, firstLineSlopeY, secondLineSlopeX, secondLineSlopeY;

        firstLineSlopeX = X2 - X1;
        firstLineSlopeY = Y2 - Y1;

        secondLineSlopeX = comparedLine.getX2() - comparedLine.getX1();
        secondLineSlopeY = comparedLine.getY2() - comparedLine.getY1();

        double s, t;
        s = (-firstLineSlopeY * (X1 - comparedLine.getX1()) + firstLineSlopeX * (getY1() - comparedLine.getY1())) / (-secondLineSlopeX * firstLineSlopeY + firstLineSlopeX * secondLineSlopeY);
        t = (secondLineSlopeX * (getY1() - comparedLine.getY1()) - secondLineSlopeY * (getX1() - comparedLine.getX1())) / (-secondLineSlopeX * firstLineSlopeY + firstLineSlopeX * secondLineSlopeY);

        if (s >= 0 && s <= 1 && t >= 0 && t <= 1)
        {
            return true;
        }

        return false; // No collision
    }


    public override int GetHashCode()
    {
        return (X1 * 1000 + X2 * 1000 + Y1 * 1000 + Y2 * 1000).GetHashCode();
    }

    public override bool Equals(object obj)
    {
        return (obj.GetHashCode() == this.GetHashCode());
    }

}

Detecting invalid polygons (self-intersecting or touching)

2 Answers2

Linked