[MySQL 5] Selection spéciale selon les coordonnées d'une liste de points

Bonjour,

Je reviens vers vous cette fois pour soumettre le cas d'une situation très tordue qui me donne du fil à retordre depuis pas mal de temps.

J'ai pour projet de créer une table dans laquelle seront inscrit des objets primitifs cartographiques (lignes, zones, points) tous définis par une liste de points (entres autres) se présentant sous la forme suivante : x1,y1;x2,y2;x3,y3... ou x représente une latitude et y la longitude.

Maintenant, et ce sera le mode le plus courant de sélection sur la table, j'aimerai sortir uniquement les objets ayant au moins un point dans un rectangle défini par Xmin, Xmax, Ymin et YMax.
Le problème est qu'il va donc falloir faire des comparaisons sur les coordonnées des points de la liste de chaque objet pour déterminer si l'enregistrement correspond à la contrainte ou non et que la liste se présente de la manière donnée ci-dessus. Pas pratique! :calim2:

Les mauvaises nouvelles sont au nombre de deux :
1 - Je ne peux pas télécharger la liste de tous mes objets pour les tester sur serveur : avec quelques centaines de milliers d'enregistrements, on fait sauter la banque.
2 - Je ne peux pas décider de créer un table avec des points d'un coté et une jointure avec une autre table stockant les objets (sur un champ contenant les ID des points contenus dans l'objet).
Pour les bonnes, c'est suivant vos réponses :)

Comment feriez-vous donc?
Merci par avance pour vos réponses et votre perspicacité...

Saluton,
Si je comprends bien, il y aurait 2 tables : figures{id,forme} et points{id_figure,X,Y}
et il faudrait déterminer dans figures celles qui ont au moins un point compris dans le rectangle dont tu ne fournis que les coordonnées du coin bas gauche et coin haut droit.

Code:

---

1 2 3 4 5 6 7

SELECT id, forme FROM figures f WHERE EXISTS(SELECT * FROM points WHERE id_figure= f.id AND X BETWEEN Xmin AND Xmax AND Y BETWEEN Ymin AND Ymax)

---

A la réflexion, c'est beaucoup plus complexe que ça et, selon moi, pas réalisable en SQL.

Bonsoir Maljuna Kris :)

Citation:

---

Envoyé par Maljuna Kris

Saluton,
Si je comprends bien, il y aurait 2 tables : figures{id,forme} et points{id_figure,X,Y}

---

Non, il n'y a qu'une seule table avec un champ contenant une liste de points sous la forme d'une chaine comme celle-ci : x1,y2;x2,y2;x3,y3... ou x,y sont des paires longitude,latitude.

Il faudrait que je sache si, dans cette liste de point, au moins une paire x,y rentre dans une zone définie par un rectangle Xmin, Xmax, Ymin et Ymax pour sortir ou non l'enregistrement concerné dans les résultats de la requête.

Citation:

---

A la réflexion, c'est beaucoup plus complexe que ça et, selon moi, pas réalisable en SQL.

---

Voila qui est dommage.
Comment faire alors (en évitant à tout pris la liste de points d'un coté et la liste d'objets de l'autre...)?

Merci de ta réponse.

Si la liste n'est pas de taille fixe (et même là ce serait une horreur), je ne voit rien à faire en SQL.

A la limite, il y a moyen de définir une fonction qui prend le rectangle et la chaine de caractères et fait le test. Là il y aura moyen de faire une boucle pour décoder la chaine. Mais ça va pas être terrible en termes de performances.

Quelques centaines de milliers d'enregistrements, ce n'est pas incommensurable. Surtout que s'il y a tant de données que ça, traiter les chaines de caractère pour tous les objets va faire très mal. Ça me semble un cas tout trouvé pour les fonctionnalités GIS. Surtout que ça permettrait de bénéficier d'index spatiaux, ce genre de requête en a grand besoin.

Citation:

---

Envoyé par Sivrît

Si la liste n'est pas de taille fixe (et même là ce serait une horreur), je ne voit rien à faire en SQL.

---

Oui, en effet j'ai bien conscience que ma structure n'est pas optimale. Mais sérieusement je ne vois pas d'autre solution satisfaisante.
Sur le plan des deux tables, il serai faisable de faire une liste de points uniquement rattachés à un seul enregistrement de la liste des objets (ce qui evite toute sorte de contraintes si les points pouvaient etre commun à deux reccords).
Mais cela ne résoud pas le probleme de la liste qui serait stockée toujours sous la forme index1,index2,index3... avec index l'index du point correspondant.

Citation:

---

A la limite, il y a moyen de définir une fonction qui prend le rectangle et la chaine de caractères et fait le test. Là il y aura moyen de faire une boucle pour décoder la chaine. Mais ça va pas être terrible en termes de performances.

---

C'est exactement je ce que je suis entrain de tester :)
On verra ce que donne la mise en charge.

Citation:

---

Quelques centaines de milliers d'enregistrements, ce n'est pas incommensurable. Surtout que s'il y a tant de données que ça, traiter les chaines de caractère pour tous les objets va faire très mal. Ça me semble un cas tout trouvé pour les fonctionnalités GIS. Surtout que ça permettrait de bénéficier d'index spatiaux, ce genre de requête en a grand besoin.

---

Parfais ça.
Cependant je suis sous hébergement mutalisé et j'aimerai, si possible, y developper mon systeme de sorte qu'il soit compatible sur un large ensemble de configurations (en termes de performances). Mon SGBD est sous MySQL et je vais regarder si il prend en charge ce genre de choses.

[Edit]
Je n'arrive pas à voir si le MySQL installé chez 1and1 le supporte.
Le serveur est sous MySQL 5.0.81 et je stocke avec MyISAM. J'ai cru comprendre que ces fonctionnalités géospatiales étaient supportées nativement depuis MySQL 5.0.16. Est-ce vraiement le cas?
[/Edit]

Merci des conseils.

Je travaille sur une application qui est confrontée à ce genre de problème et de structure. Celui qui l'a développée a traité ces cas en PHP.
1) Extraction de la chaîne contenant les coordonnées des points du polygone
2) Algorithmes en PHP pour les fonctions du genre "le point cliqué sur la carte fait-il partie du polygone"

PHP est très performant pour traiter des chaînes de caractères, MySQL beaucoup moins, ce n'est pas son boulot.

Citation:

---

Envoyé par CinePhil

PHP est très performant pour traiter des chaînes de caractères, MySQL beaucoup moins, ce n'est pas son boulot.

---

En effet, nous sommes d'accord.

Mais certains de mes garde-fous personnels m'interdisent de charger des centaines de milliers d'enregistrement au cours de requêtes pouvant être très répétées et courantes (si la requête n'intervenait qu'une fois tous les mois je n'aurai rien à dire mais là...).

Je préfère nettement la solution du SQL Spatial dont j'ai réussi à trouvé certaines fonctionnalités sur mon serveur.
Cependant la catégorie d'index SPATIAL n'est pas disponible sous PHPMyAdmin (et même lorsque je fait une requête SQL, le serveur me jette). Avez-vous une idée du pourquoi?

Jamais utilisé les fonctions spatiales de MySQL donc moi pas savoir. Désolé.

Citation:

---

Envoyé par CinePhil

Jamais utilisé les fonctions spatiales de MySQL donc moi pas savoir. Désolé.

---

Pas mieux, donc ça va être un peu spéculatif.

Citation:

---

Envoyé par fanfouer

Mais cela ne résoud pas le probleme de la liste qui serait stockée toujours sous la forme index1,index2,index3... avec index l'index du point correspondant.

---

Il faut absolument se débarrasser de cette "liste" conservée dans un champ. Ce n'est pas relationnel et ne pourra pas être manié efficacement en SQL.

L'idée était de prendre la relation dans l'autre sens : Une table "figures", et une table "points" dont les enregistrement ont une clef étrangère sur "figures". Ca nous ramène à la solution de Maljuna Kris :

Code:

---

1 2	FIGURES: id, [...] POINTS: id_figures, x, y

---

Eventuellement, on peut aussi numéroter les points d'une figure pour poser une clef primaire sur (id_figures, num). L'intérêt est que la requête devient simple, et un index sur x et/ou y peut dégrossir le travail.

Reste que les les fonctionnalités GIS seront certainement plus efficaces. Je pense qu'en terme de schéma ça ressemblerait à ça :

Code:

---

1 2 3 4 5 6

CREATE TABLE `points` ( id_figures INT(10) unsigned not null, num TINYINT(3) unsigned not null, coord TINYBLOB not null, PRIMARY KEY (id_figures, num) );

---

"coord" contiendrait un "point" GIS. Sinon il y aurait peut-être moyen de mettre directement un polygone ou un ensemble de points sur "figures", mais comme je ne connais pas cette partie de MySQL...

Citation:

---

Envoyé par fanfouer

Mais certains de mes garde-fous personnels m'interdisent de charger des centaines de milliers d'enregistrement au cours de requêtes pouvant être très répétées et courantes (si la requête n'intervenait qu'une fois tous les mois je n'aurai rien à dire mais là...).

---

Tant que tout sera conservé dans une unique chaine de caractères sur laquelle il faudra faire des traitements complexes pour trouver les données dont on a besoin, ça impliquera une lecture complète de la table. Qu'ensuite les traitements soient faits au niveau de la base ou pas ne change pas grand chose. A la limite, les faire côté client (avec quelques précautions) permet de répartir la charge. Reste que si les enregistrement se comptent par 100k, des requêtes "répétées et courantes" vont tout écrouler.

Citation:

---

Envoyé par fanfouer

Je préfère nettement la solution du SQL Spatial dont j'ai réussi à trouvé certaines fonctionnalités sur mon serveur.
Cependant la catégorie d'index SPATIAL n'est pas disponible sous PHPMyAdmin (et même lorsque je fait une requête SQL, le serveur me jette). Avez-vous une idée du pourquoi?

---

Je vois deux possibilités :

• phpMyAdmin ne gère pas ces fonctionnalités. Il a ses limites et on sort des fonctionnalités usuelles. Je suis plutôt du genre accroc au client ligne de commande (ce qui signifie aussi... que je ne connais pas vraiment phpMyAdmin :mrgreen:).
• Les fonctionnalités GIS ne viennent pas en standard (ou sont désactivées par l'hébergeur). Sur ma 5.0.51a-community-nt ça semble disponible.
• C'était bien une table MyIsam ? (je sais ça fait trois, ça m'est venu en route). Sur ma machine le moteur par défaut est InnoDb qui ne les supporte pas.

Merci Sivrît et les autres pour vos réponses :)

Entre les deux solutions que tu proposes Sivrît, je pense que je vais poursuivre vers le SQL Spatial.
Une bonne part de ce choix vient du fait que les fonctions préconisées par l'OpenGIS sont presque toutes implémentées et qu'elles permettent un traitement sur une liste de coordonnées. La compacité du stockage correspond donc parfaitement à ce que je voulais faire et l'idée de créer une table réservée aux points ne me séduit qu'à moitié (bien que, et tu as raison, ce soit nettement plus en phase avec le fonctionnement de SQL).
Il est en outre possible de travailler avec des types primitifs d'objets (lignes, zones, points), ce qui me permet de supprimer certains scripts de mon serveur vu que ce sera à SQL d'effectuer ces taches.

Enfin, il reste juste un petite chose (cf ici) : MySQL ne possède pas encore les fonctions d'analyse de formes, il faut donc de toutes façons créer le rectangle de la zone qui m'intéresse dans la requête puis de tester non pas les points, mais les enveloppes rectangulaires de chaque objet dans la table. Cela marche très bien, c'est juste pas optimisé du tout vu que j'en charge un peu plus que ce qui est effectivement présent dans le rectangle de sélection (mais le moteur de rendu élude tout point en dehors de la zone, donc plus de problèmes).

Pour PHPMyAdmin, ce n'est pas si grave, j'ai en plus deux versions de retard. Je le mettrai donc à jour et je ne sais pas si je vais avoir besoin d'index géographique vu que je ne cerne pas encore ses particularités face à un index classique.

Un grand merci pour votre aide, problème résolu :)