Comparaison des coordonnées Lat et Long

Question

J'ai une liste de plus de 15 000 coordonnées de latitude et de longitude.Étant donné des coordonnées X, Y, quel est le moyen le plus rapide de trouver les coordonnées les plus proches de la liste ?

Answer 1

Vous souhaiterez utiliser une construction géométrique appelée Diagramme de Voronoï.Cela divise le plan en un certain nombre de zones, une pour chaque point, qui englobent tous les points les plus proches de chacun de vos points donnés.

Le code des algorithmes exacts permettant de créer le diagramme de Voronoi et d'organiser les recherches de structure de données est trop volumineux pour tenir dans cette petite zone d'édition.:)

@Linor :C'est essentiellement ce que vous feriez après avoir créé un diagramme de Voronoï.Mais au lieu de créer une grille rectangulaire, vous pouvez choisir des lignes de séparation qui correspondent étroitement aux lignes du diagramme de Voronoï (de cette façon, vous obtiendrez moins de zones qui traversent les lignes de séparation).Si vous divisez récursivement votre diagramme de Voronoï en deux le long de la meilleure ligne de démarcation pour chaque sous-diagramme, vous pouvez ensuite effectuer une recherche arborescente pour chaque point que vous souhaitez rechercher.Cela nécessite un peu de travail au départ mais permet de gagner du temps plus tard.Chaque recherche serait de l'ordre du log N où N est le nombre de points.16 comparaisons, c'est bien mieux que 15 000 !

Answer 2

Je l'ai fait une fois pour un site Web.C'est à dire.trouvez le revendeur dans un rayon de 50 miles autour de votre code postal.J'ai utilisé le calcul du grand cercle pour trouver les coordonnées qui étaient à 50 milles au nord, à 50 milles à l'est, à 50 milles au sud et à 50 milles à l'ouest.Cela m'a donné une latitude min et max et une longueur min et max.À partir de là, j'ai effectué une requête dans la base de données :

select *
    from dealers
    where latitude  >= minlat
      and latitude  <= maxlat
      and longitude >= minlong
      and longitude <= maxlong

Étant donné que certains de ces résultats seront toujours à plus de 50 miles, j'ai utilisé le formule du grand cercle encore une fois sur cette petite liste de coordonnées.Ensuite, j'ai imprimé la liste avec la distance par rapport à la cible.

Bien sûr, si vous souhaitez rechercher des points proches de la ligne de date internationale ou des pôles, cela ne fonctionnera pas.Mais cela fonctionne très bien pour les recherches en Amérique du Nord !

Answer 3

Le concept général que vous décrivez est recherche du voisin le plus proche, et il existe toute une série de techniques permettant de résoudre ce type de requêtes, de manière exacte ou approximative.L'idée de base est d'utiliser une technique de partitionnement spatial pour réduire la complexité de O(n) par requête à (environ) O(log n) par requête.

Les KD-Trees et leurs variantes semblent très bien fonctionner, mais les quad-trees fonctionneront également.La qualité de ces recherches dépend du caractère statique ou non de votre ensemble de 15 000 points de données (vous n'ajoutez pas beaucoup de points de données à l'ensemble de référence).Le travail de Mount et Arya sur le Voisin approximatif le plus proche La bibliothèque est à la fois facile à utiliser et à comprendre, même sans de bonnes bases en mathématiques.Cela vous offre également une certaine flexibilité dans les types et les tolérances de vos requêtes.

Answer 4

Cela dépend plutôt du nombre de fois que vous souhaitez le faire et des ressources disponibles. Si vous effectuez le test une fois, les techniques O (log N) sont bonnes.Si vous le faites mille fois sur un serveur, la construction d'une table de recherche bitmap serait plus rapide, soit en donnant le résultat directement, soit en première étape.2 Go de bitmap peuvent cartographier la latitude du monde entier à une valeur de 32 bits à 0,011 degrés de pixels (1,2 km à l'équateur) et devraient tenir dans la mémoire.Si vous ne faites qu'un seul pays ou si vous pouvez exclure les pôles, vous pouvez avoir une carte plus petite ou une résolution plus élevée.Pour 15 000 points, vous avez probablement une carte beaucoup plus petite - je l'ai d'abord dimensionnée comme première étape pour effectuer des recherches de latin et de code postal, qui nécessitent une résolution plus élevée.En fonction des besoins, vous utilisez la valeur mappée pour pointer directement sur le résultat ou pour présélectionner les candidats (ce qui permettrait une carte plus petite, mais nécessiterait un traitement ultérieur plus important - vous n'êtes plus dans le territoire de recherche O(1) ).

Answer 5

Vous n'avez pas précisé ce que vous entendiez par plus rapide.Si vous voulez obtenir la réponse rapidement sans écrire de code, je donnerais le filtre de rayon gpsbabel il y a.

Answer 6

Sur la base de vos clarifications, j'utiliserais une structure de données géométrique telle qu'un arbre KD ou un arbre R.MySQL a un type de données SPATIAL qui fait cela.D'autres langages/frameworks/bases de données ont des bibliothèques pour prendre en charge cela.Fondamentalement, une telle structure de données intègre les points dans un arbre de rectangles et recherche l'arbre en utilisant un rayon.Cela devrait être assez rapide et je pense que c'est plus simple que de construire un diagramme de Voronoï.Je suppose qu'il existe un certain seuil au-dessus duquel vous préféreriez les performances supplémentaires d'un diagramme de Voronoï, vous serez donc prêt à payer pour la complexité supplémentaire.

Answer 7

Cela peut être résolu de plusieurs manières.J'aborderais d'abord ce problème en générant un Delaunay réseau reliant les points les plus proches les uns aux autres.Cela peut être accompli avec la commande v.delaunay dans l'application SIG open source HERBE.Vous pouvez résoudre le problème dans GRASS en utilisant l'un des nombreux modules d'analyse de réseau dans l'herbe.Alternativement, vous pouvez utiliser le SGBDR spatial gratuit PostGIS pour faire les requêtes à distance.Les requêtes spatiales PostGIS sont considérablement plus puissantes que celles de MySQL, car elles ne sont pas limitées aux opérations BBOX.Par exemple:

SELECT network_id, ST_Length(geometry) from spatial_table where ST_Length(geometry) < 10;

Puisque vous utilisez Longitude et Latitude, vous souhaiterez probablement utiliser le Fonctions sphéroïde-distance.Avec un index spatial, PostGIS s'adapte très bien aux grands ensembles de données.

Answer 8

Même si vous créez un diagramme de Voronoi, cela signifie que vous devez comparer vos coordonnées x, y aux 15 000 zones créées.Pour rendre cela plus facile, la première chose qui m'est venue à l'esprit a été de créer une sorte de grille sur les valeurs possibles, afin que vous puissiez facilement placer et coordonner x/y dans l'une des cases d'une grille, si la même chose est fait pour la liste des zones, vous devez rapidement réduire les candidats possibles à la comparaison (parce que la grille serait plus rectangulaire, il est possible qu'une zone se trouve à plusieurs positions de la grille).

Answer 9

L'optimisation prématurée est la racine de tout Mal.

Les coordonnées 15K ne sont pas tant que ça.Pourquoi ne pas parcourir les coordonnées 15K et voir si c'est vraiment un problème de performances ?Vous pourriez économiser beaucoup de travail et peut-être qu’il ne sera jamais trop lent de s’en rendre compte.

Answer 10

Sur quelle superficie ces coordonnées sont-elles réparties ?A quelle latitude se trouvent-ils ?De quelle précision avez-vous besoin ?S'ils sont assez proches l'un de l'autre, vous pouvez probablement ignorer le fait que la Terre est ronde et simplement la traiter comme un plan cartésien plutôt que de jouer avec la géométrie sphérique et les distances orthodromiques.Bien sûr, à mesure que l'on s'éloigne de l'équateur, les degrés de longitude diminuent par rapport aux degrés de latitude, donc une sorte de facteur d'échelle peut être approprié.

Commencez par une formule de distance assez simple et une recherche par force brute et voyez combien de temps cela va prendre et si les résultats sont suffisamment précis avant de vous lancer dans l'aventure.

Answer 11

Merci à tous pour les réponses.

@Tom, @Chris Upchurch :Les coordonnées sont assez proches les unes des autres et se situent dans une zone relativement petite d’environ 800 km².Je suppose que je peux supposer que la surface est plate.Je dois traiter les demandes encore et encore, et la réponse doit être suffisamment rapide pour une meilleure expérience Web.

Answer 12

Une grille est très simple et très rapide.Il s'agit essentiellement d'un tableau 2D de listes.Chaque entrée du tableau représente les points qui se trouvent à l'intérieur d'une cellule de la grille.Très simple à mettre en place la grille :

for each point p
  get cell that contains p
  add point to that cell's list

et c'est très simple de rechercher les choses :

given a query point p
  get cell that contains p
  check points in that cell (and its 8 neighbors), against query point p

Alejo

Answer 13

Juste pour être à contre-courant, voulez-vous dire une distance proche ou un temps (de conduite) ?Dans une zone urbaine, je conduirais volontiers 5 miles (5 minutes) sur l'autoroute plutôt que 4 miles (20 minutes d'arrêt et de départ) dans une autre direction.

Ainsi, s'il s'agit d'une métrique « la plus proche » dont vous avez besoin, j'examinerais les bases de données SIG avec des métriques de temps de trajet.