Newsgroup: it.scienza.informatica
Titolo: Algoritmo distanze strade-cap-città

Scusate l'eventuale OT.
Sto realizzando un sito web che permetterà di trovare gli esercizi di
proprio interesse più vicini alla propria abitazione (o ad un luogo di
interesse).
Non so da dove cominciare a scrivere l'algoritmo.
Non so se il calcolo va fatto tra i cap, tra le latitudini/longitudini
o mediante calcolo della lunghezza dei tronchi stradali o ancora ...
Sono vermanente agli inizi, ma ho già spulciato un bel po' i gruppi di
google (in italiano) non trovando nulla che mi spiegasse le basi del
lavoro che voglio fare.
Eppure sono moltissimi i siti che lo fanno (ebay trova il venditore
più vicino al tuo cap, alla tua via... viamichelin calcola addirittura
il costo del carburante...)!!!
Il mio sito dovrà lavorare all'interno di una città (al limite
all'interno di una provincia) per ora, e non necessita di una
accuratezza maniacale...
Ringrazio tutti coloro sappiano indicarmi (almeno) le basi da cui
partire.
Ciao

 partire.
Se vuoi solo sapere la distanza in linea d'aria ti basta
un database degli esercizi con le coordinate esatte (forse rilevabili
con un gps ??) e poi ci sono diversi metodi per vedere cosa e' vicino
a cosa. Se sono pochi basta calcolare banalmente la distanza e
confrontarla con una soglia data. Altrimenti si possono prima
organizzare le coordinate degli esercizi commerciali in una struttura
dati che permetta di determinare piu' rapidamente quelli vicini ad un
dato punto (qualcosa tipo quadtree, non ricordo esattamente).
Se invece vuoi calcolare il percorso lungo delle strade,
la base da cui partire potrebbe essere un algoritmo di
shortest-path su grafi diretti (cammino minimo tra due punti).
L'algoritmo e' piuttosto semplice e lo puoi trovare facilmente sulla
rete cercando con google o su un libro di algoritmi (tipo il
Cormen/Leiserson/Rivest/Stein: Introduction to Algorithms).
Immagino che poi ci siano degli algoritmi piu' specifici che vengono
usati dai vari navigatori satellitari e siti web, anche in funzione
di quali dati posseggono.
Ma tu, in che formato hai le strade ? Perche' se non hai gia' un
qualche database con tutte le strade, gli incroci, magari i numeri
civici, etc.etc. non vedo come tu possa fare.
ciao,
g.

 a cosa.
Ok ci siamo... Oggi pensando e ripensando sono arrivato a questa
conclusione: Potrei prendere la mappa della città, inserirla tra gli
assi cartesiani e calcolare le coordinate del baricentro di ogni
singola area del cap. A questo punto il gioco è fatto. Inserendo un
cap, potrei stilare una classifica di vicinanza al cap inserito. La
ricerca non sarebbe precisa al 100%, ma per cercare un albergo o un
ristorante credo che il cap vada bene come tolleranza.
Tu che ne dici?
Grazie

 Tu che ne dici?
Dal punto di vista computazionale e implementativo sarebbe una
bazzecola, visto che i CAP non sono un milione e quindi puoi
banalmente scorrerli tutti e fare un calcolo di distanza per
ognuno di essi.
Per quanto riguarda il fatto che una ricerca basata sul cap possa
rispondere alle esigenze tue, non ne ho la piu' pallida idea,
perche' non so, neanche in generale, come siano fatte per forma
ed estensione le zone con lo stesso cap.
ciao,
g.

 Tu che ne dici?
Dico che dipende dalla precisione che intendi raggiungere e soprattutto 
dai dati iniziali che hai a disposizione.