Algoritmo para calcular um diagrama Voronoi em uma esfera?

StackOverflow https://stackoverflow.com/questions/545870

Pergunta

Estou procurando um algoritmo simples (se existe) para encontrar o diagrama de Voronoi para um conjunto de pontos na superfície de uma esfera. O código -fonte seria ótimo. Eu sou um homem Delphi (sim, eu sei ...), mas como o código C também.

Foi útil?

Solução

Aqui está um artigo sobre Diagramas esféricos de voronoi.

Ou se você se destacar (Bleah!) esse site.

Outras dicas

Atualização em julho de 2016:

Graças a vários voluntários (especialmente Nikolai Nowaczyk e I), agora há um código muito mais robusto / correto para lidar com diagramas de voronoi na superfície de uma esfera em Python. Isso está oficialmente disponível como scipy.spatial.SphericalVoronoi da versão 0.18 de Scipy em diante. Há um exemplo funcional de uso e plotagem no oficial documentos.

O algoritmo segue a complexidade do tempo quadrático. Embora o LogLinear seja o ótimo teórico para os diagramas de voronoi nas superfícies das esferas, atualmente é o melhor que conseguimos implementar. Se você deseja saber mais e ajudar com o esforço de desenvolvimento, existem alguns problemas abertos relacionados à melhoria da maneira como o Python lida com os diagramas esféricos de voronoi e as estruturas de dados relacionadas:

Para obter mais informações sobre a teoria / desenvolvimento / desafios relacionados a este código Python e esforços relacionados à geometria computacional, você também pode conferir algumas palestras de Nikolai e eu:

Resposta original:

Na verdade, escrevi recentemente algum código Python de código aberto para diagramas de Voronoi na superfície de uma esfera: https://github.com/tylerjereddy/py_sphere_voronoi

O uso, o algoritmo e as limitações são documentados no ReadThEdocs (http://py-sphere-voronoi.readthedocs.org/en/latest/voronoi_utility.html). Existem alguns exemplos detalhados lá, mas também colocarei um ou dois abaixo. O módulo também lida com o cálculo das áreas de superfície da região de Voronoi, embora com algumas fraquezas numéricas na versão atual de desenvolvimento.

Não vi muitas implementações de código aberto bem documentadas para os diagramas esféricos de Voronoi, mas houve um pouco de zumbido sobre a implementação do JavaScript no site de Jason Davies (http://www.jasondavies.com/maps/voronoi/). Eu não acho que o código dele esteja aberto. Eu também vi um post sobre o uso do Python para lidar com parte do problema (http://jellymatter.com/2014/01/29/voronoi-tessellation-on-the-surface-of-a-sphere-python-code/). Muitas das fontes primárias de literatura citadas nas postagens acima pareciam muito difíceis de implementar (tentei algumas delas), mas talvez algumas pessoas achem minha implementação útil ou até sugerisse maneiras de melhorá -lo.

Exemplos:

1) Produza um diagrama de Voronoi para um conjunto de pontos pseudo-aleatórios na esfera da unidade:

import matplotlib
import matplotlib.pyplot as plt
import matplotlib.colors as colors
from mpl_toolkits.mplot3d import Axes3D
from mpl_toolkits.mplot3d.art3d import Poly3DCollection
import numpy as np
import scipy as sp
import voronoi_utility
#pin down the pseudo random number generator (prng) object to avoid certain pathological generator sets
prng = np.random.RandomState(117) #otherwise, would need to filter the random data to ensure Voronoi diagram is possible
#produce 1000 random points on the unit sphere using the above seed
random_coordinate_array = voronoi_utility.generate_random_array_spherical_generators(1000,1.0,prng)
#produce the Voronoi diagram data
voronoi_instance = voronoi_utility.Voronoi_Sphere_Surface(random_coordinate_array,1.0)
dictionary_voronoi_polygon_vertices = voronoi_instance.voronoi_region_vertices_spherical_surface()
#plot the Voronoi diagram
fig = plt.figure()
fig.set_size_inches(2,2)
ax = fig.add_subplot(111, projection='3d')
for generator_index, voronoi_region in dictionary_voronoi_polygon_vertices.iteritems():
   random_color = colors.rgb2hex(sp.rand(3))
   #fill in the Voronoi region (polygon) that contains the generator:
   polygon = Poly3DCollection([voronoi_region],alpha=1.0)
   polygon.set_color(random_color)
   ax.add_collection3d(polygon)
ax.set_xlim(-1,1);ax.set_ylim(-1,1);ax.set_zlim(-1,1);
ax.set_xticks([-1,1]);ax.set_yticks([-1,1]);ax.set_zticks([-1,1]); 
plt.tick_params(axis='both', which='major', labelsize=6)

enter image description here

2) Calcule as áreas de superfície dos polígonos da região de Voronoi e verifique se a área de superfície reconstituída é sensata:

import math
dictionary_voronoi_polygon_surface_areas = voronoi_instance.voronoi_region_surface_areas_spherical_surface()
theoretical_surface_area_unit_sphere = 4 * math.pi
reconstituted_surface_area_Voronoi_regions = sum(dictionary_voronoi_polygon_surface_areas.itervalues())
percent_area_recovery = round((reconstituted_surface_area_Voronoi_regions / theoretical_surface_area_unit_sphere) * 100., 5)
print percent_area_recovery
97.87551 #that seems reasonable for now

Observe que a Triangulação Delaunay em uma esfera é apenas o casco convexo. Assim, você pode calcular o casco convexo 3D (por exemplo, usando CGAL) e tomar o dual.

Há um artigo de Inria sobre a Triangulação de Delaunay (DT) de pontos deitados em uma esfera: Caroli, Manuel, et al. Delaunay triangulações robustas e eficazes de Delaunay em ou perto de uma esfera. 2009. onde eles falam sobre uma implementação em CGAL.

O artigo refere -se a várias implementação disponível dos algoritmos DT.

Citando do artigo:

Uma resposta fácil e padrão consiste em calcular o casco convexo 3D dos pontos, o que é notoriamente equivalente.

Para calcular o casco convexo, o artigo sugere:

  1. Hull, um programa para cascos convexos.
  2. Qhull.
  3. Cascos convexos tridimensionais. em fortran.three-dimensional convexo casco.
  4. Stripack em fortran.

A classe dt c ++ de CGAL tem o método dual Para obter o diagrama de Voronoi.

De acordo com esta postagem Por Monique Teillaud (um dos autores do artigo acima mencionado), parece -me que em novembro de 2012 a implementação ainda não estava pronta.

Já faz um tempo desde que a pergunta foi respondida, mas encontrei dois artigos que implementam Algoritmo da Fortune (Eficiência O (n lg n), memória O (n)) sobre a superfície da esfera. Talvez um futuro espectador ache essas informações úteis.

Estou trabalhando com eles eu mesmo no momento, então não posso explicar bem. A idéia básica é que o algoritmo da Fortune funcione na superfície da esfera, desde que você calcule as parábolas delimitadoras dos pontos corretamente. Como a superfície da esfera envolve, você também pode usar uma lista circular para conter a linha da praia e não se preocupar com o manuseio de células na borda do espaço retangular. Com isso, você pode varrer do Pólo Norte da esfera para o sul e voltar novamente, pulando para sites que introduzem novos pontos na linha da praia (adicionando uma parábola à linha da praia) ou a introdução de vértices celulares (removendo um parábola da linha da praia).

Ambos os trabalhos esperam um alto nível de conforto com a álgebra linear para entender os conceitos, e ambos continuam me perdendo no ponto em que começam a explicar o próprio algoritmo. Infelizmente, não fornecem código -fonte.

Eu acho que o plano Voronoi para cada ponto pode ser construído usando geometria não euuclidiana. O que normalmente era uma linha em um avião 2D agora é um 'grande círculo' na esfera (veja a Wikipedia:Geometria elíptica). É fácil descobrir quais pontos estão do lado errado de qualquer grande círculo entre dois pontos, simplesmente girando a esfera, de modo que o grande círculo dividido é o equador, e então são todos os pontos no outro hemisfério além do ponto em que você está Construindo o plano Voronoi para.

Esta não é a resposta inteira, mas é aqui que eu começaria ..

Há um bom programa de exemplo de diagrama de Voronoi aqui (incluindo código -fonte para Delphi 5/6).

Eu acho que "pontos na superfície de uma esfera" significa que você primeiro precisa remapear-os para coordenadas 2D, criar o diagrama de voronoi e depois remapear-os para esfera as coordenadas de superfície. São as duas fórmulas de Artigo de mapeamento UV da Wikipedia trabalhando aqui?

Observe também que o diagrama de Voronoi terá a topologia errada (está dentro de um retângulo e não "envolve"), aqui pode ajudar a copiar todos os pontos de (0,0)-(x, y) para o vizinho regiões acima (0, -y * 2)-(x, 0), abaixo (0, y)-(x, y * 2), esquerda (-x, 0)-(0, y) e direita (x, 0)-(x*2, y). Espero que você saiba o que quero dizer, fique à vontade para perguntar :)

CGAL está trabalhando no pacote "kernel esférico", que permitiria calcular exatamente esse tipo de coisa. Infelizmente, ainda não foi lançado, mas talvez esteja no próximo lançamento, já que eles já mencionou isso em uma palestra do Google Tech em março

Citando esta referência: http://www.qhull.org/html/qdelaun.htm

Para calcular a triangulação de Delaunay em uma esfera, calcule seu casco convexo. Se a esfera for a esfera da unidade na origem, as normais da faceta são os vértices de Voronoi da entrada.

Se seus pontos estiverem dentro de um hemisfério, você poderá fazer uma projeção gnomônica de coordenadas esféricas para planares e, em seguida, triangular, já que os grandes círculos se tornam linhas retas de menor distância.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top