구의 보로 노이 다이어그램을 계산하기위한 알고리즘?

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

문제

구의 표면에있는 포인트 세트에 대한 Voronoi 다이어그램을 찾기 위해 간단한 (존재하는 경우) 알고리즘을 찾고 있습니다. 소스 코드가 좋을 것입니다. 나는 델파이 남자입니다 (예, 알고 있습니다 ...). 그러나 나도 C 코드를 먹습니다.

도움이 되었습니까?

해결책

여기에 논문이 있습니다 구형 보로 노이 다이어그램.

또는 당신이 Fortran을 맥주한다면 (Blea!) 이 지역.

다른 팁

2016 년 7 월 업데이트 :

많은 자원 봉사자들 (특히 Nikolai Nowaczyk 및 I) 덕분에 이제 파이썬의 구 표면에 Voronoi 다이어그램을 처리하기위한 훨씬 더 강력한 / 올바른 코드가 있습니다. 이것은 공식적으로 사용할 수 있습니다 scipy.spatial.SphericalVoronoi 버전에서 0.18 Scipy의 이후. 공식적인 사용 및 음모의 예제가 있습니다. 문서.

알고리즘은 2 차 시간 복잡성을 따릅니다. Loglinear는 구의 표면의 Voronoi 다이어그램에 대한 이론적 최적이지만 현재 우리가 구현할 수있는 최고입니다. 더 많은 정보를 찾고 개발 노력에 도움을주고 싶다면 Python이 구형 Voronoi 다이어그램 및 관련 데이터 구조를 처리하는 방식을 개선하는 것과 관련된 몇 가지 공개 문제가 있습니다.

이 파이썬 코드 및 관련 계산 기하학적 노력과 관련된 이론 / 개발 / 과제에 대한 추가 배경을 보려면 Nikolai 및 I의 일부 대화를 확인할 수도 있습니다.

원래 답변 :

실제로 최근에는 구의 표면에 Voronoi 다이어그램에 대한 오픈 소스 파이썬 코드를 작성했습니다. https://github.com/tylerjereddy/py_sphere_voronoi

사용법, 알고리즘 및 제한 사항은 ReadThedocs에 문서화되어 있습니다.http://py-sphere-voronoi.readthedocs.org/en/latest/voronoi_utility.html). 자세한 예가 있지만 아래에 하나 또는 두 개를 배치하겠습니다. 이 모듈은 또한 현재 개발 버전의 수치 적 약점이 있지만 Voronoi 영역 표면 영역의 계산을 처리합니다.

구형 Voronoi 다이어그램에 대한 잘 문서화 된 오픈 소스 구현을 많이 보지 못했지만 Jason Davies 웹 사이트에서 JavaScript 구현에 대해 약간의 화제가있었습니다.http://www.jasondavies.com/maps/voronoi/). 나는 그의 코드가 열려 있다고 생각하지 않습니다. 또한 Python을 사용하여 문제의 일부를 처리하는 것에 대한 블로그 게시물을 보았습니다.http://jellymatter.com/2014/01/29/voronoi-tessellation-o--sphere-python-code/). 위의 게시물에서 인용 된 많은 주요 문헌 출처는 구현하기가 매우 어려워 보였지만 (일부 시도해 보았을 수도 있습니다) 일부 사람들은 내 구현이 유용하거나 개선하는 방법을 제안 할 것입니다.

예 :

1) 단위 구체에서 의사 랜덤 포인트 세트에 대한 보로 노이 다이어그램을 생성합니다.

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) 보로 노이 영역 다각형의 표면적을 계산하고 재구성 된 표면적이 합리적인지 확인하십시오.

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

구의 Delaunay 삼각 측량은 단지 볼록 선체 일뿐입니다. 따라서 3D 볼록한 선체 (예 : CGAL을 사용하여)를 계산하고 듀얼을 사용할 수 있습니다.

INRIA의 DeLaunay 삼각 측량 (DT)에 관한 논문이 구체에 놓여 있습니다. Caroli, Manuel 등. 구체에 또는 가까운 지점의 강력하고 효율적인 delaunay 삼각형. 2009 년. 그들이 구현에 대해 이야기하는 곳 cgal.

이 논문은 DT 알고리즘의 다양한 구현을 의미합니다.

논문에서 인용 :

쉽고 표준적인 답변은 포인트의 3D 볼록 선체를 계산하는 것으로 구성되어 있으며, 이는 악명 높게 동등합니다.

볼록한 선체를 계산하기 위해 종이는 다음을 제안합니다.

  1. 선체, 볼록한 선체 프로그램.
  2. Qhull.
  3. 3 차원 볼록 헐. Fortran.에서 3 차원 볼록한 선체.
  4. Stripack Fortran에서.

CGAL의 DT C ++ 클래스에는 방법이 있습니다. dual 보로 노이 다이어그램을 얻으려면.

에 따르면 이 게시물 Monique Teillaud (위에서 언급 한 논문의 저자 중 한 명)에 의해 2012 년 11 월에 구현이 아직 준비되지 않은 것으로 보인다.

질문에 대한 답변 이후 오랜 시간이 지났지 만 구현하는 두 가지 논문을 찾았습니다. Fortune의 알고리즘 구 표면 위의 (효율 O (n lg n), 메모리 o (n)). 미래의 시청자 가이 정보가 유용하다는 것을 알게 될 것입니다.

나는 지금 그들을 통해 그들을 통해 일하고 있으므로 잘 설명 할 수 없습니다. 기본 아이디어는 포인트의 경계 포물선을 올바르게 계산하는 한 Fortune의 알고리즘이 구의 표면에서 작동한다는 것입니다. 구의 표면은 랩 랩이므로 원형 목록을 사용하여 해변 선을 포함하고 직사각형 공간의 가장자리에 세포를 처리하는 것에 대해 걱정하지 않을 수도 있습니다. 이를 통해 구의 북극에서 남쪽으로 쓸어 넘기고 다시 등을 쓸 수 있습니다. 해변 라인에 새로운 포인트를 도입하는 사이트 (비치 라인에 포물선을 추가) 또는 셀 정점 (a repming a a a reping 비치 라인에서 포물선).

두 논문 모두 선형 대수로 개념을 이해하기 위해 높은 수준의 편안함을 기대하며, 알고리즘 자체를 설명하기 시작한 시점에서 계속 저를 잃어 버립니다. 불행히도 소스 코드도 제공하지 않습니다.

각 지점의 Voronoi 평면은 비 유클리드 형상을 사용하여 구성 할 수 있다고 생각합니다. 일반적으로 2D 비행기의 선은 이제 구의 '큰 원'입니다 (Wikipedia : Wikipedia 참조 :타원 기하학). 큰 원이 적도가되도록 구체를 회전 시켜서 단순히 구체를 회전시켜 두 지점 사이의 큰 원의 반대편에 어떤 점이 있는지 쉽게 찾을 수 있습니다. 보로 노이 비행기를 건설합니다.

이것은 전체 대답이 아니지만 여기서 시작하는 곳입니다 ..

멋진 Voronoi 다이어그램 예제 프로그램이 있습니다 여기 (Delphi 5/6의 소스 코드 포함).

"구의 표면에있는 점"은 먼저 2D 코디네이트로 재발하고 Voronoi 다이어그램을 만들고 구 표면 좌표로 재발해야한다는 것을 의미합니다. 두 가지 공식입니다 Wikipedia UV 매핑 기사 여기서 일 하시나요?

또한 Voronoi 다이어그램은 잘못된 토폴로지를 가질 것이며 (직사각형 내부에 있고 "랩 주위"), 여기서는 (0,0)-(x, y)에서 이웃에게 모든 점을 복사하는 데 도움이 될 수 있습니다. 위의 영역 (0, -y * 2)-(x, 0), 아래 (0, y)-(x, y * 2), 왼쪽 (-x, 0)-(0, y) 및 오른쪽 (x, 0)-(x*2, y). 내가 무슨 뜻인지 알기를 바랍니다. 자유롭게 물어보십시오 :)

cgal "구형 커널"패키지에서 작업하고 있으며, 이는 이러한 종류의 것들을 정확히 계산할 수 있습니다. 안타깝게도, 아직 출시되지 않았습니다, 그러나 아마도 다음 릴리스에있을 것입니다. 3 월 Google Tech Talk에서 언급했습니다

이 참조에서 인용 : http://www.qhull.org/html/qdelaun.htm

구에서 점의 Delaunay 삼각 측량을 계산하려면 볼록한 선체를 계산하십시오. 구가 원점의 단위 구인 경우, 패싯 정상은 입력의 Voronoi 정점입니다.

포인트가 하나의 반구 내에있는 경우 구형에서 평면 좌표로의 Gnomonic 투영을 수행 한 다음 대기업이 가장 짧은 거리의 직선이되기 때문에 삼각 측량을 할 수 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top