algoritmo per dividere ricorsivamente un poligono in quadranti dentro/fuori:come si chiama e dov'è il codice?

Question

Ho molti punti (centinaia di migliaia) e voglio verificare quali si trovano all'interno di un poligono.Per un poligono relativamente piccolo (vale a dire che probabilmente contiene solo decine o centinaia di punti) posso semplicemente utilizzare il riquadro di delimitazione del poligono come controllo iniziale, quindi eseguire un normale controllo punto in poligono per quei punti all'interno del riquadro .Ma immagina un poligono grande (cioè che probabilmente contenga migliaia dei miei punti) di forma irregolare.Molti punti supereranno il controllo del riquadro di delimitazione e inoltre il controllo punto in poli sarà più costoso perché il poligono più grande è composto da molti più punti.Quindi mi piacerebbe essere in grado di filtrare la maggior parte dei punti dentro o fuori senza dover eseguire il controllo completo del punto in poli.

Quindi, ho un piano, e soprattutto voglio sapere se quello che sto descrivendo è un algoritmo ben noto, e se sì, come si chiama e dove potrei trovare il codice esistente per esso.Non credo che quello che sto descrivendo sia un quad-tree o un r-tree e non so come cercarlo.Lo chiamo "albero rettangolo" qui sotto.

L'idea è, per gestire questi poligoni più grandi:

Esegui un pre-processo "albero rettangolo", in cui la profondità dell'albero rettangolo varia in base alla dimensione del poligono (ovvero, consenti maggiore profondità per un poligono più grande).L'albero rettangolo dividerebbe il riquadro di delimitazione del poligono in quattro quarti.Verificherebbe se ogni quarto di rettangolo è completamente all'interno del poligono, completamente all'esterno del poligono o nessuno dei due.Nel caso di nessuno dei due dividerebbe ricorsivamente i sottoretti, continuando in questo modo finché tutti i retti non fossero completamente all'interno o all'esterno, o fino al raggiungimento della profondità massima.Quindi l'idea è che (a) il tempo di pre-elaborazione per creare questo albero, anche se esso stesso eseguirà diversi controlli punto nel poligono, ne vale la pena perché quel tempo è sminuito dal numero di punti da controllare, e (b) la stragrande maggioranza dei punti può essere gestita utilizzando semplici controlli del riquadro di delimitazione (generalmente alcuni controlli mentre si scende dall'albero), e quindi un numero relativamente piccolo dovrebbe eseguire il controllo completo del punto nel poligono ( per quando raggiungi un nodo foglia che è ancora "nessuno dei due").

Come si chiama quell'algoritmo?E dov'è il codice?In effetti non sembra così difficile da scrivere, ma ho pensato di chiedere prima di dedicarmi alla programmazione.

Answer 1

In realtà ho finito per utilizzare un approccio correlato ma diverso.Mi sono reso conto che essenzialmente la struttura ad albero che stavo costruendo non era altro che il poligono disegnato a bassa risoluzione.Ad esempio, se il mio albero scendesse a una profondità di 8, in realtà sarebbe stato come disegnare il mio poligono su una bitmap con risoluzione 256x256 e poi eseguire test di pixel hit rispetto a quel poligono.Quindi ho esteso l'idea e ho utilizzato una libreria grafica veloce (la libreria CImg).Disegno il poligono su una bitmap in bianco e nero di dimensione 4000x4000.Quindi controllo semplicemente i punti come pixel rispetto a quella bitmap.La magia è che disegnare quell'enorme bitmap è davvero veloce rispetto al tempo che ho impiegato per costruire l'albero.Quindi ottengo una risoluzione molto più elevata di quella che avrei mai potuto ottenere con il mio albero.

Un problema è la capacità di rilevare punti vicini al bordo estremo del poligono, che potrebbero essere inclusi o esclusi in modo errato a causa di problemi di arrotondamento/risoluzione, anche alla dimensione 4000x4000.Se hai bisogno di sapere con precisione se quei punti sono dentro o fuori, potresti disegnare un tratto attorno al poligono in un altro colore e, se il test dei pixel colpisce quel colore, eseguiresti il ​​punto completo nel controllo poligonale.Per i miei scopi la risoluzione 4000x4000 era abbastanza buona (potrei tollerare un'inclusione/esclusione errata per alcuni dei miei punti limite).

Quindi il trucco fondamentale di questa soluzione è l'idea che gli algoritmi di disegno dei poligoni siano semplicemente super veloci rispetto ad altri modi in cui potresti "digitalizzare" il tuo poligono.