Calcola la distanza tra i codici di avviamento postale … E gli utenti.

Questa è più una domanda di sfida di qualcosa di cui ho urgente bisogno, quindi non passare tutto il giorno su questo ragazzi.

Ho costruito un sito di incontri (molto tempo passato) nel 2000 o giù di lì, e una delle sfide era calcolare la distanza tra gli utenti in modo da poter presentare le tue “partite” entro un raggio di X miglia. Per indicare il problema, dato il seguente schema del database (approssimativamente):

TABELLA UTENTE UserId UserName Codice postale

ZIPCODE TABLE ZipCode Latitude Longitude

Con USER e ZIPCODE uniti su USER.ZipCode = ZIPCODE.ZipCode.

Quale approccio prenderesti per rispondere alla seguente domanda: Quali altri utenti vivono in codici postali che si trovano entro X miglia dal codice postale di un determinato utente.

Abbiamo utilizzato i dati del censimento del 2000 , che hanno tabelle per i codici postali e la loro approssimativa latitudine e longitudine.

Abbiamo anche usato la formula di Haversine per calcolare le distanze tra due punti qualsiasi su una sfera … matematica davvero semplice.

La domanda, almeno per noi, essendo gli studenti universitari di 19 anni che eravamo, è diventata davvero come calcolare e / o archiviare in modo efficiente le distanze da tutti i membri a tutti gli altri membri. Un approccio (quello che abbiamo usato) sarebbe quello di importare tutti i dati e calcolare la distanza da ogni codice postale a ogni altro codice postale. Quindi devi memorizzare e indicizzare i risultati. Qualcosa di simile a:

SELECT User.UserId FROM ZipCode AS MyZipCode INNER JOIN ZipDistance ON MyZipCode.ZipCode = ZipDistance.MyZipCode INNER JOIN ZipCode AS TheirZipCode ON ZipDistance.OtherZipCode = TheirZipCode.ZipCode INNER JOIN User AS User ON TheirZipCode.ZipCode = User.ZipCode WHERE ( MyZipCode.ZipCode = 75044 ) AND ( ZipDistance.Distance < 50 ) 

Il problema, ovviamente, è che la tabella ZipDistance avrà un sacco di righe al suo interno. Non è completamente inattuabile, ma è davvero grande. Inoltre richiede un pre-lavoro completo sull’intero set di dati, che non è nemmeno ingestibile, ma non necessariamente desiderabile.

Ad ogni modo, mi stavo chiedendo quale approccio alcuni di voi guru potrebbero assumere in questo modo. Inoltre, penso che questo sia un problema comune che i programmatori devono affrontare di volta in volta, specialmente se si considerano problemi che sono algoritmicamente simili. Sono interessato a una soluzione completa che includa almeno gli HINTS su tutti i pezzi per farlo in modo molto veloce e in modo efficiente. Grazie!

Ok, per cominciare, non hai davvero bisogno di usare la formula di Haversine qui. Per le grandi distanze in cui una formula meno accurata produce un errore più grande, ai tuoi utenti non interessa se la partita è più o meno poche miglia, e per distanze più ravvicinate, l’errore è molto piccolo. Ci sono più facili (per calcolare) le formule elencate nell’articolo Wikipedia di distanza geografica .

Dal momento che i codici postali non hanno nulla a che vedere con intervalli regolari, qualsiasi processo che li divida equamente risentirà molto delle aree in cui sono raggruppati strettamente (la costa orientale vicino a Washington è un buon esempio). Se vuoi un confronto visivo, controlla http://benfry.com/zipdecode e confronta il prefisso 89 con 07.

Un modo molto migliore per gestire l’indicizzazione di questo spazio è usare una struttura di dati come un Quadtree o un R-tree . Questa struttura consente di eseguire ricerche spaziali e a distanza su dati che non sono equamente distribuiti.

Ecco come appare un Quadtree:

quadtree

Per effettuare una ricerca su di essa, si esegue il drill down di ciascuna cella più grande utilizzando l’indice delle celle più piccole che si trovano al suo interno. Wikipedia lo spiega più a fondo.

Naturalmente, poiché questa è una cosa abbastanza comune da fare, qualcun altro ha già fatto la parte difficile per te. Dato che non hai specificato quale database stai usando, l’estensione PostgreSQL PostGIS servirà come esempio. PostGIS include la capacità di creare indici spaziali R-tree che consentono di eseguire query spaziali efficienti.

Una volta importati i dati e creato l’indice spaziale, la ricerca della distanza è una query come:

 SELECT zip FROM zipcode WHERE geom && expand(transform(PointFromText('POINT(-116.768347 33.911404)', 4269),32661), 16093) AND distance( transform(PointFromText('POINT(-116.768347 33.911404)', 4269),32661), geom) < 16093 

Ti farò lavorare attraverso il resto del tutorial da solo.

Ecco alcuni altri riferimenti per iniziare.

Creo semplicemente una tabella zip_code_distances e pre-computo le distanze tra tutti i codici postali 42K negli Stati Uniti che si trovano entro un raggio di 20-25 miglia l’uno dall’altro.

 create table zip_code_distances ( from_zip_code mediumint not null, to_zip_code mediumint not null, distance decimal(6,2) default 0.0, primary key (from_zip_code, to_zip_code), key (to_zip_code) ) engine=innodb; 

Solo l’inclusione di codici di avviamento postale entro un raggio di 20-25 miglia l’una dall’altra riduce il numero di righe che è necessario memorizzare nella tabella delle distanze da un massimo di 1,7 miliardi (42 K ^ 2) – 42 K a un valore di circa 4 milioni molto più gestibile.

Ho scaricato un file di dati zipcode dal web che conteneva le longitudini e le latitudini di tutti i codici postali ufficiali degli Stati Uniti in formato csv:

 "00601","Adjuntas","Adjuntas","Puerto Rico","PR","787","Atlantic", 18.166, -66.7236 "00602","Aguada","Aguada","Puerto Rico","PR","787","Atlantic", 18.383, -67.1866 ... "91210","Glendale","Los Angeles","California","CA","818","Pacific", 34.1419, -118.261 "91214","La Crescenta","Los Angeles","California","CA","818","Pacific", 34.2325, -118.246 "91221","Glendale","Los Angeles","California","CA","818","Pacific", 34.1653, -118.289 ... 

Ho scritto un programma C # veloce e sporco per leggere il file e calcolare le distanze tra ogni codice di avviamento postale ma solo i codici di avviamento in uscita che rientrano in un raggio di 25 miglia:

 sw = new StreamWriter(path); foreach (ZipCode fromZip in zips){ foreach (ZipCode toZip in zips) { if (toZip.ZipArea == fromZip.ZipArea) continue; double dist = ZipCode.GetDistance(fromZip, toZip); if (dist > 25) continue; string s = string.Format("{0}|{1}|{2}", fromZip.ZipArea, toZip.ZipArea, dist); sw.WriteLine(s); } } 

Il file di output risultante ha il seguente aspetto:

 from_zip_code|to_zip_code|distance ... 00601|00606|16.7042215574185 00601|00611|9.70353520976393 00601|00612|21.0815707704904 00601|00613|21.1780461311929 00601|00614|20.101431539283 ... 91210|90001|11.6815708119899 91210|90002|13.3915723402714 91210|90003|12.371251171873 91210|90004|5.26634939906721 91210|90005|6.56649623829871 ... 

Vorrei quindi caricare questi dati di distanza nella mia tabella zip_code_distances usando load data infile e quindi usarlo per limitare lo spazio di ricerca della mia applicazione.

Ad esempio se hai un utente il cui codice postale è 91210 e vogliono trovare persone che si trovano entro un raggio di 10 miglia da loro, ora puoi semplicemente fare quanto segue:

 select p.* from people p inner join ( select to_zip_code from zip_code_distances where from_zip_code = 91210 and distance <= 10 ) search on p.zip_code = search.to_zip_code where p.gender = 'F'.... 

Spero che questo ti aiuti

EDIT: raggio esteso a 100 miglia che ha aumentato il numero di distanze zipcode a 32,5 milioni di righe.

controllo rapido delle prestazioni per il runtime zipcode 91210 0,009 secondi.

 select count(*) from zip_code_distances count(*) ======== 32589820 select to_zip_code from zip_code_distances where from_zip_code = 91210 and distance <= 10; 0:00:00.009: Query OK 

È ansible creare una scorciatoia del calcolo assumendo semplicemente una casella invece di un raggio circolare. Quindi, durante la ricerca, calcoli semplicemente il limite inferiore / superiore di lat / lon per un dato punto + “raggio”, e finché hai un indice sulle colonne lat / lon puoi tirare indietro tutti i record che rientrano nella casella abbastanza facilmente .

Potresti dividere il tuo spazio in regioni di dimensioni approssimativamente uguali, ad esempio approssimando la terra come un buckyball o un icosaedro. Le regioni potrebbero anche sovrapporsi un po ‘, se è più facile (es. Renderle circolari). Registra in quale regione (o) è inserito ciascun codice. Quindi puoi precalcolare la distanza massima ansible tra ogni coppia di regioni, che ha lo stesso problema di O (n ^ 2) come il calcolo di tutte le coppie di codici ZIP, ma per il più piccolo n .

Ora, per qualsiasi dato codice postale, è ansible ottenere un elenco di regioni che sono sicuramente all’interno del range dato e un elenco di regioni che attraversano il confine. Per il primo, basta prendere tutti i codici postali. Per questi ultimi, esegui il drill-down in ogni area di confine e calcola i singoli codici postali.

È certamente più complesso dal punto di vista matematico, e in particolare il numero di regioni dovrebbe essere scelto per un buon bilanciamento tra la dimensione della tabella e il tempo impiegato per calcolare al volo, ma riduce la dimensione della tabella precalcasting da una buona margine.

Userei latitudine e longitudine. Ad esempio, se hai una latitudine di 45 e una longitudine di 45 e ti è stato chiesto di trovare corrispondenze entro 50 miglia, allora potresti farlo spostando 50/69 ths in latitudine e 50/69 ths in latitude (1 gradi latitudine ~ 69 miglia). Seleziona i codici postali con latitudini in questo intervallo. Le lunghezze sono un po ‘diverse, perché diventano più piccole man mano che ti avvicini ai poli.

Ma a 45 gradi, 1 longitudine ~ 49 miglia, in modo da poter spostare 50/49 ° a sinistra in latitudine e 50/49 ° a destra in latitudine e selezionare tutti i codici di avviamento postale dalla latitudine impostata con questa longitudine. Questo ti dà tutti i codici di avviamento postale in un quadrato con lunghezze di cento miglia. Se volessi essere molto preciso, potresti usare la strega formula di Haversine che hai menzionato per togliere le cerniere agli angoli della scatola, per darti una sfera.

Non tutti i possibili codici postali verranno utilizzati. Vorrei creare zipdistance come tabella ‘cache’. Per ogni richiesta, calcola la distanza per quella coppia e salvala nella cache. Quando arriva una richiesta di una coppia di distanza, guarda prima nella cache, quindi calcola se non è disponibile.

Non conosco la complessità dei calcoli della distanza, quindi verificherei anche se il calcolo al volo è più economico rispetto al cercare (considerando anche quanto spesso devi calcolare).

So che questo post è TROPPO vecchio, ma facendo qualche ricerca per un cliente ho trovato alcune utili funzionalità dell’API di Google Maps ed è così semplice da implementare, devi solo passare all’URL i codici di origine e destinazione ZIP, e calcola la distanza anche con il traffico, puoi usarlo con qualsiasi lingua:

 origins = 90210 destinations = 93030 mode = driving 

http://maps.googleapis.com/maps/api/distancematrix/json?origins=90210&destinations=93030&mode=driving&language=en-EN&sensor=false%22

seguendo il link puoi vedere che restituisce un json. Ricorda che hai bisogno di una chiave API per usarla sul tuo hosting.

fonte: http://stanhub.com/find-distance-between-two-postcodes-zipcodes-driving-time-in-current-traffic-using-google-maps-api/

Ho avuto un grosso problema e ho praticamente usato la risposta di tutti. Stavo pensando a questo in termini di vecchia soluzione invece di “ricominciare”. Babtek fa il cenno affermando in termini più semplici.

Salterò il codice perché fornirò i riferimenti per ricavare le formule necessarie e c’è troppo da pubblicare in modo pulito qui.

1) Considerare il punto A su una sfera, rappresentato da latitudine e longitudine. Calcola i bordi nord, sud, est e ovest di una casella 2X miglia trasversali con il punto A al centro .

2) Seleziona tutto il punto all’interno della casella dalla tabella ZipCode. Ciò include una semplice clausola WHERE con due istruzioni Between che limitano Lat e Long.

3) Utilizzare la formula di haversine per determinare la distanza sferica tra il punto A e ogni punto B restituito nel passaggio 2.

4) Scartare tutti i punti B in cui la distanza A -> B> X.

5) Selezionare gli utenti in cui ZipCode si trova nel rimanente gruppo di punti B.

Questo è abbastanza veloce per> 100 miglia. Il risultato più lungo è stato ~ 0.014 secondi per calcolare la corrispondenza, e banale per eseguire l’istruzione select.

Inoltre, come nota a margine, è stato necessario implementare la matematica in un paio di funzioni e chiamarle in SQL. Una volta superato una certa distanza, il numero corrispondente di ZipCode era troppo grande per passare a SQL e usarlo come istruzione IN, quindi ho dovuto usare una tabella temporanea e unire i codici Zip risultanti all’utente nella colonna ZipCode.

Sospetto che l’utilizzo di una tabella ZipDistance non fornirà un guadagno di prestazioni a lungo termine. Il numero di file diventa davvero grande. Se si calcola la distanza da ogni zip a ogni altro codice postale (eventualmente), il numero di righe risultante da 40.000 codici postali sarebbe ~ 1.6B. Whoah!

In alternativa, sono interessato all’utilizzo del tipo di geografia integrata di SQL per vedere se ciò renderà più semplice questo, ma i buoni vecchi tipi int / float sono ben serviti per questo esempio.

Quindi … l’elenco finale delle risorse online che ho usato, per il tuo facile riferimento:

1) Differenza massima, latitudine e longitudine .

2) La formula di Haversine .

3) Discussione lunga ma completa di tutto il processo , che ho trovato da Google nelle tue risposte.