Structure des données spatiales

Question

Je recherche une bonne structure de données fonctionnelles pour stocker des données spatiales (ponctuelles). La structure de données devrait permettre des requêtes epsilon simples pour les points déjà présents. Aussi j'ai besoin de modifier les données assez souvent. Cela signifie que les points peuvent bouger et devraient pouvoir être mis à jour dans la structure de données. Cela peut probablement être géré en utilisant une suppression/ajout normal, mais un vrai mouvement pourrait être plus rapide. Pour l'instant, je pense à utiliser quad/oct-trees (ou plus), car la partie de mouvement devrait être assez facile à faire. Cependant, les quadri-arbres sont connus pour être pires en ce qui concerne l'équilibrage. KD-Trees pourrait être un autre choix, mais la mise à jour semble assez méchant. La plupart des implémentations de structures de données spatiales que je peux trouver sont seulement procédurales et j'utilise un langage fonctionnel.

Answer 1

KD arbres ou des arbres Quad/Oct sont des choix raisonnables.

Exemples dans Haskell:

• QuadTree

• KD Tree

Les deux sont assez simples pour coder comme purement structures de données fonctionnelles.

Answer 2

Selon la façon dont vous l'utilisez et rapidement, les points se déplacent, vous pouvez également envisager sweep and prune. Fondamentalement, vous gardez les points triés dans une dimension (disons x). Si les points changent très rarement, le tri par insertion en cours pour chaque étape de la simulation sera très rapide.

(je pense que vos deux suggestions sont déjà très bien, par la voie)

Answer 3

R-Trees et R * -Arbres sont également une autre solution, facile à mettre en œuvre. Voir https://github.com/mariusaeriksen/ocaml-rtree (dans OCaml) pour un exemple. Je les ai utilisés dans une simulation d'évacuation, l'étape de mise à jour n'est pas si lente que cela.

Answer 4

This old paper par Overmars et van Leeuwen décrit la pseudo quadtree - un quadtree qui peut aussi s'équilibrer comme insertions et suppressions progrès. Le coût amorti des insertions et des suppressions est quelque chose comme O(log^d(n)) et peut même être échangé contre le montant de l'équilibrage effectué (vous pouvez en lire plus à ce sujet dans le document).