Resolver la auto-intersección de polígonos más rápido que O( $n^2$ )

Question

Dado un polígono 2D representado por una secuencia ordenada de puntos en un plano. El polígono sólo puede ser cerrado y tener auto-intersecciones.

Estoy buscando un algoritmo que resuelva las auto-intersecciones de este polígono más rápido que O( $n^2$ ).

He intentado separar la parte del algoritmo de recorte de Vatti, que resuelve las auto-intersecciones, pero no lo he conseguido. El resultado correcto es algo así:

Answer 1

Probablemente sepa que la simplicidad se puede probar en O( n ) a través del algoritmo de Chazelle, pero es tan complicado que nadie lo implementa. Son preferibles las implementaciones más sencillas sin la misma complejidad temporal asintótica. mucho más preferibles. Por ejemplo:

Feito, F., Juan Carlos Torres y A. Ureña. "Test de orientación, simplicidad e inclusión para polígonos planos". Ordenadores y gráficos 19.4 (1995): 595-600. ( Descarga del PDF .)

Si realmente quieres una buena complejidad temporal asintótica, puedes conseguir fácilmente O( n registro n ) mediante el algoritmo de Shamos & Hoey. Véase, por ejemplo La explicación de Dan Sunday .