recherche d'un périmètre à partir de la longitude et latitude

**sami_c** · 28/02/2007, 12h28

salut,
j'ai un fichier qui contient la liste des villes ainsi que la position géographique (longitude, latitude)
étant donnée une ville (long1, lat1), je voudrais chercher les villes appartenant à un rayon de 100km, pour limiter la recherche j'ai pensé à ceci :
je cherche tt les villes dont :
1 - longitude comprise entre long1-X et long1+X
2 - latitude comprise entre lat1-X et lat1+X
le pb c'est que je ne sais pas comment calculer la valeur de X, c-a-d le nombre de dégrées relatif à 100km !
est-ce que cette méthode est correcte ? quelle est la valeur de X ?

**pseudocode** · 28/02/2007, 14h59

Bon, remarque evidente, ton algo va te donner les villes qui sont dans le meme "carré", mais pas dans le meme "cercle". voila, c'est dit.

Pour le reste, ton X n'est pas une constante. En effet la longueur d'un degré de latitude/longitude dépend de la latitude a laquelle tu es

.

Pour la latitude, c'est (a peu pres) une constante: 1° = 114 km

Pour la longitude, ca varie beaucoup en fonction de la latitude:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
Longueur d'1° de longitude suivant la latitude:
 
º Lat 	longueur en Km
0	111
10	110
20	105
30	96
40	85
50	72
60	56
70	38
80	19
90	0

**souviron34** · 28/02/2007, 15h28

je dirais même plus

ça dépend aussi de la projection et des paramètres de la Terre utilisée (rayon, ellipticité, posiiton du centre).
(par exemple en général chaque pays a ses propres coordonnées du centre de la terre et sa propre ellipticité, afin d'être au plus proche de sa surface réelle)...

Pour calculer le nombre de kms relatifs à un nombre de degrés, comme mentionné, ça dépend des projections....et c'est compliqué...

Et grandement...

Voir http://www.galleryofmapprojections.com/

En France en général c'est la projection Lambert 2 qui est utilisée.

Une approximation (mais j'insiste sur "approximation"), et que à nos latitudes (entre 40 et 50 degrés) 1 degré de latitude fait 100 kms et un degré de longitude fait 110 kms.

Le calcul exact est très complexe. Si vous voulez des exemples de sources, recherchez "SIG projections" ou "GIS projections" sur Google....

Bon courage ...

**pseudocode** · 28/02/2007, 15h38

Envoyé par souviron34

Une approximation (mais j'insiste sur "approximation"), et que à nos latitudes (entre 40 et 50 degrés) 1 degré de latitude fait 100 kms et un degré de longitude fait 110 kms.

1° de longitude <-> 110 kms en France ?!??

**souviron34** · 28/02/2007, 15h59

Envoyé par pseudocode

1° de longitude <-> 110 kms en France ?!??

oui tu as raison c'était en sens inverse.. Environ 79 kms..

Voici un petit calculateur en ligne sami_c

http://www.csgnetwork.com/degreelenllavcalc.html

**sami_c** · 28/02/2007, 17h43

merci pour tous

en fait je ne cherche pas un calcul exact ! j'ai une grosse table SQL (environs 35'000 lignes) qui contient les long/lat, donc j'ai besoin d'un truc hyper rapide et tanpi si c'est pas précis
en fait je ne peux pas m'amuser à convertir soustraire la long/lat de tt les villes avec long1/lat1 et puis convertir en Km, ça sera trop lent comme traitement, c'est pour ça que j'ai besoin d'une approximation
NOTE : je travaille sur les villes de France

**souviron34** · 28/02/2007, 17h49

Envoyé par sami_c

merci pour tous

en fait je ne cherche pas un calcul exact ! j'ai une grosse table SQL (environs 35'000 lignes) qui contient les long/lat, donc j'ai besoin d'un truc hyper rapide et tanpi si c'est pas précis
en fait je ne peux pas m'amuser à convertir soustraire la long/lat de tt les villes avec long1/lat1 et puis convertir en Km, ça sera trop lent comme traitement, c'est pour ça que j'ai besoin d'une approximation
NOTE : je travaille sur les villes de France

tu programmes en quoi ??

Parce que en C moi j'ai fait un truc 2 fois pire (750 000 lignes, 6 conversions) en 8 secs...

**thewho** · 28/02/2007, 18h05

Bonjour,

Envoyé par souviron34

Une approximation (mais j'insiste sur "approximation"), et que à nos latitudes (entre 40 et 50 degrés) 1 degré de latitude fait 100 kms et un degré de longitude fait 110 kms.

On ne met jamais de s dans les symboles d'unité, même "au pluriel".

Je sais, c'est une erreur si courante qu'on pourrait croire que..., sans parler d'écrire KMS, presque aussi fréquent, et qui cumule l'erreur du s, au fait que ce sont des symboles, qui par conséquent doivent être écrits tels qu'ils sont définis, le passage en majuscule/minuscule changeant la signification du symbole.

C'était mon petit grain de sel de la journée

**pseudocode** · 28/02/2007, 19h32

Envoyé par thewho

Bonjour,
On ne met jamais de s dans les symboles d'unité, même "au pluriel".

Je sais, c'est une erreur si courante qu'on pourrait croire que..., sans parler d'écrire KMS, presque aussi fréquent, et qui cumule l'erreur du s, au fait que ce sont des symboles, qui par conséquent doivent être écrits tels qu'ils sont définis, le passage en majuscule/minuscule changeant la signification du symbole.

C'était mon petit grain de sel de la journée

**Graffito** · 01/03/2007, 00h05

Bonjour,

Parce que en C moi j'ai fait un truc 2 fois pire (750 000 lignes, 6 conversions) en 8 secs...

Je pourrais dire la même chose en Delphi : ce n'est pas le calcul de distance ou la conversion d'e cordonnées string du genre ddmmssNdddmmssE en lat/lon réelles qui consommeront beaucoup de temps CPU.

**pseudocode** · 01/03/2007, 09h51

Envoyé par Graffito

Bonjour,
Je pourrais dire la même chose en Delphi : ce n'est pas le calcul de distance ou la conversion d'e cordonnées string du genre ddmmssNdddmmssE en lat/lon réelles qui consommeront beaucoup de temps CPU.

Ca consomme encore moins si tu fais une procedure stockée en base... Meme plus besoin de transferer les données entre la Bdd et le programme. Tout tient dans une requete SQL:

Code :

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

1
2
/* villes a 100km autour de paris */
SELECT * From Villes Where distance(longitude,latitude,2.2,48.5) < 100

**souviron34** · 01/03/2007, 10h15

Envoyé par pseudocode

Ca consomme encore moins si tu fais une procedure stockée en base... Meme plus besoin de transferer les données entre la Bdd et le programme. Tout tient dans une requete SQL:

Code :

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

1
2
/* villes a 100km autour de paris */
SELECT * From Villes Where distance(longitude,latitude,2.2,48.5) < 100

ah oui ????

pt'ête bin que la requête fait qu'une ligne, mais le temps de calcul d'une SGBDR est infiniment plus long qu'un algo direct : ne serait-ce que chargement des talbles et suivrent les sauts de pointeurs....
Pour le même calcul (distance) tu rajoutes N*M appels à ce mécanisme....

**pseudocode** · 01/03/2007, 10h32

Envoyé par souviron34

ah oui ????

pt'ête bin que la requête fait qu'une ligne, mais le temps de calcul d'une SGBDR est infiniment plus long qu'un algo direct : ne serait-ce que chargement des talbles et suivrent les sauts de pointeurs....
Pour le même calcul (distance) tu rajoutes N*M appels à ce mécanisme....

Tout depend de ton SGBDR. C'est sur que si c'est Access, c'est mal barré.

Perso j'ai SQL Server 2005, et mes procedures stockées sont ecrites en C#, compilés en CIL et executées par le CLR. Donc la partie "calcul" a les memes perf qu'une appli .Net externe classique. La difference c'est que je n'ai pas de transferts de données a faire.

**souviron34** · 01/03/2007, 10h35

ben t'as fait pour 100 km.. Essaye 3000 .....

**pseudocode** · 01/03/2007, 10h53

Envoyé par souviron34

ben t'as fait pour 100 km.. Essaye 3000 .....

Bah c'est le meme temps.

Le Select parcours TOUJOURS toutes les lignes de la table et execute la procedure stockée pour chaque ligne. Que je mette 0, 100 ou 3000, le nombre d'appel de ma procedure stockée est le meme.

**wissem_dev** · 01/03/2007, 16h33

voici le code que j’ai utilisé, donc je suis besoin de voir comment faire pour obtenir un résulta correcte ou plus ou moins exacte

$late = 45.75;
$loge = 5.6;
$k= 0.1; //en degré
$la1 = $late-$k;
$la2 = $late+$k;
$lo1 = $loge-$k;
$lo2 = $loge+$k;

$query_espace = "SELECT cp FROM villes
WHERE (latitude BETWEEN '$la1' AND '$la2')
AND (longitude BETWEEN '$lo1' AND '$lo2')";

telle que cp:un code postal tapé par l'internaute

**pseudocode** · 01/03/2007, 17h35

Je suis pas tres doué en PHP...

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
 
// centre du cercle
$late = 45.75;
$loge = 5.6;
 
// rayon du cercle en km
$dist = 100;
 
// ecart permis sur la latitude en degre
$klate = $dist/114;
 
// ecart permis sur la latitude en degre
if ( abs($late)>=0  && abs($late)<10 ) $kloge = $dist/111;
if ( abs($late)>=10 && abs($late)<20 ) $kloge = $dist/110;
if ( abs($late)>=20 && abs($late)<30 ) $kloge = $dist/105;
if ( abs($late)>=30 && abs($late)<40 ) $kloge = $dist/96;
if ( abs($late)>=40 && abs($late)<50 ) $kloge = $dist/85;
if ( abs($late)>=50 && abs($late)<60 ) $kloge = $dist/72;
if ( abs($late)>=60 && abs($late)<70 ) $kloge = $dist/56;
if ( abs($late)>=70 && abs($late)<80 ) $kloge = $dist/38;
if ( abs($late)>=80 && abs($late)<90 ) $kloge = $dist/19;
if ( abs($late)>=90 ) $kloge = 180;
 
// bornes min/max des latitudes/latitudes
$la1 = $late-$klate;
$la2 = $late+$klate;
$lo1 = $loge-$kloge;
$lo2 = $loge+$kloge;
 
// Requete SQL
$query_espace = "SELECT cp FROM villes 
WHERE (latitude BETWEEN '$la1' AND '$la2') 
AND (longitude BETWEEN '$lo1' AND '$lo2')";

NB: cet algo devient tres FAUX pres des poles... Mais bon, y a pas bcp de villes par la-bas

**Graffito** · 01/03/2007, 17h49

NB: cet algo devient tres FAUX pres des poles... Mais bon, y a pas bcp de villes par la-bas

Après cette première sélection, on peut affiner avec la vraie distance.

**Melem** · 02/03/2007, 09h56

Etant donnés deux points M1 et M2 de la surface de la terre, ton problème se résume en faitau calcul de la longueur de l'arc M1M2 connaissant leur longitude (Long) et latitude (Lat) respectives. Pour ca y a plusieurs méthodes mais la plus simple je pense c'st celle-ci:

D'abord, nous faisons l'approxmation que la Terre est une sphère parfaite de centre O et de rayon R.
soit alpha l'angle que font les vecteurs OM1 et OM2. La longueur de l'arc M1M2 est R*alpha (alpha exprimé en radians). Tout ce qu'on sait de alpha cependant c'est cos(alpha) = ProduitScalaire(OM1, OM2)/(||OM1||.||OM2||). On fait alors un arccos pour trouve alpha.

N.B: Coordonnées sphériques -> Coordonnées cartésiennes)
Si on a M(R, Long, Lat), alors
OM(x, y, z) = (R.cos(Lat).cos(Long), R.cos(Lat).sin(Long), R.sin(Lat))
En fait ca dépend encore du repère ...

**sami_c** · 06/03/2007, 12h53

Envoyé par souviron34

tu programmes en quoi ??

Parce que en C moi j'ai fait un truc 2 fois pire (750 000 lignes, 6 conversions) en 8 secs...

j'utilise PHP, c'est un site web, donc 8 secondes c'est trop long !! en plus comme j'ai dis, j'ai pas besoin d'une bonne précision

recherche d'un périmètre à partir de la longitude et latitude

Algorithmes et structures de données

Discussions similaires

Partager

Partager