Come trovare prima intersezione di un raggio con cerchi in movimento

Question

sono stato alle prese con un problema per un po 'e finora non hanno trovato una soluzione migliore, allora l'ingenuo uno:

N cerchi sono dati che si stanno muovendo secondo a una legge lineare. Per ognuno dei cerchi abbiamo il suo raggio iniziale (momento 0.0), le coordinate iniziali e il suo raggio e le coordinate al momento 1.0 (momento finale). Abbiamo anche raggi k dati con coordinate della loro origine e un vettore lungo il raggio. Ogni raggio esiste solo in un dato momento t _k. Devo essere in grado di trovare la prima intersezione di un raggio con uno qualsiasi dei cerchi. Il numero previsto di k è piuttosto grande (milioni o miliardi) e il numero atteso di cerchi (migliaia). Ho bisogno di una soluzione più veloce quindi controllo tutti i raggi contro tutti i cerchi.

Ho cercato su Internet per un po 'di tempo, ma non ho trovato un buon approccio alla soluzione. Sarà apprezzata anche un'idea per il più facile problema dei cerchi che non si muovono.

Ho la sensazione che un albero di kd dovrebbe essere appropriato per il caso statico e forse un kd-tree cinetico risolverà quello più difficile. Ancora non riesco a capire come usare kd-tree anche per quello più facile.

Answer 1

È possibile considerare questo come caso statico in 3D con il tempo come coordinata aggiuntiva. Cerchio con percorso diventato fruscio e raggio in un piano orario = t _k. Se i tronconi non sono posizionati troppo densi rispetto al partizionamento dello spazio binario (albero k-d, ...) può essere d'aiuto.

Per trovare tutte le partizioni attraversate dal raggio trovare prima la partizione in cui è l'origine e che la traversa (nella struttura ad albero) per il vicino della partizione nella direzione del raggio. Dipende dal metodo di partizionamento utilizzato. È lineare nel numero di partizioni attraversate da raggi.

Aggiornamento: È l'idea di mettere il trambusto in ogni partizione che sta toccando. Un tronco sarà in più partizioni.

Questo è un esempio in 1 dimensione più tempo. Tutto è lo stesso, i cerchi hanno il punto iniziale e finale e il raggio iniziale e finale.

1 | E /
    | . /
    | ./
    | ./
    | ./
0 | S/
t/X 

partizionamento in direzione X:

| E :/
    | . :/ 
    | . : 
    | . /: 
    | ./: 
    | S/: 
      X 

Questa trapezoidale andrà in entrambe le partizioni.

partizionamento in direzione del tempo:

| E :/
    | . :/ 
    | . : 
t------------------- 
    | ./: 
    | S/: 
      X 

trapezio da X partizione sinistra andrà in entrambe le partizioni di tempo, mentre nella partizione destra X andrà solo in partizione superiore.

Per implementarlo è necessario calcolare c'è un'intersezione tra la linea e il piano dell'asse su una parte del piano e se non c'è un'intersezione su quale lato di un piano è una linea. Il calcolo è lo stesso in caso 2D o anche in dimensioni superiori.

Answer 2

(Pensando ad alta voce) Potresti voler usare una griglia ad otto o più risoluzioni con l'algoritmo di Bresenham per eliminare rapidamente molti controlli?