c# - Compruebe si Polygon es auto-intersecante
.net geometry (3)
Compruebe si algún par de segmentos de línea no contiguos se intersecan.
Tengo un objeto System.Windows.Shapes.Polygon, cuyo diseño está determinado completamente por una serie de puntos. Necesito determinar si este polígono se auto interseca; es decir, si alguno de los lados del polígono se interseca con cualquiera de los otros lados en un punto que no es un vértice. ¿Hay una manera fácil / rápida de calcular esto?
Para completar, agrego otro algoritmo a esta discusión.
Suponiendo que el lector sepa acerca de los cuadros delimitadores alineados con el eje (Google, si no es así) puede ser muy eficiente encontrar rápidamente pares de bordes que tengan su enfrentamiento de AABB utilizando el "algoritmo de barrido y podado". (buscalo en Google). Las rutinas de intersección son llamadas en estos pares.
La ventaja aquí es que incluso puede cruzar un borde no recto (círculos y splines) y el enfoque es más general aunque casi igualmente eficiente.
Huella de memoria fácil, lenta y baja : compare cada segmento con todos los demás y verifique las intersecciones. Complejidad O (n 2 ) .
Huella de memoria media, ligeramente más rápida (versión modificada de arriba): almacene los bordes en "cubos" espaciales, luego ejecute el algoritmo anterior en cada cubo. Complejidad O (n 2 / m) para m cucharones (suponiendo una distribución uniforme).
Huella de memoria rápida y alta : use una función de hash espacial para dividir los bordes en cubos. Compruebe si hay colisiones. Complejidad O (n) .
Huella de memoria rápida y baja : use un algoritmo de línea de barrido, como el que se describe here (o here ). Complejidad O (n log n)
El último es mi favorito, ya que tiene una buena velocidad: el equilibrio de la memoria, especialmente el here . La implementación tampoco es demasiado complicada.