1

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.

http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Straight_skeleton_2/invalid_polygons.png

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.

3
  • 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, 2013 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, 2013 at 16:23
  • ArcGIS. However I'm writing a C# library that does this for me. Aug 19, 2013 at 16:44

2 Answers 2

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.

1
  • Is the code for this tool open? As in I can view the code? I'm writing a C# class. Aug 19, 2013 at 16:45
1

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

}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.