¿Cómo detectar si un polígono tiene autointersecciones?

Question

Imagine que tiene un polígono 2D (un 2D closed polygonal chain para ser más preciso). ¿Cómo se comprueba si contiene autointersecciones? Puede ser convexo o cóncavo, orientarse en sentido horario o antihorario.

Ahora, podría ejecutar un algoritmo estándar O(N log N) para verificar si se cruzan dos segmentos. Pero creo que debido a que tenemos alguna estructura adicional, el orden de los segmentos y el hecho de que cada dos segmentos consecutivos se encuentran en los puntos finales, podría idearse un algoritmo más simple y más rápido (¿quizás O(N)?).

¿Alguna idea?

Answer 1

¿Necesita simplemente verificar las intersecciones propias, o encontrarlas todas? Este último es más difícil que O(N log N), ya que puede tener intersecciones O(n^2) con n segmentos.

Si solo necesita averiguar si existen autointersecciones, o si encuentra una pequeña cantidad de ellas, busque here. Este documento parece reclamar exactamente lo que necesita, especialmente en la sección de planarización de polígonos. Dudo que implementar el algoritmo descrito sea simple o valga la pena para cualquier problema de tamaño razonable. Pero tal algoritmo existe. Descargo de responsabilidad: no he tratado de leer el documento y entenderlo.