Comment rechercher efficacement tous les points de repère dans une plage d'un certain point de repère?

14

J'essaie de commencer avec un projet de recherche géographique qui trouvera tous les points de repère dans les 10 km / miles (pas importants pour cette histoire) d'un point de repère particulier.

Ainsi, par exemple, disons que j'ai une base de données d'un million de points de repère. Afin de trouver tous les points de repère dans la plage de 10 miles d'un point de repère avec certaines coordonnées, je devrais calculer une distance entre un point de repère à partir de ma recherche et 1 000 000 de points de repère.

Y a-t-il une meilleure façon de le faire?

L'alternative à laquelle je pensais est de classer les points de repère tels que le pays, la région, la ville, le quartier, les affaires, l'historique, etc. de telle manière que les entreprises puissent faire partie d'un quartier ou d'une ville. La ville fait partie d'une région, d'un pays, etc. Cela peut restreindre une liste de calculs, mais il semble que beaucoup de travail soit nécessaire pour que la recherche soit rapide et précise.

L'API Google Maps pourrait-elle aider?

Dario Granich
la source
5
Vous pourriez probablement éliminer un bon nombre simplement en effectuant un calcul rapide de la distance de Manhattan, puis en effectuant un deuxième filtre par la suite pour exclure les points de repère qui se trouvent dans un carré de 10 km mais qui sont en dehors du rayon de 10 km.
Neil
3
Quelle technologie de base de données utilisez-vous? La réponse n'est pas indépendante de la base de données.
jpmc26
1
@Neil En tant que deuxième passage, vous pouvez inclure n'importe quel point de repère où les x et y tombent tous les deux à 7 km de l'origine sans calculer la distance réelle.
JimmyJames

Réponses:

10

Depuis SQL Server 2008, il existe un type de données géographiques qui stocke les emplacements (paires lat / lon) et vous permet d'écrire facilement des requêtes liées à l'emplacement.

Il existe une réponse StackOverflow existante qui en discute en profondeur.

Une requête de base pour trouver les 7 articles les plus proches :

USE AdventureWorks2012  
GO  
DECLARE @g geography = 'POINT(-121.626 47.8315)';  
SELECT TOP(7) SpatialLocation.ToString(), City FROM Person.Address  
WHERE SpatialLocation.STDistance(@g) IS NOT NULL  
ORDER BY SpatialLocation.STDistance(@g);  

Une requête basique pour tout trouver à moins de 100m (deuxième réponse à la question)

-- Get the center point
DECLARE @g geography
SELECT @g = geo FROM yourTable WHERE PointId = something

-- Get the results, radius 100m
SELECT * FROM yourTable WHERE @g.STDistance(geo) <= 100
Flater
la source
11
@KonradRudolph: comme c'est le cas pour toute colonne SQL utilisée pour interroger une table avec un nombre de lignes important. Vous avez raison, mais ce commentaire s'appliquerait à pratiquement toutes les requêtes SQL publiées comme réponse.
Flater
2
Où avez-vous lu "MS SQL Server" dans la question?
Doc Brown
3
@Flater Je conviens que cela serait normalement évident et redondant, mais le libellé d'OP semble suggérer qu'ils ne connaissent pas de tels mécanismes.
Konrad Rudolph
2
@ jpmc26: Vous êtes consterné que j'ai répertorié une option valide et que je n'ait pas inclus une autre option? Quelle? Si vous pensez qu'il est pertinent d'ajouter PostGIS, ajoutez vous-même la réponse (ce que vous avez fait) et ne recourez pas à critiquer les autres pour ne pas avoir la même idée que vous.
Flater
3
Votre réponse m'apparaît essentiellement comme un argumentaire de vente MS SQL. Vos commentaires suggérant qu'ils changent de base de données pour quelque chose qui coûterait des dizaines de milliers de dollars sans réellement se renseigner sur ce que leur situation ne fait que faire apparaître plus. Il ne décrit même pas comment l'OP peut réellement implémenter leur requête ou discuter du fait que le faire et que l'index spatial est utilisé n'est pas aussi simple dans MS SQL que dans d'autres bases de données. Il ne traite pas non plus des concepts sous-jacents. C'est une mauvaise réponse, qu'elle soit "valide" ou non. Voilà pourquoi cela me dérange.
jpmc26
29

Utilisez une base de données prenant en charge les requêtes SIG (systèmes d'information géographique) . La plupart des bases de données le prennent en charge ou ont des extensions, mais les détails seront spécifiques à la base de données (dans leur réponse , Flater montre la syntaxe pour SQL Server).

Si vous devez implémenter de telles requêtes dans votre application, vous pouvez implémenter une structure de données qui autorise les requêtes spatiales, par exemple un arbre kd . C'est comme un arbre de recherche binaire, sauf que chaque niveau de l'arbre se partitionne sur une dimension de coordonnées différente. Cela vous permet de restreindre la recherche à un plus petit ensemble de candidats réalisables. En effet, vous traduisez votre recherche «rayon de 10 km» en limites pour chaque dimension de coordonnées, et resserrez les limites au fur et à mesure de votre progression dans l'arborescence.

amon
la source
5
Il y a aussi un échange de pile SIG
BlueRaja - Danny Pflughoeft
8
PostGIS est la première option gratuite. Il prend en charge bien plus que les types et fonctions SIG très basiques de SQL Server. Mais c'est une fonctionnalité de base.
jpmc26
@amon Je trouve le commentaire de jpmc26 comme un bon ajout, et pas autant que de critiquer votre exemple. "Si vous voulez recommencer à zéro, vous n'avez pas besoin de payer pour une base de données sous licence - celle-ci gratuite et open-source fera également très bien l'affaire".
mgarciaisaia
11

Oui, il y a une meilleure façon. Vous devez utiliser un index spatial . Ces index organisent des métadonnées sur les géométries pour filtrer très rapidement les géométries éloignées, économisant ainsi beaucoup de cycles CPU en évitant les calculs que vous décrivez. Vous ne devriez pas vous soucier de l'implémenter vous-même, car toutes les principales bases de données relationnelles fournissent un type de géométrie spatiale et des index pour les accompagner.

Ce que vous voulez examiner, ce sont des requêtes "à distance" (requêtes pour des géométries à une certaine distance d'une autre géométrie). Ce sont des problèmes très standard et résolus et sont possibles dans toutes les bases de données ci-dessus (et intégrées dans plusieurs):

  • PostGIS: ST_DWithin
  • SQL Server: STDistance(pas clair que l'utilisation de l'index sur la version de géographie 3D de cette fonction est prise en charge)
  • Oracle: SDO_WITHIN_DISTANCE(Cela ne dit pas explicitement que cela déclenchera l'utilisation de l'index. Je revérifierais le plan de requête. Vous pourriez avoir besoin d'appliquer un SDO_FILTERpour qu'il utilise l'index.)
  • MySQL: Toujours en train de comprendre cela.

Solution de contournement pour déclencher l'utilisation de l'index

Dans le pire des cas où vous avez du mal à faire en sorte que le système utilise l'index spatial avec ces requêtes, vous pouvez ajouter un filtre supplémentaire. Vous créez un cadre de délimitation carré avec des côtés de longueur 2 * (distance de recherche) centrés sur votre point de recherche et comparez les cadres de délimitation des géométries de table à ceux-ci avant de vérifier la distance réelle. C'est ce que fait PostGIS ST_DWithinci-dessus en interne de toute façon.


Distance en SIG

Alors que les index spatiaux sont fantastiques et absolument la bonne solution à votre problème, le calcul de la distance peut devenir logiquement compliqué. En particulier, vous devez vous soucier de la projection (essentiellement tous les paramètres du système de coordonnées) dans laquelle vos données sont stockées. La plupart des projections 2D (autres que les systèmes de coordonnées angulaires comme les diverses projections lat / longues) déforment considérablement la longueur. Par exemple, la projection Web Mercator (celle utilisée par Google, Bing et tous les autres principaux fournisseurs de cartes de base) élargit de plus en plus les zones et les distances à mesure que l'emplacement s'éloigne de l'équateur . Je peux me tromper car je ne suis pas formellement formé aux SIG, mais le meilleur que j'ai vu pour les projections 2D est quelques-unes spécifiques qui promettent des distances correctes à partir d'unpoint unique et constant dans le monde entier. (Non, il n'est pas pratique d'utiliser une projection différente pour chaque requête; cela rendrait vos index inutiles.)

L'essentiel est que vous devez vous assurer que vos calculs sont exacts. La façon la plus simple de le faire dans une perspective de développement est d'utiliser des projections angulaires (souvent appelées "géographiques") et des fonctions qui prennent en charge le calcul à l'aide d'un modèle sphéroïde, mais ces calculs sont légèrement plus chers que les équivalents 2D. et certaines bases de données peuvent ne pas prendre en charge leur indexation. Si vous pouvez obtenir des performances acceptables en les utilisant, c'est probablement la voie à suivre. Une autre option courante est les projections régionales (comme les zones UTM) qui rapprochent à la fois les distances et les zones à corriger si vos données sont limitées à une partie particulière du monde. Ce qui convient le mieux à votre application dépendra de vos besoins spécifiques,

Cela s'applique même si vous n'utilisez pas d'index spatiaux intégrés. Vos données ont une projection quelle que soit la technologie ou la technique que vous utilisez ou utilisez actuellement, et elles affectent déjà actuellement toutes les requêtes et tous les calculs que vous effectuez.

jpmc26
la source
3

Je conviens que si possible, l'utilisation d'un support spécifique dans une base de données serait le moyen le plus sensé de le faire.

Cependant, si je devais le faire sur une base de données sans support spécifique, je commencerais par demander un carré qui entoure la circule, par exemple (y> (y1 - rad)) AND (y <(y1 + rad)) AND (x> ( x1 - rad)) ET (x <(x1 + rad)). En supposant que vos points ont une distribution à peu près égale, la recherche d'un carré vous donnera vos vrais matchs plus environ 30% de faux matchs supplémentaires. Vous pouvez ensuite éliminer les fausses correspondances.

Peter Green
la source
Mais sans un index spatial approprié, une telle requête analysera au pire toute la base de données, au mieux tous les éléments dans la plage de latitude OU de longitude donnée en fonction de votre index, c'est-à-dire une "bande" plutôt qu'un carré. Si vous ne voulez pas réduire les performances, utilisez une base de données qui prend en charge les index spatiaux!
jcaron
@jcaron Je pense que cette requête pourrait être optimisée avec un index B-tree ordinaire sur xet y. (Peut-être combiné, peut-être séparé. Je profilerais un peu pour comprendre ce qui fonctionne mieux dans la pratique.)
jpmc26
@ jpmc26 Non, ça ne peut pas. Réfléchissez bien, vous verrez.
jcaron
@jcaron Ce serait peut-être mieux si vous n'étiez pas énigmatique à propos de quelque chose qui n'est clairement pas simple. Les arbres B peuvent être utilisés pour les BETWEENrequêtes. Je ne vois pas pourquoi le pire des cas, vous ne pourriez pas avoir 2 index, puis les résultats filtrés de chaque index sont réunis. (C'est quelque chose que les SGBDR font en interne lorsqu'ils jugent utile d'utiliser plusieurs index.) Si un index combiné fonctionne, il devrait filtrer une dimension entièrement au premier niveau, puis se rétrécir relativement rapidement au deuxième niveau.
jpmc26
2
@jcaron en fait, vous pouvez utiliser l'index pour quelque chose comme, y between -68 and -69 and x between 10 and 11mais bien sûr, l'index spatial fait un meilleur travail pour cette tâche
Juan Carlos Oropeza