Computando o diagrama Voronoi de uma região dentro de uma caixa

Estou enfrentando um problema da seguinte forma: Tenho uma caixa cheia de pontos com uma certa distribuição desconhecida e gostaria de calcular o diagrama de Voronoï. O problema é que o número de pontos é tão grande que isso pode ser impossível para a distribuição completa.

Portanto, planejei fazer isso apenas em uma região dentro da caixa, onde o número de pontos não fosse tão grande. Para fazer isso, preciso saber como calcular a região mínima que pode afetar o diagrama Voronoi de uma determinada região menor dentro dessa caixa.

Em outras palavras, eu gostaria de calcular o diagrama Voronoï dos pontos dentro do pequeno cubo da figura abaixo que se encaixa no diagrama Voronoï que teria os pontos da caixa cheia armazenando o menor diagrama Voronoï possível na memória.

Para calcular o diagrama de Voronoi de conjuntos enormes (> 100 milhões) de pontos, você pode usar o seguinte 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.

O algoritmo é explicado com mais detalhes no meu artigo . Pode ser trivialmente paralelizado (basta adicionar "#pragma omp paralelo para" antes do loop principal), pois não há dependência de dados. Ele é implementado na minha biblioteca de programação GEOGRAM C ++ (junto com uma Kd-Tree com eficiência de memória que pode atingir mais de 100 milhões de pontos). Observe que no GEOGRAM também há uma implementação Delaunay / Voronoi padrão paralela que funciona bem com até 100 milhões de sites.

Com relação à implementação paralela do algoritmo clássico (Boywer-Watson), a implementação do GEOGRAM está documentada aqui (consulte também o arquivo de origem c ++ associado que possui comentários extensos). Não tenho artigo publicado sobre isso, escreverei um se o tempo permitir. A idéia principal é usar spinlocks associados ao tetraedro para garantir que apenas um thread individual possa modificar um tetraedro.

Parece que os especialistas não estão respondendo à sua pergunta, então tentarei fornecer uma idéia. Porém, antes de fazer isso, sugiro fortemente que você procure na literatura alguns métodos sofisticados que já foram desenvolvidos. No entanto, sem garantir que seja uma sugestão boa, rápida ou eficiente, proponho a seguinte metodologia. Lembre-se de que eu cometi alguns erros, por isso não garanto que tudo esteja totalmente correto, mas espero que a idéia do método ofereça uma abordagem que o ajude a resolver seu problema.

Seja o conjunto dos seus pontos em todo o cubo "grande". Corrija seu cubo "pequeno" em algum lugar do cubo grande e deixe ser o conjunto de pontos contidos em , ou seja, Inicialmente, defina .C V C C V C = V ∩ C . V ′ C = V $V$$C$$V_C$$C$$V_C = V \cap C.$$V'_C=V_C$

Etapa 1: Gere o diagrama Voronoi . Para cada ponto denota por sua célula Voronoi, que é um poliedro convexo em três espaços. Além disso, denote por os vértices da célula de Voronoi centralizados em e por os vértices de todos os Voronoi células do diagrama de Voronoi .v ∈ V ' C V o r ( v ) W ( v ) v ∈ V « C W ( V ' C ) = ∪ v ∈ V « C W ( v ) V o R ( V ′ C$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)$

Etapa 2: todos os pontos de e todos os vértices de Voronoi branco. W ( V ′ C$V'_C$$W(V'_C)$

Etapa 3: para cada vértice de Voronoi desenhe a esfera de Delaunay centrada em , que é a esfera com centro e raio de distância entre e um dos pontos de cuja célula Voronoi possui como um vértice (não importa em que ponto, existem vários, mas o resultado é sempre o mesmo).w w w V ′ C$w \in W(V'_C)$$w$$w$$w$$V'_C$$w$

Caso 3.1. Se a esfera Delaunay de estiver contida no cubo , cor preto.C $w$$C$$w$

Caso 3.2 Se a esfera de Delaunay não estiver contida no cubo mas não contiver nenhum ponto de em seu interior (aberto), preto o ponto .V $C$$V$$w$

Caso 3.3. Se a esfera Delaunay de conter pontos de no seu interior (aberto), (1) adicionar os pontos de contido no interior da esfera para o conjunto e (2) manter a cor do ponto de branco . V V V ′ C$w$$V$$V$$V'_C$$w$

Etapa 4: para cada ponto verifique se todos os vértices Voronoi de sua célula Vornoi estão pretos. Se nem todos forem pretos, mantenha a cor branco. Se eles são pretos, cor preto. W ( v ) v $v \in V'_C$$W(v)$$v$$v$

Etapa 5: verifique se todos os pontos do conjunto original são pretos.$V_C$

Caso 5.1. Se eles são todos preto, o diagrama de Voronoi restrito ao cubo é a parte local da global de Voronoi diagrama restrito a . Fim.C V o R ( V ) $Vor(V'_C)$$C$$Vor(V)$$C$

Caso 5.2. Se houver vértices brancos em , volte para a Etapa 1. Na Etapa 1, ao gerar o novo diagrama de Voronoi , as células de Voronoi mantêm as células pretas em torno dos pontos pretos de iguais, mantendo todas as pretas Voronoi vértices de e faz alteração apenas em relação aos brancos. V o R ( V ' C ) V ' C W ( V ' C$V_C$$Vor(V'_C)$$V'_C$$W(V'_C)$

Eu espero que isso ajude.

A maneira mais simples de fazer isso é cercar sua caixa inerte com uma caixa maior que contenha pelo menos todos os vizinhos mais próximos dos pontos dentro de sua caixa interna. Observe que haverá um problema quando a caixa interna estiver próxima à borda da caixa de dados abrangente: você não possui pontos externos.

Calcular um mosaico de Voronoi / Delaunay pode ser mais sutil do que você imagina. Uma das questões é como decidir com precisão se um ponto está de um lado ou de outro de um plano / linha de mosaico.

Existe a biblioteca C ++ "CGAL" muito completa para fazer isso em http://www.cgal.org/ . Meus colegas e eu usamos isso em vários trabalhos publicados em astrofísica: parece ser sólido em lidar com todas as armadilhas potenciais na criação desses mosaicos.

Entendo sua pergunta como: Quero desenhar o diagrama de Voronoi para um subconjunto de pontos, de modo que seja o mesmo que é obtido quando se considera o conjunto completo de pontos. Os diagramas de Voronoi são desenhados juntando-se primeiro aos pontos vizinhos e depois desenhando um plano perpendicular à linha no ponto médio. Você faz isso para todos os vizinhos mais próximos e possui um diagrama de voronoi na vizinhança de um ponto. Faça isso para todos os pontos e você terá um diagrama voronoi para todos os pontos. Veja bem, os diagramas de voronoi são definidos localmente. Não há segundo segundo vizinho mais próximo ou terceiro efeito de vizinho mais próximo. Apenas o primeiro efeito vizinho mais próximo. Então, tudo o que você precisa fazer para obter um diagrama de voronoi com um subconjunto de pontos é identificar os pontos na sub-região de interesse, conectá-los a todos os respectivos vizinhos mais próximos, e desenhe um plano passando pelos pontos médios desse segmento de linha e perpendicular ao segmento de linha. Este diagrama será o mesmo para uma região local, independentemente de você considerar uma sub-região ou uma região completa.

Sugiro que você tenha uma abordagem visual e intuitiva usando o Grasshopper for Rhinoceros3D. Embora o Rhinoceros seja um pacote CAD comercial e o Grasshopper seja um plug-in para ele, você pode executar plug-ins gratuitamente, sem limitações e fazer seus experimentos (o Rhino3D sem licença limita apenas o salvamento dos arquivos Rhino). O Grasshopper inclui um grande número de funções matemáticas usadas em uma tela, e os diagramas de Voronoi 3D são um deles.