data-structures - espaciales - base de datos geografica

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

Dependiendo de cómo lo esté usando y de que los puntos se muevan rápidamente, también podría considerar barrer y podar . 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 tus dos sugerencias ya son bastante buenas, por cierto)

Answer 2

KD-trees o Quad / Oct trees son opciones razonables.

Ejemplos en Haskell:

• QuadTree

• KD Tree

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

Answer 3

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

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

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

Answer 4

Este viejo documento de Overmars y van Leeuwen describe el pseudo quadtree : un quadtree que también puede equilibrarse a sí mismo a medida que avanzan las inserciones y eliminaciones. El costo amortizado de las inserciones y eliminaciones es algo así como O(log^d(n)) e incluso se puede negociar contra la cantidad de saldo realizado (puede leer más sobre esto en el documento).