Contenitore segmento di linea per un veloce intersezione Ray? (2D)

Question

Ho un raggio, ho bisogno di trovare il segmento di linea più vicina che colpisce. Penso che sia possibile farlo in O (log n) se ordinare i segmenti di linea prima, ma non riesco a ricordare come ordinare loro ... Credo che una sorta di albero avrebbe funzionato meglio, ma come faccio sorta li sia da punto di inizio e fine? Vorrei anche inserimenti veloci in questa struttura dati, se possibile.

Ci sono un sacco di codice per un raggio contro un segmento di linea, ma ho bisogno di qualcosa per un raggio vs molti segmenti di linea ... non so quali termini a Google per.

Un link ad un articolo appropriata è buono, codice C ++ è ancora meglio. Grazie! :)

PS: I segmenti sono in realtà i bordi di un poligono non auto intersecante ordinata in senso antiorario ... ma penso ci può essere qualche vantaggio ordinandoli in modo diverso

Questo è tutto in 2D.

---

Il secondo pensiero, non sono del tutto sicuro che questo è possibile. Una sorta di partizionamento spaziale potrebbe aiutare, ma per il resto, non riesco a pensare a un modo per ordinare le linee in modo che potessero essere confrontati con un raggio arbitrario.

Answer 1

Si potrebbe prendere un riquadro di delimitazione del poligono (x min-max, y coordinate) e costruire una griglia all'interno della scatola. Poi, per ogni cella, ricordare tutte le linee che attraversano la cella.

Trova un intesection in questo modo:

• Scopri quali cellule il raggio colpisce prima (O (1))
• Griglia attraversamento algoritmo a "disegnare" un raggio attraverso la griglia . Quando si preme cella non vuota, controllare tutte le sue linee, controllare se intersezione è all'interno della cellula e scegliere l'intersezione più vicino. Se tutte le intersezioni sono al di fuori della cellula, proseguire (questo è O (lunghezza griglia)).

Si potrebbe anche fare la griglia gerarchica (cioè quadtree -. Un albero che stavi chiedendo), e camminare utilizzando lo stesso algoritmo. Questo viene fatto in raytracing in 3D e la complessità temporale è O (sqrt ( N)).

---

In alternativa, utilizzare l'approccio che ho fatto nella mia raytracer:

• quadtree contenente le linee (edificio quadtree è desribed nel articolo) - di dividere i nodi (= aree) se contengono troppi oggetti in 4 sub-nodi (sotto-aree)

• Raccogliere tutti nodi foglia del quadtree che sono colpito dal raggio:

  Calcola ray-rettangolo intersezione (non duro) per la radice. Se la radice viene colpito dal raggio, procedere con i suoi figli in modo ricorsivo.

La cosa interessante di questo è che quando un nodo della struttura è non ha colpito, hai saltato l'elaborazione di un'intera sottostruttura (potenzialmente una grande area rettangolare).

Alla fine, questo è equivalente ad attraversare la rete - si raccolgono le più piccole celle percorso del raggio, e quindi verificare tutti gli oggetti in loro per intersezione. Non vi resta che provare tutti loro e scegliere l'incrocio più vicino (in modo da esplorare tutte le linee di percorso del raggio).

Questa è O (sqrt (N)).

In griglia di attraversamento, quando si trova un incrocio, è possibile interrompere la ricerca. Per raggiungere questo obiettivo con quadtree attraversamento, si dovrà seach i bambini nel giusto ordine - o ordinare i 4 intersezioni rect dalla distanza o abilmente attraversare la griglia a 4 celle (una siamo tornati al traversal)

.

Questa è solo un approccio diverso, relativamente stesso di difficile attuazione penso, e funziona bene (ho testato su dati reali - O (sqrt (N))). Anche in questo caso, si potrebbe trarre beneficio da questo approccio se si dispone di almeno un paio di righe, quando il poligono ha 10 bordi il beneficio rispetto al solo test tutti loro sarebbe poco credo.

Answer 2

Sei alla ricerca di metodi attivi / Tabella Bordo scanline basate? Si può dare un'occhiata alla voce di Wikipedia per Scanline Rendering o cercare il grafica Gems directory per gli algoritmi (per lo più C, ma po 'di codice C ++ pure) .

Answer 3

Tieni presente che l'ordinamento è un O (n log n) nella migliore delle ipotesi. Si può essere meglio solo controllando ogni individualmente.

Answer 4

Come stai certo che ti ha colpito qualcuno di loro? Se sono le linee, è improbabile.

Se è davvero un poligono (cioè planare) che si sta cercando di testare, il solito modo di fare questo genere di cose è intersecano con il piano prima, quindi verificare che il punto (le coordinate 2d) per interno / esterno poligono.

Forse ho capito male quello che si sta effettivamente facendo.

In intersezioni accelerazione generali con figure complesse è fatto con il partizionamento spaziale (e quindi tecniche come MailBoxing, se i test sono costosi).

[Aggiornamento: ho letto male l'intento originale] È comunque possibile utilizzare (2d) partizionamento spaziale, ma l'overhead potrebbe non essere vale la pena. singolo test sono a buon mercato, se i poligoni non sono complicate potrebbe essere più conveniente per loro andare a piedi. Difficile dire da descrizione.

Answer 5

chiedere chiarimenti, è corretto?

• Si dispone di un insieme dinamico di segmenti di linea L .
• Domanda: dato qualsiasi punto (x, y) ed e qualsiasi direzione del raggio da questo punto, si vuole determinare la linea più vicina a L (se del caso)?

Quindi il punto (x, y) è non risolve? (Potrebbe essere un qualsiasi punto, e ogni direzione?)