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.

Answer 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. Please keep us posted.

Answer 2

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

}