Discussion :

[ram-0000]

Bonjour,

D'une part, j'ai un tableau de 3 colonnes organisé comme suit:

Code :

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

Nom de pays, Latitude moyenne, Longitude moyenne

D'autre part, j'ai une position géographique (position de la souris mais cela a peu d'importance):

Code :

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

Latitude exacte, Longitude exacte

Je cherche à trouver le nom du pays sur lequel je me trouve. L'algorithme que j'imagine est le suivant:

Code :

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

1
2
3
4
5
6
7
8
9
10
 
distance mini = +infini
pays trouve = "aucun"
Pout tous les pays
   distance courante = SQRT( (Latitude exacte - Latitude moyenne du pays)^2 + (Longitude exacte - Longitude moyenne du pays)^2 )
   si distance < distance mini
      distance mini = distance courante
      pays trouve = nom du pays
   fin si
Fin pour

Je me demandais s'il n'y avait pas plus rapide comme algo car je vais souvent faire des interrogations (1 ou 2 par secondes) et que mon tableau de pays contient environ 500 entrées.

[khayyam90]

Bien le bonjour,

Si tu n'as qu'une seule info par pays, ça ne suffira pas.
Dès que deux pays auront des taille différentes et que interrogeras un lieu près de leur frontière, l'algo se trompera et privilégiera le pays le plus petit.
Exemple simple, la France et la Luxembourg. La coordonnée moyenne de la Frane est bien en dessous de Paris et je te laisse imaginer où sera répertoriée Metz ou Thionville

Pour résoudre correctement un problème d'appartenance de coordonnées, il te faut définir des polygones de coordonnées pour chaque pays.

Cependant l'idée des coordonnées moyennes est pertinent pour orienter la recherche et obtenir un faible nombre de pays à tester. En triangulant par Delaunay ton ensemble de coordonnées moyennes, chaque interrogation de lieu te donnera un triangle et donc 3 pays à tester.

[khayyam90]

Et un cas pour lequel la triangulation est encore moins pertinente : pour les pays contenus dans d'autres pays (Afrique du Sud et Lesotho), là ça ne va plus du tout

[ram-0000]

Si tu n'as qu'une seule info par pays, ça ne suffira pas. Dès que deux pays auront des taille différentes et que interrogeras un lieu près de leur frontière, l'algo se trompera et privilégiera le pays le plus petit.
Exemple simple, la France et la Luxembourg. La coordonnée moyenne de la Frane est bien en dessous de Paris et je te laisse imaginer où sera répertoriée Metz ou Thionville .

Tout à fait d'accord

Et un cas pour lequel la triangulation est encore moins pertinente : pour les pays contenus dans d'autres pays (Afrique du Sud et Lesotho), là ça ne va plus du tout

Tout à fait d'accord aussi

Mais pour l'instant, je n'ai que ces données.

Avec mon algo, il y a des cas pour lesquels j'aurai des réponses "farfelues" mais je reviens à ma question, est ce qu'il y a mieux comme algo (plus rapide, plus efficient) ?

[pseudocode]

Avec mon algo, il y a des cas pour lesquels j'aurai des réponses "farfelues" mais je reviens à ma question, est ce qu'il y a mieux comme algo (plus rapide, plus efficient) ?

Si c'est possible dans ton cas, tu peux précalculer la carte des régions (point par point, ou par Voronoi). Ca te donne un tableau d'entier de taille Largeur x Hauteur de l'image, et chaque case du tableau te donne le n° du pays.

Sinon, tu peux partitioner l'espace pour réduire le nombre de positions à tester (BSP-tree, kd-tree, ...)

[souviron34]

impossible a determiner avec uniquement ces informations...

Meme pas une liste d'exclusion....

Il faut au minimum pour chaque pays lat min et max, long min et max...

[Zavonen]

On peut peut-être faire ainsi.
Une latitude se situe entre -90 et +90
Une longitude entre -180 et +180
Ainsi on a une bijection de la mappemonde sur le rectangle défini plus haut.
On considère les rectangles de type [la, la+1]*[lo,lo+1]
Certains de ces rectangles sont entièrement contenus dans un pays, d'autres non.
On considère ensuite la zone des rectangles non-inclus dans un seul pays, et on fait un recouvrement de ces rectangles par des rectangles correspondant à des variations de 1/10 de degré en latitude et en longitude.
A nouveau, certains des sous rectangles sont entièrement contenus dans un seul pays, et d'autres non.
On considère ensuite les sous-rectangles des précédents du second type correspondant à des variations de 1/100 ième de degré.
On s'arrête quand on estime que la précision est suffisante.
Ce travail préparatoire est assez long, mais quand il est fait l'algo est immédiat et très rapide.
Pour situer un point on regarde s'il est dans la première famille de rectangles, sinon dans la seconde etc...
Il restera une marge d'erreur d'autant plus faible qu'on est descendu loin dans les puissances de 10.

[deltree]

Bonjour à tous,
le découpage en zone est effectivement la meilleure méthode.

Mais je tenais juste à préciser 2 choses sur l'algo initial: (pour ajouter mon grain de sel )

Code :

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

1
2
3
4
5
6
7
8
9
10
 
distance mini = +infini
pays trouve = "aucun"
Pout tous les pays
   distance courante = SQRT( (Latitude exacte - Latitude moyenne du pays)^2 + (Longitude exacte - Longitude moyenne du pays)^2 )
   si distance < distance mini
      distance mini = distance courante
      pays trouve = nom du pays
   fin si
Fin pour

1. le calcul de distance sera très incorrect surtout proche des cercles polaires (ce sont des angles, et pas des distances, il faudrait un calcul trigo)
2. inutile de calculer la racine SQRT: pour calculer le minimum, autant directement comparer les carrés de distance: ce sera déjà moins couteux, et conduit au même résultat.

Pour une méthode encore plus approximative, on peut se contenter de dimension carrée:
distance=abs(delta latitude+delta longitude)

Mais j'ajouterais au minimum la taille du pays en plus des coordonnées du milieu: je serais assez déconcerté de sélectionner la Guyane, l'équateur, le pérou, la bolivie en plusieurs points du brésil très éloignés de ces plus petits pays.

Edit: au temps pour moi, l'équateur n'est pas frontalier avec le brésil. Cependant avec cet algo, il y a le risque de le sélectionner depuis le Brésil, alors qu'en incluant la taille, on limite le risque.

[ram-0000]

le découpage en zone est effectivement la meilleure méthode.

Je vais travailler sur ce concept pour voir.

1. le calcul de distance sera très incorrect surtout proche des cercles polaires (ce sont des angles, et pas des distances, il faudrait un calcul trigo)

D'accord avec cette remarque sachant tout de même que plus on est proche des pôles moins il y a de pays.

2. inutile de calculer la racine SQRT: pour calculer le minimum, autant directement comparer les carrés de distance: ce sera déjà moins couteux, et conduit au même résultat.

OK pour cette simplification

Pour une méthode encore plus approximative, on peut se contenter de dimension carrée: distance=abs(delta latitude+delta longitude)

Je vais voir si cette simplification n'introduit pas de trop grandes incertitudes.

Mais j'ajouterais au minimum la taille du pays en plus des coordonnées du milieu

Idée très intéressante, je vais voir aussi.

En tout cas, merci à tous pour vos remarques