Discussion :

[_cheval_]

Bonjour à tous,
après moult recherche, je ne trouve pas mon bonheur.

je suis à la recherche d'un algorithme, me permettant de retrouver un code postal en fonction d'une latitude et longitude.

Je m'explique, je possède un BD avec 500000 codes postaux, chacun d'entre eux possède une latitude et une longitude.
Je reçois depuis un Smartphone les coordonnées de la personnes utilisant mon application avec la latitude et longitude exacte.

Je cherche donc un algorithme qui me permette de retrouver le code postal le plus proche de ma coordonnée.

Attention, je connais la formule (Et je l'utilise dans d'autre cas) permettant d'obtenir la distance entre 2 points.
Mais je ne souhaite pas calculer la distance entre mes 500000 codes postaux et renvoyer la plus petite (Bcp trop long).

Je cherche vraiment un algo, me donnant parmi 500000 pts, lequel est le plus proche (Même pas besoin de la distance exacte).

Merci d'avance à qui saura m'aider.
Jérémie

[pseudocode]

Bonsoir,

il s'agit d'un problème de type NNS (Nearest neighbor search) pour lequel il existe différentes approches bien connues.

A la vue de l'énoncé, je pense qu'un simple partitionnement de l'espace 2d (en carré, ou mieux en hexagone) devrait permettre de limiter grandement la liste des voisins. Un fois cette courte liste obtenue, on calcule toutes les distances en on garde la plus faible.

[_cheval_]

Ok parfait je lirais la doc que tu m'as fourni, trop difficile à cette heure ci.

Par contre, n'étant pas mathématicien, si tu as un exemple de partitionnement en carré je suis preneur.
Peut être est ce expliqué dans ton lien que je lirais demain.

Quoiqu'il en soit, merci de m'avoir mit sur une piste.

[Nebulix]

Si ton fichier de villes est trié en longitude, il est très rapide d'y sélectionner les villes "pas trop loin en longitude" ( O(ln(N))).
Dans ce sous-ensemble de 1000 villes (estimé au pif), tu peux sélectionner celles qui ne sont "pas trop loin en latitude".
Dans ce petit nombre (10 ?) tu peux calculer ce que tu veux...

[_cheval_]

Bon je tenais à poster un premier brouillon que je viens de terminer à l'instant en utilisant la technique du carré.

Pour info la table cod_pos :
cod_pos, lat (en degré),lon (en degré).

Ca marche tràs bien, ce n'est absolument pas optimisé, on travaille dessus. Je posterais ensuite le résultat de l'optimisation.

Si certains veulent s'amuser à optimiser tout ca, je suis preneur.

Sinon, pour les lat, et long je suis Francais expatrié au Canada, et l'algo fonctionne très bien, sauf au fin fond du Nord du Canada, ou il y a un code postal pour 200Km!!!

Enfin bon merci à tous.

Je mettrais ma version finale d'ici peu.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
<?php
header('Content-type: text/html; charset=utf-8');
require("config.php");
require("configNA.php");
 
 
 function getDistance($ori_lat,$ori_lon,$des_lat,$des_lon) {
        $a = sin(($des_lat - $ori_lat)/2) * sin(($des_lat - $ori_lat)/2) + cos(($ori_lat)) * cos(($des_lat)) * sin(($des_lon - $ori_lon)/2) * sin(($des_lon - $ori_lon)/2);
        $c = 2 * atan2(sqrt($a), sqrt(1 - $a));
        return number_format((6371 * $c), 10); //6371 = rayon de la terre
    }
 
 
 
$lat=45.544012;
$lon=-73.552372;
 
 
$lat=45.44912;
$lon=-73.308721;
 
 
$lat=45.517557;
$lon=-73.515651;
 
$lonPlus=$lon+1;
$lonMoins=$lon-1;
$latPlus=$lat+1;
$latMoins=$lat-1;
$daoBase=new DaoBase();
$cod_pos='';
$tabZipCoord=array();
 
//lon+1
$psql='select cod_pos,lat,lon from cod_pos where lon<'.$lonPlus.' and lon>'.$lon.' order by lon asc limit 0,500';
$daoBase->execute($psql,'read');
echo '<h1>'.$psql.'</h1>';
 
if ($daoBase->numRows()<=0)
{
    echo 'No ZipCod found ['.$daoBase->numRows().']';
    die;
}
 
 
echo $daoBase->numRows().' zip_cod found<br />';
while($row = $daoBase->getArray()) {
   // print_r($row);
   // echo '<br />';
    $cod_pos.='"'.$row['cod_pos'].'",';
}
$cod_pos = substr($cod_pos,0, -1);
 
 
 
 
//lon +1
$psql='select cod_pos,lat,lon from cod_pos where lon>'.$lonMoins.' and lon<'.$lon.' order by lon desc limit 0,500';
$daoBase->execute($psql,'read');
echo '<h1>'.$psql.'</h1>';
if ($daoBase->numRows()<=0)
{
    echo 'No ZipCod found ['.$daoBase->numRows().']';
    die;
}
 
 
echo $daoBase->numRows().' zip_cod found<br />';
while($row = $daoBase->getArray()) {
   // print_r($row);
   // echo '<br />';
    $cod_pos.='"'.$row['cod_pos'].'",';
}
$cod_pos = substr($cod_pos,0, -1);
 
echo $cod_pos;
 
//lat +1 
$psql='select cod_pos,lat,lon from cod_pos where lat<'.$latPlus.' and lat>'.$lat.' and cod_pos in ('.$cod_pos.') order by lat asc limit 0,10';
$daoBase->execute($psql,'read');
echo '<h1>'.$psql.'</h1>';
if ($daoBase->numRows()<=0)
{
    echo 'No ZipCod found ['.$daoBase->numRows().']';
    die;
}
 
echo $daoBase->numRows().' zip_cod found<br />';
$i=0;
while($row = $daoBase->getArray()) {
    print_r($row);
    echo '<br />';
    $tabZipCoord[$i]['cod_pos']=$row['cod_pos'];
    $tabZipCoord[$i]['lon_rad']=3.141592653 * ($row['lon']/180);
    $tabZipCoord[$i]['lat_rad']=3.141592653 * ($row['lat']/180);
    $i++;
}
 
//lat -1
$psql='select cod_pos,lat,lon from cod_pos where lat>'.$latMoins.' and lat<'.$lat.' and cod_pos in ('.$cod_pos.') order by lat desc limit 0,10';
$daoBase->execute($psql,'read');
echo '<h1>'.$psql.'</h1>';
if ($daoBase->numRows()<=0)
{
    echo 'No ZipCod found ['.$daoBase->numRows().']';
    die;
}
 
 
echo $daoBase->numRows().' zip_cod found<br />';
$cod_pos='';
while($row = $daoBase->getArray()) {
    print_r($row);
    echo '<br />';
    $tabZipCoord[$i]['cod_pos']=$row['cod_pos'];
    $tabZipCoord[$i]['lon_rad']=3.141592653 * ($row['lon']/180);
    $tabZipCoord[$i]['lat_rad']=3.141592653 * ($row['lat']/180);
    $i++;
}
 
 
 
 
 
echo '<h1>Final Tab</h1>';
//Get good cod_pos
print_r($tabZipCoord);
$lon_rad=3.141592653 * ($lon/180);
$lat_rad=3.141592653 * ($lat/180);
 
$tabFinal=array();
for ($j=0;$j<$i;$j++){
    $tabFinal[$tabZipCoord[$j]['cod_pos']]=getDistance($lat_rad, $lon_rad, $tabZipCoord[$j]['lat_rad'], $tabZipCoord[$j]['lon_rad']);
}
 
echo '<h1>Tableaux de distances</h1>';
print_r($tabFinal);
$tabSave=array_flip($tabFinal);
 
echo '<h1>Tableaux de distances TRIE</h1>';
sort($tabFinal,SORT_NUMERIC);
print_r($tabFinal);
print_r($tabSave);
 
 
echo '<h1> Code postal final : '.$tabSave[$tabFinal[0]].'</h1>';
 
 
?>

[pseudocode]

Sinon, pour les lat, et long je suis Francais expatrié au Canada, et l'algo fonctionne très bien, sauf au fin fond du Nord du Canada, ou il y a un code postal pour 200Km!!!

S'il n'y a pas de candidats dans le carré que tu as choisi, recommence en prenant un carré plus gros.