Métodos de indexación alternativos para las operaciones de conjuntos de puntos

Question

Es habitual utilizar un índice espacial de cuadro delimitador para mejorar el rendimiento cuando se trabaja con un gran número de características. Cuando se realizan operaciones contra geometrías individuales con un gran número de vértices, ¿existen estrategias de optimización similares?

Por ejemplo, ¿existen estructuras de datos que puedan acelerar las operaciones de punto en polígono o de unión?

Answer 1

OK para Punto en Polígono solamente:

Creo que el problema se basa en la "naturaleza fractal" de los objetos 2d y en la distribución incierta y desequilibrada de la información espacial. Si se dispone de una cuadrícula regular, es fácil calcular la posición o la relación de una celda. Pero una isolínea de un modelo de terreno puede tener partes poco complicadas en un lado y otras matemáticamente complicadas en el otro (partes morfológicamente activas como crestas, valles...).

La indexación trata de manejar dos cosas:

1. Una rutina rápida que te da un conjunto de cubos en los que recoges objetos que puedes distiguir espacialmente (¡los cubos!). Y los BBoxes son fáciles de calcular y de manejar.

2. Un conjunto de relaciones (superposición, tacto) para distinguir o relacionar las cosas espaciales (los objetos).

Desgraciadamente, los BBoxes no le dan ninguna pista sobre cuántos puntos hay en cada BBox, sobre la forma de los objetos (agujeros, convexos, ...) y sobre la distribución local de la información (90% de los puntos en la esquina superior izquierda del BBox). Por lo tanto, usted puede encontrar miembros de la operación rápida en el nivel de los objetos y perder mucho tiempo en la construcción de la relación de la prueba.

Para utilizar un enfoque más irregular, la triangulación de la OMI en combinación con los quadtrees es una de las estrategias, en la que se puede acercar la parte de construcción de cubos y la parte de construcción de relaciones de un índice (bucketing == construcción de relaciones).

Para el ejemplo de Point-in-Polygon-Test es posible construir un caché irregular utilizando:

1. Triangulación delaunay restringida de su cubierta de polímeros, con puntos de malla de borde adicionales para la detección del exterior de la cubierta
2. poner esto en el esquema de indexación quadtree con no más de N triángulos por caja (cubos fractales)
3. encontrar el conjunto de triángulos al que pertenece el punto - la hoja en el quadtree
4. encontrar el triángulo en el que se encuentra el punto (la parte de prueba sobre un máximo de N triángulos)
5. y pide los ID de los polígonos de los vértices del triángulo
6. si el ID es único el punto pertenece al polígono, si no es así queda fuera

El coste de construir la lata y los quadtrees es muy alto y difícil de calcular y el quadtree tiene que equilibrar triángulos grandes y pequeños (triángulos que no caben en cajas de subárbol más pequeñas).

Algunas herramientas y enlaces:

Triángulo - Triangulación de polígono de restricción

Quadtrees - Con ejemplos de fuentes

Repositorio Stony Brook - Estructuras de datos y geometría de disco