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

17

Es común utilizar un índice espacial de cuadro delimitador para mejorar el rendimiento cuando se trabaja con un gran número de entidades. 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 el punto en el polígono u operaciones de unión?

    
pregunta Matthew Snape 23.07.2012 - 14:24

1 respuesta

2

Aceptar 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 isolínea de un modelo de terreno puede tener partes no complicadas en el lado opuesto y matemáticamente complicadas en el otro lado (partes morfológicamente activas como crestas, valles ...).

La indexación intenta manejar dos cosas:

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

  2. Un conjunto de relaciones (superposición, toque) para distinguir o relacionar la materia espacial (los objetos).

Desafortunadamente, los BBoxes no te darán una pista, cuántos puntos hay en cada BBox, cómo se forman los objetos (agujeros, convexos, ...) y cómo la información se distribuye localmente (90% de los puntos en la parte superior izquierda esquina del BBox). Por lo tanto, puede encontrar miembros de operaciones rápidas en el nivel del objeto y perder muchas veces en la construcción de la relación de la prueba.

Para utilizar un enfoque más irregular, la triangulación de IMO en combinación con y quadtrees es una de las estrategias en las que puede acercar el agrupamiento y la relación de construcción de un índice (agrupamiento == construcción de relación).

Para el ejemplo de prueba de punto en polígono, es posible construir un caché irregular usando:

  1. ! triangulación delaunay restringida de su cubierta de polietileno, con puntos de malla de borde adicionales para la detección fuera de la cubierta
  2. ponga esto en el esquema de indexación de quadtree con no más de N triángulos por caja (cubos fractales)
  3. encuentre el conjunto de triángulos al que pertenece el punto - la hoja en el quadtree
  4. encuentre el triángulo en el que se encuentra el punto (la parte de prueba sobre los triángulos N máximos)
  5. y solicite los ID de polígono de los vértices de triángulos
  6. si el ID es único, el punto pertenece al polígono, si no está fuera

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

Algunas herramientas y enlaces:

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

Quadtrees - Con ejemplos de fuentes

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

    
respondido por el huckfinn 29.01.2014 - 10:52

Lea otras preguntas en las etiquetas