Trovare le coordinate più vicine in un array?

Question

Ho due ArrayList, tipo di dati Double, 1.latitudes 2. longitudini, ciascuna ha oltre 200 elementi

dicono i dare un casuale coordinate prova, dire (1.33, 103.4), il formato è [latitudine , longitudine]

c'è qualche algoritmo per trovare facilmente il punto più vicino, o devo forza bruta calcolare ogni punto possibile, trovare ipotenusa e quindi confrontare oltre 200 ipotenus per restituire il punto più vicino? grazie

Answer 1

Se gli array sono ordinati, è possibile utilizzare la ricerca binaria per trovare la posizione di un punto richiesto nell'array. Dopo aver trovato l'indice, dovresti controllare quattro punti vicini per trovare il più vicino.

1) Supponiamo di avere due array ordinati longitudini-saggio e latitudini-saggio

2) si esegue una ricerca prima e trovate due punti prossimi

3) Poi di ricerca di uno e trovate altri due punti

4) Ora si hanno da due a quattro punti (i risultati potrebbero intersecare)

5) Questi punti formeranno un quadrato intorno punto di destinazione

6) Trova il punto più vicino

Answer 2

Ordinare la serie di punti lungo un asse. Quindi, individuare il punto nell'array più vicino al punto richiesto lungo questo asse e calcolare la distanza (utilizzando qualsiasi metrica appropriata alla topologia e alla scala del problema).

Quindi, cercare lungo l'array in entrambe le direzioni fino a quando la distanza da questi punti è maggiore del risultato migliore finora. Il punto di distanza più breve è la risposta.

Ciò può comportare la ricerca dell'intero array ed è una forma di Branch and bound vincolata dalla geometria del problema. Se i punti sono distribuiti in modo abbastanza equo attorno al punto che stai cercando, la scansione non richiederà molte prove.

indici spaziali alternative (come quad-alberi) darà risultati migliori, ma proprio piccolo numero di punti renderebbero il costo di installazione nel preparare l'indice più grande di un semplice ordinamento. Dovrai tenere traccia delle variazioni di posizione causate dall'ordinamento in quanto l'altro array non verrà ordinato nello stesso modo. Se si modificano i dati in una singola serie di punti, l'ordinamento riordina interi punti allo stesso tempo.

Answer 3

non è vero che il valore lat (o long) più vicino dovrebbe essere scelto per la ricerca sull'asse lungo (o lat), infatti si potrebbe stare su una lat (o long) ma lontano lungo il lungo (o lat) valore

così modo migliore è quello di calcolare le distanze e ordinarli