Linea orizzontale più veloce < - > algoritmo di intersezione poligonale convesso?

Question

Devo risolvere una cosa relativamente semplice: ho un poligono 2D convesso di n-vertici e una linea orizzontale (!) con alcune coordinate 'y'. Ho solo bisogno di una cosa: verificare se il poligono è attraversato da questa linea (ovvero ha 2 intersezioni) oppure no.

Il più veloce a cui riesco a pensare è trovare coordinate min / max y all'interno di un poligono (loop ripetuto n volte con due confronti e due negozi) e quindi confrontare se il min y < = y < max y.

In qualche modo ritengo che questo potrebbe essere risolto più "matematicamente" ma finisco sempre con un codice più lento (ad esempio il modo vettoriale - ho bisogno di calcolare le differenze per n [i] e n [i + 1], quindi moltiplicarli, aggiungere ecc - molto più lentamente di 2 cmps + negozi).

Answer 1

Devi solo verificare se il tuo poligono ha un punto con y1 < y e uno con y2 > y. Non appena hai trovato questi due punti, hai finito. Se puoi indicizzare i tuoi punti in base alla coordinata y, dovrebbe essere una ricerca veloce.

Answer 2

Se si tratta di una linea 2D orizzontale quindi sì, il metodo che hai descritto è probabilmente il più veloce. Potresti anche cortocircuitare, come se avessi superato il controllo e avessi un min + max che sono > e < il tuo valore y allora hai un incrocio.

Answer 3

Se devi farlo ogni volta sul raw, probabilmente non troverai alcun trucco per renderlo più veloce di così.

Se è possibile memorizzare nella cache il valore Y min / max con il poligono, è possibile risparmiare tempo non eseguendo il ciclo di ogni vertice ogni volta che si esegue il test.

Se al tuo poligono è associato un rettangolo di selezione associato, puoi testarlo in base alle estensioni del riquadro anziché al poligono e ottenere lo stesso risultato più velocemente.

Answer 4

Un altro approccio, è descritto qui: algoritmo ottimale se la linea interseca il poligono convesso . Ma poiché stai gestendo linee ortogonali, puoi semplificarlo un po ':). Pertanto, la complessità totale è il registro N senza memorizzare i valori.