Come rilevare due forme in movimento sovrapposte?

Naviga le tue risposte
2

Dato un elenco di cerchi con le sue coordinate (xey) che si muovono ogni secondo in direzione diversa (sud-est, sud-ovest, nord-est e nord-ovest), e il cerchio cambierà direzione se colpisce il muro come un rimbalzo, quindi come possiamo rilevare se qualcuno di essi si scontrano o si sovrappongono l'uno con l'altro? Non sono sicuro di poter utilizzare alcune strutture di dati come Binary Search Tree perché tutte le coordinate variano ogni secondo, quindi l'albero dovrà essere ricostruito di conseguenza. Oppure possiamo usare Algoritmo della linea di scansione verticale ogni volta? Qualche idea su come farlo in modo efficiente?

    
posta peter 27.10.2012 - 06:49
fonte

2 risposte

5

Quadtree è un fratello dell'albero binario, per 2D.

Ecco una buona spiegazione con l'esempio live in Javascript: link

    
risposta data 27.10.2012 - 06:57
fonte
4

Se ne hai un numero modesto e dato che sono cerchi, puoi confrontare la distanza tra i punti centrali di ogni cerchio con tutti gli altri. Se la distanza è inferiore alla somma dei due raggi, si sovrappongono.

Questo approccio non è terribilmente efficiente, ma dovrebbe essere sufficiente per i numeri nelle dozzine senza alcun impatto notevole sulle prestazioni. E ci sono un paio di modi per velocizzarlo (confrontando i valori al quadrato invece di fare un costoso sqrt nel calcolo della distanza e controllando se la differenza delle coordinate x o y dei punti medi è maggiore della somma dei raggi, per esempio). / p>     

risposta data 27.10.2012 - 08:28
fonte

Leggi altre domande sui tag

Quando una funzione viene chiamata in Javascript, esiste un modo semplice per trovare dove viene dichiarata una funzione? Utilizzo di un prodotto con licenza GNU GPLv3 per uso aziendale interno