R Tree Aperçu de 50 000 pieds?

Question

Je travaille sur un projet d'école qui consiste à prendre un point lat/long et à trouver les cinq points les plus proches dans une liste de lieux connus. La liste doit être stockée en mémoire, avec la mise en garde que nous devons choisir une "structure de données appropriée" - c'est-à-dire que nous ne pouvons pas simplement stocker toutes les places dans un tableau et comparer les distances une par une de façon linéaire. L'enseignant a suggéré de regrouper les données de lieu par État américain pour éviter de calculer la distance pour des endroits qui sont évidemment trop loin. Je pense que je peux faire mieux. De mes recherches en ligne, il semble qu'un R-Tree ou l'un de ses variants pourrait être une solution soignée. Malheureusement, cette phrase est aussi loin que j'ai compris la technique, car la littérature est tout simplement trop dense pour ma tête non académique.

• quelqu'un peut me donner une vue d'ensemble très élevé de ce que le processus est de remplissage d'un arbre R avec des données lat/long, puis traversant l'arbre pour trouver les 5 voisins les plus proches d'un point donné?

• De plus le projet est en C, et je n'ai pas besoin de réinventer la roue, donc si vous avez utilisé une implémentation en C open source existante d'un arbre R, je serais intéressé par vos expériences.

MISE À JOUR:This blog post décrit un algorithme de recherche simple pour un espace cloisonné régional (comme un quadtree PR). J'espère que cela aidera un futur lecteur.

Answer 1

Avez-vous envisagé d'autres structures de données? Je crois, au lieu de R-tree, un point Quadtree serait plus efficace pour votre besoin. Spatial Index Demos fournit quelques démos pour une liste de structures de données possibles, y compris R-tree et Point Quadtree. J'espère que cela donne un aperçu.

Answer 2

arbres Quad

Un arbre de quad prend un carré de superficie et le divise en quatre enfants avec la moitié des dimensions le long de l'axe X et Y.

+---+---+ 
| | | Each square is a child 
| | | of the parent; when you 
+---+---+ get to leaves a node has 
| | | a single point or a list 
| | | of points. 
+---+---+ 

Cette structure de données est récursive et vous recherchez des points en vérifiant que l'enfant tient le point jusqu'à ce que vous obtenez à la feuille. Une feuille a un seul membre (point avec X, Y coords) ou une liste de membres, en fonction de la mise en œuvre. Si vous remplissez un nœud, vous le divisez en 4 et distribuez les enfants. Essentiellement, la structure de données est une généralisation d'un arbre binaire, donc elle n'est pas nécessairement équilibrée.

équilibrage d'un arbre quad peut ne pas être nécessaire à vos fins et reste comme un exercice pour le lecteur - essayez la recherche sur le web pour « arbre quad équilibré »

Notez que cette structure de données ne peuvent pas les éléments d'index qui peuvent chevauchement, mais si vous ne stockez que des points, ce ne sera pas un problème.

Trouver plus proches voisins dans un arbre quad

Du haut de ma tête, voici un algorithme rapide et sale pour trouver le plus proche « n » voisins à votre point. Ce n'est pas forcément efficace, mais il sera assez simple à mettre en place. Si quelqu'un a un lien vers un meilleur, n'hésitez pas à le poster dans un commentaire ou une réponse.

• Localisez le nœud d'arborescence quad contenant votre point, en gardant une liste de ses parents.

• poussoir tous les points du noeud dans une file d'attente de priorité sur la base de leur distance par point de base (à savoir par la longueur de l'hypoténuse par le théorème de Pythagore). Selon sur l'implémentation, il peut y avoir un ou plusieurs par nœud. Pour une implémentation simple d'une structure de données de file d'attente prioritaire , recherchez 'binary heap'.

• Si l'un des 'n' points est plus éloigné que les bords de la boîte englobante, ajoutez le contenu de ses voisins. C'est-à-dire que si votre point de base est proche du bord de la boîte englobante, il est possible que les nœuds d'arbre voisins contiennent des points plus proches que les points trouvés dans votre cadre de sélection. Vous devrez sauvegarder l'arborescence pour cela, c'est pourquoi vous devez suivre vos nœuds parents.

• Lorsque tous les 'n' points les plus proches sont plus proches que les bords de votre boîte englobante, vous savez qu'il ne peut pas y avoir de voisins que vous avez manqués. Par conséquent, les «n» points les plus proches dans cette case doivent être vos «n» plus proches voisins.