Para un polígono definido como una secuencia de (x, y) puntos, ¿cómo puedo detectar si es complejo o no? Un polígono complejo tiene intersecciones con sí mismo, como se muestra:Probando si un polígono es simple o complejo
¿Existe una solución mejor que comprobar cada par que tendría una complejidad en tiempo de O (N)?
Existen métodos de barrido que pueden determinar esto mucho más rápido que un enfoque de fuerza bruta. Además, se pueden usar para dividir un polígono no simple en múltiples polígonos simples.
Para obtener más información, consulte this article, en particular, este code to test for a simple polygon.
El enlace del código es http://geomalgorithms.com/a09-_intersect-3.html#simple_Polygon() La versión de auto-escape de markdown no funciona. –
Consulte Bentley Ottmann Algorithm para obtener un método basado en barrido O ((N + I) log N) para esto. Donde N es el número de segmentos de línea e I es el número de puntos de intersección.
De hecho, esto se puede hacer en el uso del tiempo lineal algoritmo de triangulación de Chazelle. Triangula el polígono o descubre que el polígono no es simple.
Excepto que hay pocas o ninguna implementación práctica de Chazelle debido a su complejidad para implementar. –
Bueno, si el usuario ingresa el polígono con gmaps, entonces no es probable que tenga más de 100 vértices. En este caso, iría primero con una solución simple y veré si es suficiente. –
@Nikita, la pregunta puede haber sido engañosa en ese sentido. El usuario también puede editar un polígono existente con miles de vértices. De todos modos, todavía estoy interesado en saber cuál es el mejor enfoque para esto. –