Trovare tutti gli oggetti 3D all'interno di una certa distanza dal punto

Question

Ho un set di oggetti (chiamiamolo points) che contengono i componenti X-y e z delle loro posizioni all'interno di uno spazio preciso. Vorrei modellare le interazioni tra gli oggetti in points, tuttavia, non posso farlo a meno che non possa trovare rapidamente gli oggetti nel set che sono meno di una certa distanza da uno degli oggetti in questo set.

Questo suona indubbiamente un po 'poco chiaro, quindi lascia che il primo punto di generazione di points abbia coordinate <x, y, z>, vorrei capire quale degli oggetti in points ha una distanza inferiore a [alcuni arbitrari Valore] dal primo punto.

Stavo considerando un'implementazione di un R-Tree per farlo in Java, eppure mi sento come se questo sia un problema abbastanza comune che esiste una soluzione più semplice. Se non ce n'è uno, apprezzerei una semplice spiegazione del metodo con cui una interroga un R-Tree per trovare oggetti che si trovano all'interno di alcuni generatori x da un oggetto nell'albero, dove x è già noto. Modifica: Nota che i valori di posizione di questi oggetti cambieranno

Answer 1

La r * -tree è una buona buona struttura di dati per questo, in particolare quando i punti stanno cambiando.È progettato per le modifiche, in realtà.

L'albero K-D è più semplice, ma non supporta molto bene i cambiamenti.È progettato per una costruzione di bulk una tantum.

Tuttavia, poiché i tuoi dati sono solo tridimensionali: se i tuoi dati sono abbastanza piccoli da adattarsi alla memoria, e i valori massimi e minimi di x, y, z sono noti, un octree o aSEMPLICE Grid potrebbe essere il compromesso di semplicità e prestazioni di cui hai bisogno.

In particolare se risolvi prima il raggio di query, un file griglia è difficile da battere.R * -Trees Attraente Quando è necessario supportare più raggi, query per finestre, query più vicine al vicine e tutto questo.

Answer 2

Modifica: Square= Cube (Comunque immaginandolo nello spazio 2D sarebbe forse meglio, quindi puoi convertirlo in 3D)

Stavo pensando e penso di averlo risolto. Tuttavia questa è solo la soluzione "mia", non ho alcun riferimento per questo.

crei classe "quadrato", che ha posizione, larghezza ed elenco di punti in quell'oggetto.

Tutti i quadrati verranno memorizzati in array o hashmap in base alla loro posizione, quindi possono essere accessibili rapidamente, se si conosce la posizione che cerchi.

Tutti i quadrati saranno distribuiti regolarmente, quindi - dal punto di vista dell'istanza "punto" - non devi conoscere tutti i quadrati esistenti per capire in un tempo costante in cui appartieni. (Esempio: so che ci sono quadrati con larghezza di 40 e sono distribuiti dalla distanza di 20. Sono in posizione 10001, quindi so che appartengo a piazze in posizione 9980 e 10000)

I quadrati saranno attraversati l'uno dall'altro, quindi un punto può essere in più quadrati.

Quando fai qualcosa, per ogni punto, tu controlli solo i punti, che vengono memorizzati in quadrati a cui appartiene. Naturalmente - i quadrati devono essere abbastanza grandi e abbastanza incrociati per raggiungere il tuo obiettivo.

Quando i punti in movimento, sono responsabili della registrazione e della registrazione dei quadrati.

---

.

1D Esempio:

Lezioni: Line segment e Point

Attrributes:

.

Line segment: int position, List<Points> points

Point: int position, List<LineSegment> lineSegments

Voglio interagire solo con punti di distanza di 20.

Quindi creo istanze di Line segments con larghezza 40 e li ho messi uno per uno in una distanza di 20.

Così saranno in posizione 0, 20, 40, 60 ....

Il frist si coprà area 0-40, secondo 20-60 ecc.

Li ho inseriti nell'array e con la posizione nota, posso accederle rapidamente: arrayOfLineSegments[position/20]

Quando creo il punto, lo aggiungo al line segments a cui appartiene.

Quando aggiorno, ogni punto interagisce solo con i punti in Selezioni.

Quando muoverò il punto, registrati e discutere gli schemi che appartiene a.

Answer 3

È possibile utilizzare A per loop per controllare la matrice di oggetto.

Utilizzare la seguente formula: d = sqrt[(x1-x2)^2 + (y1-y2)^2 + (z1-z2)^2]

X1, Y1, Z1 Essendo il primo punto in Points e X2, Y2, Z2 Essendo i punti dell'oggetto che stai controllando.Questo controllerà il tuo punto noto contro tutti gli altri punti.Se la distanza (D) è inferiore alla distanza desiderata x, fai tutto ciò che vuoi che il programma di fare.