Detección de polígonos no válidos (autointersección o contacto)

Question

Un polígono no válido puede definirse como uno que se interseca a sí mismo, o uno en el que las líneas hacen contacto, es decir, las dos formas en la parte superior de esta imagen.

Dados los Puntos XY de un polígono, ¿qué lógica (usando C# preferiblemente, pero mientras vea lógica, puedo traducir) se podría implementar para detectar estas situaciones?

He mirado el Algoritmo Bentley-Ottmann Sin embargo, esto detecta si las líneas se cruzan y no si se tocan. Por no hablar de que en el artículo de la wikipedia dice que es lento.

Answer 1

Si no quieres escribir algo desde cero, posiblemente podrías llamar a Check Geometry desde ArcToolbox. Lo he utilizado algunas veces para ciertas geometrías. No estoy seguro de si todos los casos anteriores se devolverá como mala geometría. Es posible que desee probar la herramienta en un conjunto de datos de prueba. Por favor, manténganos informados.

Answer 2

Terminé eligiendo el algoritmo Hoey-Shamos. Estoy en medio de la implementación (el código funciona, pero es demasiado lento, lo estoy optimizando)

No puedo publicar mi código exacto ya que esto es para una organización privada, pero puedo publicar un enlace al código Java en el que me basé

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

Line2D, como se menciona en el enlace anterior, es una clase Java. He creado una versión en C# de esa clase. Los TreeSets no están disponibles en C#, así que utilicé un List, pero tendré que encontrar una manera de optimizarlo, ya que estoy bastante seguro de que ahí está mi cuello de botella. Puedo compartir la clase Line2D, pero me temo que eso es todo :(

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

}