Lo discbased es una buena opción para los objetos en un mapa-editor?

Question

Estoy planeando la implementación de un mapa-editor. Pero yo realmente no sé qué estructura de datos son una buena opción para almacenar el mapa-objeto. Cuando el usuario se desplaza (rollos) el mapa, habrá mucho buscar de qué objetos están en la zona visible, generalmente por tener una min_x, min_y y max_x, max_y par de coordenadas.

He leído que el R-los árboles son buenos para este tipo de uso, pero parecen ser complicados de implementar.

Hasta ahora sólo he usado una lista enlazada que yo tenga que recorrer muy a menudo; no es la óptima, pero funciona. ¿Hay alguna opción mejor de las estructuras de datos?

Answer 1

R-los árboles son de hecho una gran elección. Dependiendo de la plataforma que usted podría ser capaz de encontrar implementaciones de trabajo para no tener que pasar por el dolor.

Una alternativa más sencilla es utilizar Quadtrees (que son un caso especial de los R-trees, lo más sencillo) que puede ser lo suficiente para el caso de uso.

Answer 2

R-los Árboles si los datos están dispersos (que es muy probable que sea). Si usted tiene densa datos que puede almacenar un azulejo sistema basado en 2-D de la matriz o matriz dentada (matriz de matrices). Me gustaría evitar listas enlazadas, pero depende de lo que usted está tratando de lograr.

Answer 3

Echa un vistazo a la aplicación de la "com.vividsolutions.el stc.índice.strtree.STRtree" en el STC.

"Una sola consulta R-tree creado utilizando el Tipo de Teja-Recursivo (STR) algoritmo"

Answer 4

Dependiendo de sus necesidades y de datos como de otros carteles han tocado lo mejor es utilizar diferentes métodos. Si usted necesita una robusta y rápida aplicación que son los mejores para no simplemente utilizar una estructura de datos, pero a la vez el soporte de múltiples estructuras de datos para los diferentes conjuntos de datos. Si usted está teniendo problemas para entender cómo crear un índice de árbol R y tus datos no se loco una gran combinación de una profunda quad-tree siguió con sencillo MBR cheques pueden ser una fácil solución bastante buena. Para una colección con relativamente pocos elementos de un circuito simple puede superar el análisis de un árbol/lista enlazada, de manera que aunque un quad-tree no es el mejor ajuste para la mayoría de los datos se puede llegar muy cerca de ese número mágico donde estándar de bucle puede ser lo suficientemente rápido como para ser utilizable. También tenga en cuenta que el uso de una lista enlazada estructura versus uso de un considerable conjunto de recorrer más lento, especialmente si su software es cada vez compilado para el hardware directamente, como con la compilación JIT. Pero si usted puede hacerlo... R-tree es la manera de ir la mayoría del tiempo.

Answer 5

Otra opción, en lugar de preocuparse de este tipo de aplicación a sí mismo, es el uso de una base de datos espaciales: PostGIS es un común, de código abierto. La base de datos va a cuidar de el quad-tree de acceso para usted, permitiéndole almacenar sólo las geometrías en una base de datos, y tiene el identificador de base de datos geográfica de los índices para usted.