Estructura de datos para datos espaciales

Question

Estoy buscando una buena estructura de datos funcional para almacenar datos espaciales (puntuales). La estructura de datos debería permitir consultas epsilon simples para puntos ya presentes. También tengo que modificar los datos con bastante frecuencia. Esto significa que los puntos se pueden mover y deberían poder actualizarse en la estructura de datos. Esto probablemente se pueda manejar usando un delete/add normal, pero un movimiento real podría ser más rápido.

Por ahora estoy pensando en usar quad/oct-trees (o superior), ya que la parte de movimiento debería ser bastante fácil de hacer. Sin embargo, se sabe que los árboles cuádruples son peores en lo que respecta al equilibrio. KD-Trees podría ser otra opción, pero la actualización parece bastante desagradable. También la mayoría de las implementaciones de estructuras de datos espaciales que puedo encontrar son solo de procedimiento y estoy usando un lenguaje funcional.

Answer 1

KD-árboles o árboles Quad/Oct son opciones razonables.

Ejemplos en Haskell:

• QuadTree

• KD Tree

Ambos son bastante simples para codificar estructuras de datos como puramente funcionales.

Answer 2

Dependiendo de cómo lo esté usando y de que los puntos se muevan rápidamente, también podría considerar sweep and prune. Básicamente, mantienes los puntos ordenados en una dimensión (digamos x). Si los puntos cambian de lugar muy pocas veces, ejecutar la ordenación de inserción para cada paso de simulación será muy rápido.

(creo que sus dos sugerencias ya son bastante buenos, por cierto)

Answer 3

R-Trees y R * -Tes son también otra solución, fácil de implementar.

Consulte https://github.com/mariusaeriksen/ocaml-rtree (en OCaml) para obtener un ejemplo.

Los usé en una simulación de evacuación, el paso de actualización no es tan lento como ese.

Answer 4

This old paper por Overmars y van Leeuwen describe la seudo quadtree - un árbol de cuatro ramas que también puede equilibrar a sí misma como inserciones y deleciones de progreso. El costo amortizado de las inserciones y eliminaciones es algo así como O(log^d(n)) e incluso puede negociarse con la cantidad de saldo realizado (puede leer más sobre esto en el documento).