Requete SQL compliquée

[tanglung]

Bonjour,

J'ai une BDD MySQL qui contient une liste de points. Elle est organisée ainsi:

Titre | x | y

Ou titre est le titre du point sur ma carte, et x, y ses coordonnées

J'aimerai recupérer tous les points de la BDD en la triant par proximité d'un point A de coordonées X et Y.

SELECT * FROM points ORDER BY ????


Quelqun aurait il une idée ??

Un grand merci !

PS : on peut y arriver en calculant les distances avec pythagor, en chargant tous les points dans un tableau,puis en le triant par distance, mais ca oblige a charger tous les points de la BDD et y en a plus de 10 000 donc intraitable pour le serveur

[arnaudmn]

Que cherche tu réellements a faire ? A tu un interêt a récupérer 10000 lignes dans ta requete ?
Tu peux déja trier en prenant juste ce qui est proche de A (en faisant un Abs(X-Xa)<=10), idem sur Y). Puis tu faits une boucle, consrtuit un tableau avec pythagor et fait le tri en mémoire.
En sachant que, si tu fais le calcul directement dans la requete, tu vas quand même obligé le serveur a travailler sur 10000 points, ce qui revient quasiment au même qu'en charger 10000 et faire le calcul a coté de la requete.

[skippyzrnr]

bien que je pense que le traitement sois assez lourd quand meme tu as surement interet à utiliser les fonctions mathématiques natives de mySQL : http://dev.mysql.com/doc/refman/5.0/fr/mathematical-functions.html

Et pourquoi pas créer une table des distances entre chaque points ? comme ca tu fais un traitement enorme c'est vrai , mais une fois seulement

[khantic]

Si tes points sont des coordonnées GPS (angle en degré), c'est pas pareil que si tes points sont en pixel (sur une carte).

Dans le second cas, il faut utiliser pythagore, et ça fonctionne très bien, dans le premier, c'est bien plus compliqué, je sais qu'il y a des arccosinus et des arcsinus dans une expression à rallonge.

Bon courage !

[jcaron]

J'ai une BDD MySQL qui contient une liste de points. Elle est organisée ainsi:

Titre | x | y

Ou titre est le titre du point sur ma carte, et x, y ses coordonnées

J'aimerai recupérer tous les points de la BDD en la triant par proximité d'un point A de coordonées X et Y.

SELECT * FROM points ORDER BY ????
[...]
PS : on peut y arriver en calculant les distances avec pythagor, en chargant tous les points dans un tableau,puis en le triant par distance, mais ca oblige a charger tous les points de la BDD et y en a plus de 10 000 donc intraitable pour le serveur

Effectivement, la méthode "brutale" c'est:

SELECT * FROM points ORDER BY power(x-?,2)+power(y-?,2) LIMIT 10

mais ça l'oblige à regarder tous les points un par un, donc avec un nombre important de points et/ou un nombre important de requêtes ce n'est pas très jouable. Et comme évoqué par khantic, suivant le type de coordonnées (et éventuellement l'échelle, on n'a pas les mêmes problèmes à l'échelle de la France qu'à l'échelle du monde, par exemple), le calcul peut devenir plus compliqué.

Si les points autour desquels tu cherches d'autres points sont une liste finie, tu peux effectivement appliquer la méthode proposée par skippyzrnr.

Maintenant si comme je le pense tu veux pouvoir trouver ça à partir de n'importe quel point entré par l'utilisateur, il faut être un peu plus subtil. Une solution applicable consiste à découper ton territoire en une grille dont tu numérotes les cases (par exemple du découpes en 10 x 10, et chaque chaque a pour numéro ligne * 10 + colonne). Tu as un calcul simple pour obtenir la case à partir des coordonnées (si tes coordonnées au départ sont dans une grille 1000 x 1000, ce serait bêtement int(y/100)*10 + int(x/100).

Dans ta table tu rajoutes un index sur ce numéro de case (je ne sais pas si MySQL gère les index sur des expressions, si ce n'est pas le cas tu ajoutes bêtement une colonne supplémentaire à ta table avec le numéro de la case, et un index sur cette colonne).

Quand tu veux trouver les points proches de ton point de référence (appelons-le "a"), tu trouves la case dans laquelle se trouve a (et éventuellement les cases adjacentes, pour le cas où a serait "au bord" de la case -- si tu veux faire top intelligent tu vas choisir les cases adjacentes en fonction de la position de a dans sa case, genre si a est dans la moitié gauche de la case, pas la peine d'aller voir la case qui est à droite), et tu utilises l'index pour limiter la recherche aux points qui sont dans ces cases, et tu utilises le tri évoqué plus haut pour trouver les points réellement les plus proches.

Donc ça donnerait:

SELECT * FROM points WHERE case IN (?,?,?,?) ORDER BY power(x-?,2)+power(y-?,2) LIMIT 10

Evidemment ça veut dire qu'implicitement tu limites la distance maximale des points trouvés à grosso-modo la taille d'une case, mais dans ce cas rien ne t'empêche de prendre plus de cases autour de ton point.

Si jamais tes points ont une répartition pas très homogène (genre 9000 points dans une case et le reste dans les autres) tu peux commencer par réduire la taille de tes cases (avec l'inconvénient ci-dessus), sinon tu peux faire plusieurs "niveaux" de cases.

Note qu'avec d'autres BDD comme postgresql tu peux faire des index GIST sur les points qui permettent probablement de simplifier un certain nombre de choses, mais même avec un mySQL on doit pouvoir arriver à quelque chose.

Bon courage!

Jacques.