Récupérer des enregistrements proches d'une coordonnée géopgraphique donnée

Logiciel & apps Programmation
1

Bonjour,

On va tout de suite expliquer plus en détail le problème parce que le titre n’est peut-être pas totalement clair.
J’ai une table (MySQL) de lieux avec des champs Latitude et Longitude et j’aimerai récupérer (SELECT * FROM lieux …) tous les enregistrements situés à moins de X mètres d’une position géographique P (coordonnées latitude-longitude).

Je présume qu’il existe une formule permettant de dire si un couple Lat/Lon est dans à plus ou moins X mètres qu’un autre couple Lat/Lon mais cela m’obligerait à parcourir tous les lieux de ma table et appliquer la formule pour savoir si le lieu est proche de P ou pas (pas terrible côté performance).

Toute la difficulté de l’élaboration de la clause WHERE repose sur le fait que la “surface de recherche” est un disque. Si j’optais pour une surface carré (centrée sur
P et de côtés parallèles aux latitudes et longitudes, ce qui est acceptable à notre latitude) ça serai beaucoup plus simple : je calcule les coordonnées de 3 des sommets A, B, C et je n’ai que deux comparaisons de réels à mettre dans ma clause (… WHERE lat BETWEEN sommetA_lat AND sommetC_lat AND lon BETWEEN sommetA_lon AND sommetB_lon).

Si je me borne à avoir une zone en disque je ne vois qu’une seule solution : faire le calcule de distance entre P et l’enregistrement courant dans la requête (… WHERE COMPUTE_DISTANCE(lat, lon, P.lat, P.lon) - la fonction COMPUTE_DISTANCE() calculant la distance entre les points). Cela dit, je ne trouve pas non plus que ça soit terrible (MySQL va devoir passer sur chaque enregistrement de toutes façons…).

Des idées ?

2

Peut import la solution, MySQL sera à coup sur obligé de faire un test sur chaque entrée de la base de donnée. Hormis la délimitation de zone, qui risquerais de nuir gravement à la précision du systeme, enfin de réduire le nombre de test à effectuer je vois pas…

Ou pour partir sur une idée de zone, ca serais de faire une sorte d'indexation. Ainsi tu testerais sur des zone grande, et qui serais délimité par des coordonnée (4 pour un carré) ca te ferais moins de teste pour affiné tes résultats. Et les tests points par points seulement les entrées correspondant à cette zone serais testé ( Gros probleme quand les points rechercher se trouve sur les limite entre 2 zone )
3

Tiens, tu n’as pas des fonctions géographiques de ce genre avec mySQL? (je sais qu’il y a ça avec pgSQL, mais mySQL, … à voir)

4

PyrO_70 > Oui c’est vrai que MySQL va obligatoirement itérer (et donc faire les calculs géographiques) sur chaque enregistrements.
Mais cela dit tu as raison : je peux très bien utiliser une zone temporaire carrée (englobant donc mon disque, zone de recherche réelle) pour exclure “rapidement” des lieux j’aurai deux clauses WHERE reliées par un AND : La première étant simple (simple comparaison de réels sans calcul) MySQL pourrait rapidement (vu qu’il n’effectuera pas l’autre clause) écarter les lieux trop loin.

WHERE
(coords dans carré centré sur P)
AND
(calcul de distance compliqué)

J’ai découvert que oui Sans-Nom : Spatial Extensions dans MySQL 5.1.
Y’a même un type de champ POLYGON permettant de stocker une zone (délimitée par des coordonnées Lat/Lon) et d’utiliser ensuite les fonctions spatiales dessus.

Et pour le calcul de distance en MySQL je suis tombé sur ce tuto/billet assez explicite : Géo-référence[/url] ([url=http://www.programmeur-analyste.com/index.php]Blog-notes d’un programmeur autonome).

Je pense que j’ai assez de matière pour travailler dessus ce week-end : Merci de vos conseils :slight_smile:

5

Bah tu vois :slight_smile:

Par contre mySQL 5.1… mais me semble que ça existe aussi en 5.0

6

Bon, j’ai fait ce qui suit :

SELECT 
	champ1, 
	champ2, 
	ACOS(
		SIN(RADIANS( ##REF_LATITUDE## ))
		*
		SIN(RADIANS(`lat`))
		+
		COS(RADIANS( ##REF_LATITUDE## ))
		*
		COS(RADIANS(`lat`))
		*
		COS(RADIANS( ##REF_LONGITUDE##  - `lon`))
	)
	*
	6378137 AS `distance` 
FROM 
	`lieux` 
HAVING 
	`distance` < 1000

Cela retourne tous les lieux situés à 1Km d’un point de coordonnées ##REF_LATITUDE## et ##REF_LONGITUDE## (en degrés décimal) et la distance en mètres (car j’ai utilisé la mesure du rayon de la Terre en mètres : 6378137)

La formule de calcul de distance provient de la page suivante : Distance Calculation - How to calculate the distance between two points on the Earth

Il ne reste plus qu’à optimiser cela en rajoutant une clause simple (i.e. facile à calculer) afin que MySQL puisse écarter rapidement les lieux trop loins… Quelqu’un sait ajouter x mètres à une longitude ?

7

Tu pourrais déjà commencer par stocker la lattitude en radians, fin d’une manière à éviter le calcul du sin / cos.

Tu peux même ajouter des trigger pour automatiser le changement des valeurs (genre: tu modifies la latitude, et ça te recalcule son cos & sin).

8

Ca c’est pas faux du tout :
Je peux stocker “SIN(RADIANS(lat))” et “COS(RADIANS(lat))” dans des champs à part.
(Et comme c’est hébergé chez Free : y’a MySQL 5 et ces triggers : cool :D)

9

J’ai fait calculer le SIN(RADIANS( ##REF_LATITUDE## )) par PHP (sin(deg2rad($ref_latitude))) : Mais je me demande si ça sert bien à quelque chose vu que MySQL devait sûrement mettre ce résultat en cache non ?

( Je peux également stocker la valeur de COS(RADIANS(lon)) et SIN(RADIANS(lon)) afin d’optimiser le COS(RADIANS( ##REF_LONGITUDE## - lon)) qu’on transforme en somme de produits de cos() et de sin() : comme quoi les maths servent bien :wink: )

10

A priori, pour les parties constantes il peut mettre en cache. Mais tu n’as aucune certitude, c’est mieux (je pense) de le faire côté PHP pour ce coup. Le seul souci étant la différence entre les types flottant mySQL & PHP (il peut y en avoir, oui).

Essaye un truc genre :

SET @@x := SIN(RADIANS( ##REF_LATITUDE## ));

Et de l’utiliser dans ta requête. C’est une possibilité aussi.

11

J’avais effectivement la même crainte mais les résultats que j’obtenais avec PHP étaient identiques à ceux de MySQL :slight_smile:
Cela dit, c’est vrai que je préfère utiliser une variable MySQL (d’ailleurs la syntaxe c’est SET @x := …; : un seul @)

J’ai également fait des comparaison de performances pour différentes parties du calcul sur la longitude :
D’abord :
radians(a-b) Versus radians(a)-radians(b) : la seconde est plus rapide de 19% (0.1490 sec contre 0.1781 sec)
Mais ensuite :
cos(radians(a)-radians(b)) Versus cos(radians(a))*cos(radians(b)) + sin(radians(a))*sin(radians(b)) : La première est plus rapide de 190% (0.2163 sec contre 0.6291 sec)
Même en optimisant la seconde forme (variable pour le calcul du radians de a et valeurs cos(radians(b)) et sin(radians(b)) pré-calculées (stockées dans la table) : je tombe avec peine à 0.4037 sec (toujours 86% trop lente, d’autant plus que la première forme gagne en vitesse en stockant également le radians de b dans la table)

(Benchmarks réalisés avec SELECT BENCHMARK(1000000, calcul);)