Rapprocher les polygones d'un lat, long à mysql

Question

Quelqu'un connaît-il un moyen de récupérer tous les polygones dans une base de données MySQL à une distance donnée à partir d'un point? La distance réelle n'est pas si importante car elle est calculée pour chaque polygone trouvé plus tard, mais ce serait une énorme optimisation de simplement faire ce calcul pour les polygones qui sont "proches".

J'ai regardé le MBR et contient des fonctions, mais le problème est que certains des polygones ne sont pas contenus dans une boîte délimitation tracée autour du point car elles sont très grandes, mais certains de leurs sommets sont toujours proches.

Aucune suggestion?

Answer 1

Une version lente (sans index spatiaux):

SELECT  *
FROM    mytable
WHERE   MBRIntersects(mypolygon, LineString(Point(@X - @distance, @Y - @distance), Point(@X + @distance, @Y + @distance))

Pour utiliser les index spatiaux, vous devez dénormaliser votre table afin que chaque sommet de polygone soit stocké dans son propre enregistrement.

Créez ensuite le SPATIAL INDEX Sur le terrain qui contient les coordonnées des sommets et émettez simplement cette requête:

SELECT  DISTINCT polygon_id
FROM    vertices
WHERE   MBRContains(vertex, LineString(Point(@X - @distance, @Y - @distance), Point(@X + @distance, @Y + @distance))

Les choses seront beaucoup plus faciles si vous stockez UTM Coordonne dans votre base de données plutôt que la latitude et la longitude.

Answer 2

Je ne pense pas qu'il y ait une seule réponse à cela. Il s'agit généralement de savoir comment organiser vos données afin qu'il utilise la localité spatiale inhérente à votre problème.

La première idée qui me vient à l'esprit serait d'utiliser une grille, d'attribuer chaque point à un carré et de vérifier le carré dans lequel le point se trouve et ceux qui l'entourent. Si nous parlons de grilles infinies, alors utilisons une valeur de hachage du carré, cela vous donnerait plus de points que nécessaire (où vous avez des collisions), mais réduira toujours la quantité d'un tas. Bien sûr, cela n'est pas immédiatement applicable aux polygones, c'est juste un brainstoral. Une approche possible qui pourrait donner trop de collisions serait pour ou toutes les valeurs hachées et sélectionner toutes les entrées où les hachages et avec cette valeur sont non nuls (je ne sais pas si cela est possible dans MySQL), vous voudrez peut-être utiliser un grand quantité de bits cependant.

Le problème avec cette approche est que, en supposant que nous parlons des coordonnées sphériques (Lat, le fait généralement) les singularités, à mesure que les «carrés» de la grille se rétrécissent à l'approche des pôles. L'approche facile est ... ne mettez aucun point près des pôles ... :)

Answer 3

Créez une boîte de délimitation pour tous les polygones et (le stockage éventuellement de ces résultats dans la base de données rendra cela beaucoup plus rapidement pour les polygones complexes). Vous pouvez ensuite comparer la boîte de délimitation pour chaque polygone avec le tour du point à la taille souhaitée. Sélectionnez tous les polygones qui ont des boîtes de délimitation qui se croisent.