Comment puis-je diviser le globe en petites grilles de telle sorte que cela me permette d’attribuer chaque emplacement lat / long à une grille? [fermé]

Question

Afin de calculer les emplacements les plus proches représentés par la latitude / la longitude, j’envisageais de diviser la carte en petites grilles, environ 100 x 100 mètres. Essentiellement, chaque point serait affecté à une grille.

Je comprends que je pourrais aussi utiliser des index spatiaux avec MySQL, etc., mais je prévois d'utiliser une base de données non relationnelle telle que Cassandra où il serait difficile d'indexer des objets spatiaux. Une sorte de technique d'approximation de grille pourrait être soigné.

Quel serait le meilleur moyen de créer un tel système de grille et d’y cartographier les emplacements spatiaux 2D?

Edit1: Cela pourrait aller si les grilles ne sont pas parfaitement uniformes, surtout autour des pôles.

Answer 1

Les grilles rectangulaires peuvent constituer une estimation raisonnable, mais uniquement sur une zone relativement petite qui n’est pas trop proche des pôles. Une solution globale nécessite une approche différente.

Answer 2

La correspondance entre les coordonnées spatiales bidimensionnelles et votre index / geohash spatial est un problème intéressant. Vous pouvez consulter cette article sur les quadtrees, les geohashes et les courbes de Hilbert . La courbe de Hilbert est une courbe remplissant l'espace qui fournit la localité; pour vos besoins, cela signifie que les éléments proches dans l'index spatial unidimensionnel seront proches dans un espace bidimensionnel.

L'objectif (décrit par d'autres intervenants) est de minimiser le nombre de requêtes nécessaires pour couvrir l'espace en question sans requérir des tonnes de données inutiles du serveur. La manière dont vous faites la correspondance entre un espace 2D et un index 1D affectera cet objectif.

Answer 3

Sans connaître exactement les exigences de votre application, Geohashing est peut-être une technique appropriée: http: //en.wikipedia. org / wiki / Geohash

& "; Il s’agit d’une structure de données spatiales hiérarchique qui subdivise l’espace en compartiments de forme quadrillée. Les Geohashes offrent des propriétés telles que la précision arbitraire et la possibilité de supprimer progressivement les caractères de la fin du code afin de réduire sa taille (et de perdre progressivement la précision). & Quot;

Answer 4

Vous ne pouvez pas créer de grille rectangulaire mappant uniformément un globe. Si la grille doit être uniforme, vous devez utiliser des triangles à la place. Mais en général, je doute que cela résoudra votre problème. Vous avez besoin d'un octree en 2D (lien de recherche Google; vérifiez les images). pour savoir comment cela fonctionne): vous devez diviser vos coordonnées en hiérarchies (par exemple, nord / sud / est / ouest de l’origine pour le premier niveau, puis entre 90 degrés, etc.).

Ensuite, vous pouvez faire plusieurs sélections qui donneront rapidement le plus petit rectangle contenant les coordonnées existantes. Maintenant, vous pouvez vérifier la taille du rectangle. Si c'est & Lt; 100m, alors vous avez trouvé une solution. Sinon, vous n'aurez que quelques positions à vérifier (généralement une).

Google pour " base de données octree sql " pour les implémentations.