Calcular el diagrama de Voronoi de una región dentro de una caja

Me enfrento a un problema de la siguiente manera: tengo una caja llena de puntos con una cierta distribución desconocida y me gustaría calcular su diagrama de Voronoï. El problema es que la cantidad de puntos es tan grande que puede ser imposible hacerlo para la distribución completa.

Por lo tanto, he planeado hacer eso solo para una región dentro de la caja, donde el número de puntos no era tan grande. Para hacerlo, necesito saber cómo calcular la región mínima que puede afectar al diagrama de Voronoi de cierta región más pequeña dentro de ese cuadro.

En otras palabras, me gustaría calcular el diagrama de Voronoï de los puntos dentro del cubo pequeño de la figura a continuación que se ajusta al diagrama de Voronoï que tendría los puntos de la caja llena almacenando el diagrama de Voronoï más pequeño posible en la memoria.

Para calcular el diagrama de Voronoi de grandes conjuntos de puntos (> 100 millones), puede usar el siguiente algoritmo:

1) create a kd-tree with all the points
2) for each point p [in parallel optionally]
     N = 10
     while not finished
       compute the N nearest neighbors of the point p
       compute the intersection of the N half-spaces defined by p 
       and the neighbors
       if there is a neighbor further away than 
         twice the radius of the ball centered on p and 
         bounding the intersection, finished = true
       N = N * 1.5
  // when exiting the loop, the computed intersection 
  // corresponds to the Voronoi cell of p, because no other bisector
  // can contribute to the Voronoi cell.

El algoritmo se explica con más detalles en mi artículo . Puede ser trivialmente paralelo (simplemente agregue "#pragma omp parallel for" antes del bucle principal), ya que no hay dependencia de datos. Está implementado en mi biblioteca de programación GEOGRAM C ++ (junto con un Kd-Tree eficiente en memoria que escala hasta más de 100 millones de puntos). Tenga en cuenta que en GEOGRAM también hay una implementación estándar paralela de Delaunay / Voronoi que funciona bien con hasta 100 millones de sitios.

Con respecto a la implementación paralela del algoritmo clásico (Boywer-Watson), la implementación de GEOGRAM se documenta aquí (ver también el archivo fuente c ++ asociado que tiene comentarios extensos). No tengo ningún artículo publicado al respecto, escribiré uno si el tiempo lo permite. La idea principal es usar spinlocks asociados con el tetraedro para garantizar que solo un hilo individual pueda modificar un tetraedro.

Parece que los expertos no responden su pregunta, así que intentaré darle una idea. Pero antes de hacerlo, sugiero encarecidamente que busque en la literatura algunos métodos sofisticados que ya se han desarrollado. Sin embargo, sin garantizar que esta sea una sugerencia buena, rápida o eficiente, propongo la siguiente metodología. Tenga en cuenta que es posible que haya cometido algunos errores, por lo que no garantizo que todo sea completamente correcto, pero espero que la idea del método le brinde algún enfoque que lo ayude a resolver su problema.

Deje que sea ​​el conjunto de sus puntos en todo el cubo "grande". Arregle su cubo "pequeño" en algún lugar del cubo grande y deje que sea ​​el conjunto de puntos contenidos en , es decir, Inicialmente establezca .$V$$C$$V_C$$C$$V_C = V \cap C.$$V'_C=V_C$

Paso 1: generar el diagrama de Voronoi . Para cada punto denota por su celda Voronoi, que es un poliedro convexo en tres espacios. Además, denote con los vértices de la celda de Voronoi centrados en y con los vértices de todos los Voronoi células del diagrama de Voronoi .$Vor(V'_C)$$v \in V'_C$$Vor(v)$$W(v)$$v \in V'_C$$W(V'_C) = \cup_{v \in V'_C} W(v)$$Vor(V'_C)$

Paso 2: Colorea todos los puntos de y todos los vértices de Voronoi blancos.$V'_C$$W(V'_C)$

Paso 3: Para cada vértice de Voronoi dibuje la esfera de Delaunay centrada en , es decir, la esfera con centro y radio la distancia entre y uno de los puntos de cuya celda Voronoi tiene como vértice (no importa qué punto, hay varios, pero el resultado es siempre el mismo).$w \in W(V'_C)$$w$$w$$w$$V'_C$$w$

Caso 3.1. Si la esfera de Delaunay de está contenida en el cubo , colorea negro.$w$$C$$w$

Caso 3.2. Si la esfera de Delaunay no está contenida en el cubo pero no contiene ningún punto de en su interior (abierto), colorea el punto negro.$C$$V$$w$

Caso 3.3. Si la esfera de Delaunay de contiene puntos de en su interior (abierto), (1) agregue los puntos de contenidos en el interior de la esfera al conjunto y (2) mantenga el color del punto blanco . $w$$V$$V$$V'_C$$w$

Paso 4: Para cada punto verifique si todos los vértices Voronoi de su celda Vornoi son negros. Si no todos son negros, mantenga el color de blanco. Si son negros, color negro.$v \in V'_C$$W(v)$$v$$v$

Paso 5: Verifique si todos los puntos del conjunto original son negros.$V_C$

Caso 5.1. Si son todo negro, el Voronoi diagrama restringido al cubo es la porción local de la mundial Voronoi diagrama restringido a . Final.$Vor(V'_C)$$C$$Vor(V)$$C$

Caso 5.2. Si hay vértices blancos en , entonces regrese al Paso 1. En el Paso 1, al generar el nuevo diagrama de Voronoi , uno mantiene las celdas de Voronoi alrededor de los puntos negros de igual, mantiene todo negro Voronoi vértices de y hace alteración solo en relación con los blancos. V o r ( V ′ C ) V ′ C W ( V ′ C$V_C$$Vor(V'_C)$$V'_C$$W(V'_C)$

Espero que esto ayude.

La forma más sencilla de hacerlo es rodear su caja interna con una caja más grande que contenga al menos todos los vecinos más cercanos de los puntos dentro de su caja interna. Tenga en cuenta que surgirá un problema cuando el cuadro interno esté cerca del borde del cuadro de datos que lo abarca: no tiene puntos externos.

Calcular un mosaico Voronoi / Delaunay puede ser más sutil de lo que piensas. Una de las cuestiones es cómo decidir con precisión si un punto está en un lado u otro de un plano / línea de teselación.

Existe la muy completa biblioteca C ++ "CGAL" para hacer esto en http://www.cgal.org/ . Mis colegas y yo hemos usado esto en varios artículos publicados en astrofísica: parece ser sólido como una roca para abordar todas las dificultades potenciales en la creación de estas teselaciones.

Entiendo su pregunta como: Quiero dibujar el diagrama de Voronoi para un subconjunto de puntos de modo que sea el mismo que se obtiene al considerar el conjunto completo de puntos. Los diagramas de Voronoi se dibujan uniendo primero los puntos vecinos y luego dibujando un plano perpendicular a la línea en el punto medio. Haces esto para todos los vecinos más cercanos y tienes un diagrama de voronoi cerca de un punto. Haga esto para todos los puntos y tendrá un diagrama de voronoi para todos los puntos. Usted ve, los diagramas voronoi se definen localmente. No hay un segundo efecto de vecino más cercano o tercer vecino más cercano. Solo el primer efecto vecino más cercano. Entonces, todo lo que tiene que hacer para obtener un diagrama voronoi con un subconjunto de puntos es identificar los puntos en la subregión de interés, conectarlos con todos sus vecinos más cercanos respectivos, y dibuje un plano que pase por los puntos medios de este segmento de línea y perpendicular al segmento de línea. Este diagrama será el mismo para una región local, ya sea que considere una subregión o una región completa.

Le sugiero que tenga un enfoque visual e intuitivo utilizando Grasshopper para Rhinoceros3D. Aunque Rhinoceros es un paquete CAD comercial y Grasshopper es un complemento para él, puede ejecutar complementos de forma gratuita sin limitaciones y realizar sus experimentos (Rhino3D sin licencia limita solo el almacenamiento de archivos de Rhino). Grasshopper incluye una gran cantidad de funciones matemáticas utilizadas en un lienzo, y los diagramas 3D Voronoi son una de ellas.