Trovare i punti n più vicini a qualsiasi punto arbitrario in due dimensioni (albero r, quadrifoglio, indice spaziale)

2

Ho una distribuzione di oggetti punto bidimensionali. Come è possibile trovare il numero N più vicino di punti a un dato punto senza scorrere sull'intera collezione di punti (mantenendo solo la "n" minima)? Lo farò per ogni punto in modo tale che la tecnica della forza bruta (che sto usando in questo momento. Ci sono 12.000 punti in questo set, quindi a volte l'ottimizzazione prematura è il .. percorso maturo da intraprendere.

Ho esaminato gli alberi R tuttavia, per quanto so che restituiscono tutti i punti entro una determinata distanza di un punto, questo potrebbe funzionare, ma avrei bisogno di iniziare a distanze estremamente ridotte e fare successivamente ricerche più ampie fino a trovare 'n'. Forse avrei anche bisogno di creare un oggetto cerchio geometrico personalizzato e usarlo per legare la ricerca al posto del quadrato predefinito, pensieri su questo approccio? Il cerchio è necessario?

I quadrifoli sono meglio per questo? È possibile attraversare le caselle più piccole o più grandi alla ricerca di 5 punti più vicini? Sembra che questo potrebbe avere anche un potenziale - anche se ho solo preso una rapida occhiata a questo algoritmo rispetto a r-trees.

Qual è il modo migliore per affrontarlo in modo accurato senza ricorrere alla forza bruta?

    
posta easymoden00b 14.04.2015 - 15:59
fonte

1 risposta

1

Questo è facile.

  • Cammina lungo l'albero (quad tree o R-tree, ecc.) fino a trovare il nodo più basso che contiene il "punto di ricerca".
  • Quindi guarda il genitore di quel nodo e controlla tutti i punti contenuti all'interno del genitore (comprese le sottovoci)
  • Se non hai trovato abbastanza punti, passa al genitore del genitore ecc.

Ricorda

  • Che il punto più vicino potrebbe essere in un nodo fratello.
  • Per ulteriori "contrassegni" ordina la ricerca in modo da poter eseguire il salvataggio non appena sai che hai il n punto di chiusura.
  • Tenendo una pila di nodi mentre cerchi in basso, non è necessario memorizzare un puntatore al genitore in ogni nota ad albero.
  • Il modo in cui dividi un nodo in sottonodi non cambia questo, quindi R-Tree e Quod Tree possono essere ricercati nello stesso modo.
risposta data 28.07.2015 - 12:42
fonte

Leggi altre domande sui tag