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

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

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

OK solo para Punto en Polígono:

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

La indexación trata de manejar dos cosas:

1. Una rutina rápida que le proporciona un conjunto de cubos en el que recopila objetos que puede distinguir espacialmente (¡los cubos!). Y los BBoxes son fáciles de calcular y manejar.

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

Desafortunadamente, BBoxes no le dará idea, cuántos puntos hay en cada BBox, cómo se forman los objetos (agujeros, convexos, ...) y cómo se distribuye localmente la información (90% de los puntos en la esquina superior izquierda de la BBox). Por lo tanto, puede encontrar miembros de operación rápida en el nivel de objeto y perder mucho tiempo en la construcción de relaciones de la prueba.

Para utilizar un enfoque más irregular, la triangulación de la OMI en combinación con y cuadrícula es una de las estrategias, donde puede acercar la parte de creación de índices y la creación de relaciones de un índice (creación de relaciones = almacenamiento).

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

1. ! triangulación de Delaunay restringida de su cubierta de polietileno, con puntos de malla de borde adicionales para la detección fuera de la cubierta
2. pon esto en un esquema de indexación de árbol cuádruple 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 árbol cuádruple
4. encuentre el triángulo en el que se encuentra el punto (la parte de prueba sobre máx. N triángulos)
5. y solicite las ID de polígono de los vértices del triángulo
6. si la ID es única, el punto pertenece al polígono, si no está fuera

El costo de construir la lata y los cuadrúpedos es muy alto y difícil de calcular, y el cuadrilátero tiene que equilibrar triángulos grandes y pequeños (triángulos que no caben en cuadros de subárbol más pequeños).

Algunas herramientas y enlaces:

Triángulo: triangulación de polígono de restricción

Quadtrees - Con ejemplos fuente

Repositorio de Stony Brook: estructuras de datos y geometría de disco