Obtenir des polygones proches d'un lat, long dans MySQL

Question

Est-ce que quelqu'un connaît un moyen d'aller chercher tous les polygones dans une base de données MySQL à une distance donnée d'un point? La distance réelle n'est pas si importante puisqu'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 de délimitation dessinée autour du point car ils sont très gros, mais certains de leurs sommets sont toujours proches.

Des suggestions?

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 du polygone est stocké dans son propre record.

Ensuite, créez le SPATIAL INDEX sur le champ qui contient les coordonnées des sommets et émettre 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 facile si vous stockez UTM coordonnées dans votre base de données plutôt que la latitude et longitude.

Answer 2

Je ne pense pas qu'il y ait une seule réponse à cela. C'est généralement une question d'organisation de vos données afin qu'elles utilisent la localité spatiale inhérente à votre problème.

La première idée qui me vient à l'esprit serait d'utiliser une grille, d'assigner chaque point à un carré, et de cocher la case où se trouve le point et celles qui l'entourent. Si nous parlons des grilles infinies, alors utilisez une valeur de hachage du carré, cela vous donnerait plus de points que nécessaire (où vous avez des collisions), mais réduira encore le montant par un groupe. Bien sûr, ceci n'est pas immédiatement applicable aux polygones, c'est juste un brainstorming. Une approche possible qui pourrait générer trop de collisions consisterait à OU toutes les valeurs hachées ensemble et sélectionner toutes les entrées où les hachages AND avec cette valeur est non nulle (pas sûr si cela est possible dans MySQL), vous pouvez utiliser un grand quantité de bits cependant. Le problème avec cette approche est, en supposant que nous parlons de coordonnées sphériques (lat, long généralement), les singularités, car les carrés de la grille se rétrécissent à mesure que vous approchez les pôles. L'approche facile à cela est ... ne placez pas de points près des pôles ... :)

Answer 3

Créer une boîte englobante pour tous les polygones et (le stockage éventuel de ces résultats dans la base de données en fera un beaucoup plus rapide pour les polygones complexes). Vous pouvez ensuite comparer la zone de délimitation pour chaque polygone avec celle autour du point à la taille désirée. Sélectionnez tous les polygones qui ont des limites de délimitation.