rien de mieux que les boîtes de délimitation?

Question

J'ai un scénario, où j'ai x millions de points de latitude de longitude.

Quand un nouveau point latitude / longitude est ajouté que je veux savoir efficacement que d'autres points sont dans un paramètre de distance configuré utilisateur, donc je peux les ajouter à une liste.

a obtenu quelque chose de mieux que les boîtes bondissant?

J'aimerais voir des algorithmes, des références et quelques implémentations;) merci de bien vouloir

Answer 1

Il y a quelques options qui sont mieux, pour la plupart basés autour partitionnement de l'espace .

Une commune, et souvent très bonne option (qui est pas trop difficile à mettre en œuvre) est d'utiliser un KD-Tree . Quadtrees sont plus faciles à mettre en œuvre, mais plus lent pour la recherche. En fonction de la distribution de vos données et vos besoins, d'autres algorithmes de partitionnement de l'espace peuvent mieux fonctionner, ont des exigences de mémoire plus bas, ou d'autres problèmes qui sont liés.

Answer 2

Un collègue m'a dit qu'il avait une bonne expérience en utilisant Morton-Code comme un index spatial sur les données du SIG, peut-être que quelque chose est utile d'examiner.

Answer 3

Cette approche rapide et sale peut vous faire économiser de la douleur: Diviser la surface de la terre dans 1 boîtes de degré. Vous aurez alors un ensemble d'éléments 180x360 et vous aurez seulement besoin de chercher un petit nombre de boîtes, y compris la boîte contenant le nouveau point et toutes les cases immédiatement autour d'elle dont l'un des coins se trouve à la distance spécifiée par l'utilisateur. Vous trouverez qu'il ya quelques trucs que vous pouvez utiliser pour comprendre rapidement ce que les boîtes à utiliser sans les considérer tous. Il suffit de ne pas oublier wrap-around latitude et longitude.

Si votre « seulement » ont des millions de points, et ils ne sont pas regroupés dans les points chauds, qui pourraient passer à travers.

Une façon théoriquement supérieure: Vous pouvez mapper chaque point dans un espace à trois dimensions, puis les stocker dans un octree , qui vous permettra de trouver rapidement des points à proximité à une distance arbitraire. Bien sûr, la distance dans l'espace en trois dimensions sera légèrement différente de la distance du grand cercle sur le globe, de sorte que vous devrez calculer un facteur de conversion. Cela devrait être simple, cependant. Vous ne Si vous ne me dérange pas d'insérer le code tiers mentionnez pas un langage de mise en œuvre, mais il va certainement être une implémentation octree bien testée pour la langue que vous travaillez., Cette solution est la façon de aller.