c# - Detecting invalid polygons (self-intersecting or touching)

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

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

}