[ALGORITMO] Minima distanza tra un punto e un insieme di punti

[ekontar]

Chiedo un consiglio a chi, magari, è più fresco di studi scolastici .....
Ho un punto di coordinate (x,y) e una tabella che contiene un elenco di N punti, ognuno con la propria coordinata (x,y) ... voglio trovare il punto della tabella che ha DISTANZA MINIMA dal punto dato ...
Per il calcolo della distanza tra due punti non ho problemi, inoltre posso (volendo) esplorare la tabella ordinando i punti per x oppure per y (li estraggo con una query).
Io adesso, molto bovinamente, me li passo TUTTI e ogni volta che trovo una distanza più piccola di quella precedente la aggiorno (con la tecnica del pivot ..)
Sono certo, però, che sia un problemino noto e che abbia una soluzione un po' più elegante e veloce.

Qualche idea, per cortesia ?

Grazie
eK

[linoma]

Sn incuriosito cm risolveresti il problema della distanza tra 2 punti? E che sarebbe la tecnica del pivot? Il bubble sort?

[antotan]

La distanza euclidea bidimensionale tra due punti sfrutta il teorema di pitagora. In pratica non fai altro che creare un triangolo rettangolo e calcolarne l'ipotenusa.

Distanza euclidea bi-dimensionale

Spero ti sia utile

[ekontar]

ciao e grazie per l'interessamento ... il COME calcolare la distanza non è un problema: i punti sono in realtà coordinate GPS (LAT,LONG) di località note (nei navigatori satellitari sarebbero i PDI, punti di interesse) e io devo trovare quello più vicino al punto in cui mi trovo, mettiamola così ... la formula per calcolare la distanza si trova in rete, non è naturalmente la distanza euclidea, ma si usa una formula decisamente più complessa e .... sferica ...

Però, come dicevo, non è un problema il calcolo della distanza: la tecnica del pivot che dicevo è la classica, intuitiva, dove si parte con una variabile (minima_distanza) inizializzata ad un valore enorme, poi si passano in rassegna TUTTI i punti della tabella, si calcola la distanza con il punto fisso dato, se la distanza è minore del valore attuale di (minima_distanza), il pivot, si mette il nuovo valore minimo nella variabile e si prosegue ...
alla fine del ciclo, si esce sapendo qual'è il punto più vicino.

Io vorrei sapere se, secondo voi, c'è un metodo più "intelligente" per evitare di fare il confronto con TUTTI i punti della tabella. Temo di no, anche perchè la sola cosa "intelligente" che potrei fare è ordinare i punti per latitudine o longitudine ma non credo che servirebbe a nulla ....

ciao
eK

[antotan]

Originariamente inviato da ekontar
ciao e grazie per l'interessamento ... il COME calcolare la distanza non è un problema: i punti sono in realtà coordinate GPS (LAT,LONG) di località note (nei navigatori satellitari sarebbero i PDI, punti di interesse) e io devo trovare quello più vicino al punto in cui mi trovo, mettiamola così ... la formula per calcolare la distanza si trova in rete, non è naturalmente la distanza euclidea, ma si usa una formula decisamente più complessa e .... sferica ...

Ciao ovviamente non era rivolta a te la risposta, avendo letto che

...Per il calcolo della distanza tra due punti non ho problemi...

ma a linoma

[linoma]

Sinceramente ho fatto la gestione flotta dei pullmans pubblici della mia citta cn tanto di GPS sui mezzi e di mappa in grafica vettoriale alla centrale operativa e di paline informative,
e x appunto incappai nello stesso problema. Ma poiche davi x scontato il calcolo della distanza tra 2 punti ( ed omettere che il tipo di coordinate è GPS e ce ne sn di vari tipi e sopratutto alcuni utlizzano figure geometriche diverse per giungere a definire il punto)
mi è piaciuto farti sputare il rospo.

mod da linoma informazioni inesatte

[ekontar]

ok, linoma, io il rospo l'ho sputato, spero tu sia contento ... però non ho capito bene se mi puoi suggerire qualcosa di meglio: se hai lavorato su un progetto simile al mio magari hai dovuto anche tu affrontare problemi simili.
Nei navigatori satellitari, ad esempio, quando ti informano che c'é un distributore di benzina nelle vicinanze credo facciano esattamente quello che devo fare io: "esplorano" in un raggio di x metri attorno al punto in cui sei se ci sono PDI da segnalare ... ma dubito che confrontino le distanze di TUTTI i PDI in memoria con la posizione attuale del veicolo !!

[linoma]

Io lavorai su semplici GPS che inviano tra le altre cs latitudine e la longitudine (nn ricordo neache gli altri dati). Poi c'era un OCX che svolgeva il grosso, se nn ricordo male della stessa azienda di google maps.
A suo tempo, col tuo stesso problema avrei fatto le stesse cs calcolarmi la distanza e poi trovarmi il + vicino, sinceramente nn vedo altre soluzioni. Naturalmente avranno un database organizato tra l'altro molto bene. E poi cn la potenza di calcolo che ce oggi.

(cmq io gioco)