Controlla se Polygon si sta autointeratori

Question

Ho un oggetto System.windows.shapes.polygon, il cui layout è completamente determinato da una serie di punti. Devo determinare se questo poligono si sta intersecando; cioè, se uno dei lati del poligono interseca uno degli altri lati in un punto che non è un vertice. C'è un modo semplice/veloce per calcolarlo?

Answer 1

• Impronta di memoria facile, lenta e bassa: Confronta ogni segmento con tutti gli altri e controlla le intersezioni. Complessità SU²).

• Leggermente più veloce impronta di memoria media (versione modificata di sopra): memorizzare i bordi in "secchi" spaziali, quindi eseguire algoritmo sopra su base per bucket. Complessità SU² / m) per m secchi (assumendo distribuzione uniforme).

• Footprint di memoria veloce e alta: Usa una funzione hash spaziale per dividere i bordi in secchi. Controlla le collisioni. Complessità SU).

• Footprint di memoria veloce e bassa: Utilizzare un algoritmo della riga, come quello descritto qui (o qui). Complessità O (n log n)

L'ultimo è il mio preferito in quanto ha una buona velocità: bilanciamento della memoria, in particolare il Algoritmo Bentley-Ottmann. L'implementazione non è nemmeno troppo complicata.

Answer 2

Controlla se qualche paio di non contiguo I segmenti di linea si intersecano.

Answer 3

Per completezza aggiungo un altro algoritmo a questa discussione.

Supponendo che il lettore sia a conoscenza delle scatole di delimitazione allineate agli assi (Google IT in caso contrario), può essere molto efficiente trovare rapidamente coppie di bordi che hanno lo scontro di AABB utilizzando l'algoritmo "Sweep and prugne". (Google IT). Le routine di intersezione vengono quindi chiamate su queste coppie.

Il vantaggio qui è che potresti persino intersecare un bordo non dritto (cerchi e spline) e l'approccio è più generale sebbene quasi simile efficiente.