Calculer la distance entre les codes postaux... et les utilisateurs.

Je voudrais simplement créer une table zip_code_distances et pré-calculer les distances entre tous les codes postaux 42K aux États-Unis qui sont dans un rayon de 20-25 mile les uns des autres.

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;

Le fait d'inclure uniquement les codes postaux dans un rayon de 20-25 miles les uns des autres réduit le nombre de lignes que vous devez stocker dans la table de distance de 1,7 milliard (42K ^ 2) - 42K à un million de 4 beaucoup plus gérable.

J'ai téléchargé un fichier de données de code postal à partir du web qui contenait le longitudes et latitudes de tous les codes postaux officiels des États-Unis au format 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
...

J'ai écrit un programme C # rapide et sale pour lire le fichier et calculer les distances entre chaque code postal, mais seulement les codes postaux de sortie qui tombent dans un rayon de 25 miles:

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);
    }
}

Le fichier de Sortie Résultant se présente comme suit:

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
...

Je chargerais alors simplement ces données de distance dans ma table zip_code_distances en utilisant load data infile, puis l'utiliserais pour limiter l'espace de recherche de mon application.

Par exemple, si vous avez un utilisateur dont le code postal est 91210 et qu'il veut trouver des personnes qui se trouvent dans un rayon de 10 milles, vous pouvez maintenant simplement faire ce qui suit:

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'....

J'espère que cela aide

EDIT: rayon étendu à 100 miles, ce qui a augmenté le nombre de distances de code postal à 32,5 millions de lignes.

Vérification rapide des performances pour le code postal 91210 durée 0.009 secondes.

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

Vous pouvez raccourcir le calcul en supposant simplement une boîte au lieu d'un rayon circulaire. Ensuite, lors de la recherche, vous calculez simplement la limite inférieure/supérieure de lat/lon pour un point donné+"rayon", et tant que vous avez un index sur les colonnes lat/lon, vous pouvez retirer tous les enregistrements qui tombent dans la boîte assez facilement.

Vous pouvez diviser votre espace en régions de taille à peu près égale - par exemple, approximer la terre comme un buckyball ou un icosaèdre. Les régions pourraient même se chevaucher un peu, si c'est plus facile (par exemple, les rendre circulaires). Enregistrez dans quelle (S) région (s) se trouve chaque code postal. Ensuite, vous pouvez précalculer la distance maximale possible entre chaque paire de régions, qui a le même problème O(N^2) que le calcul de toutes les paires de codes postaux, mais pour les plus petits n .

Maintenant, pour un ZIP donné code, vous pouvez obtenir une liste de régions qui sont certainement dans votre plage donnée, et une liste de régions qui traversent la frontière. Pour le premier, il suffit de saisir tous les codes postaux. Pour ce dernier, percez dans chaque région frontalière et calculez par rapport aux codes postaux individuels.

C'est certainement plus complexe mathématiquement, et en particulier le nombre de régions devrait être choisi pour un bon équilibre entre la taille de la table et le temps passé à calculer à la volée, mais cela réduit la taille de la table précalculée par une bonne marge.

J'utiliserais la latitude et la longitude. Par exemple, si vous avez une latitude de 45 et une longitude de 45 et qu'on vous demande de trouver des correspondances à moins de 50 miles, vous pouvez le faire en déplaçant 50/69 ths en latitude et 50/69 ths en latitude (1 deg latitude ~ 69 miles). Sélectionnez les codes postaux avec des latitudes dans cette plage. Les Longitudes sont un peu différentes, car elles deviennent plus petites à mesure que vous vous rapprochez des pôles.

Mais à 45 deg, 1 longitude ~ 49 miles, de sorte que vous pouvez déplacer 50 / 49ths gauche dans latitude et 50 / 49ème droite en latitude, et sélectionnez tous les codes postaux de la latitude définie avec cette longitude. Cela vous donne tous les codes postaux dans un carré avec des longueurs d'une centaine de miles. Si vous voulez être vraiment précis, vous pouvez alors utiliser la formule Haversine que vous avez mentionnée pour éliminer les zips dans les coins de la boîte, pour vous donner une sphère.

Toutes les paires possibles de codes postaux ne seront pas utilisées. Je construirais zipdistance comme une table 'cache'. Pour chaque requête, calculez la distance pour cette paire et enregistrez-la dans le cache. Lorsqu'une requête pour une paire de distance arrive, regardez d'abord dans le cache, puis calculez s'il n'est pas disponible.

Je ne connais pas les subtilités des calculs de distance, donc je vérifierais aussi si l'informatique à la volée est moins chère que de regarder vers le haut (en tenant compte de la fréquence à laquelle vous devez le faire calculer).

Je sais que ce post est trop vieux, mais faire des recherches pour un client, j'ai trouvé des fonctionnalités utiles de L'API Google Maps et est si simple à mettre en œuvre, il vous suffit de passer à l'url les codes postaux d'origine et de destination, et il calcule la distance même avec le trafic, vous pouvez l'utiliser langue:

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

Suivant le lien, vous pouvez voir qu'il renvoie un json. Rappelez-vous que vous avez besoin d'une clé API pour l'utiliser sur votre propre hébergement.

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

J'ai le problème en cours d'exécution, et à peu près la réponse de tout le monde s'est habituée. Je pensais à cela en termes de l'ancienne solution au lieu de simplement " recommencer à zéro."Babtek obtient le signe de tête pour avoir déclaré en termes les plus simples.

Je vais ignorer le code parce que je vais fournir des références pour dériver les formules nécessaires, et il y a trop de choses à poster proprement ici.

1) considérons le Point a sur une sphère, représentée par la latitude et la longitude. calculez le Nord, le Sud, L'Est et L'Ouest bords D'une boîte de 2x miles à travers avec le Point A AU CENTRE .

2) Sélectionnez tous les points dans la zone de la table de Code Postal. Cela inclut une clause WHERE simple avec deux entre les instructions limitant par Lat et Long.

3) Utilisez la formule haversine pour déterminer la distance sphérique entre le Point A et chaque point B retourné à l'étape 2.

4) jeter tous les points B où la distance A - > B > X.

5) Sélectionnez les utilisateurs où le code postal est dans l'ensemble de points restant B.

C'est assez rapide pour > 100 miles. Le résultat le plus long était de ~ 0,014 secondes pour calculer la correspondance, et trivial pour exécuter l'instruction select.

Aussi, comme note de côté, il était nécessaire d'implémenter les mathématiques dans quelques fonctions et de les appeler en SQL. Une fois que j'ai passé une certaine distance, le nombre correspondant de codes postaux était trop grand pour être renvoyé à SQL et utilisé comme instruction IN, donc j'ai dû utiliser une table temporaire et joindre les codes postaux résultants à L'utilisateur sur le code postal colonne.

Je soupçonne que l'utilisation d'une table ZipDistance ne fournira pas un gain de performance à long terme. Le nombre de lignes devient vraiment grand. Si vous calculez la distance entre chaque zip et chaque autre code postal (éventuellement), le nombre de lignes résultant de 40 000 codes postaux serait ~ 1.6 B. Whoah!

Alternativement, je suis intéressé à utiliser le type de géographie intégré de SQL pour voir si cela rendra cela plus facile, mais les bons vieux types int / float ont bien servi pour cela échantillon.

Donc... liste finale des ressources en ligne que j'ai utilisées, pour votre référence facile:

1) différence maximale, Latitude et Longitude .

2) La Formule Haversine .

3) discussion longue mais complète de l'ensemble du processus , que j'ai trouvé à partir de googler des choses dans vos réponses.