球上のボロノイ図を計算するアルゴリズム?

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

質問

球の表面上の一連の点のボロノイ図を見つけるための単純な (存在する場合) アルゴリズムを探しています。ソースコードは素晴らしいでしょう。私は Delphi 派ですが (はい、わかっています...)、C コードも使います。

役に立ちましたか？

解決

ここで球状ボロノイ図の紙がしています。

それとも、Fortranの（bleah！）を完全に理解場合はこのサイトがありますのます。

他のヒント

2016 年 7 月の更新:

多くのボランティア (特に Nikolai Nowaczyk と私) のおかげで、Python で球面上のボロノイ図を処理するための、より堅牢で正確なコードが作成されました。これは正式に次のように利用可能です scipy.spatial.SphericalVoronoi バージョンから 0.18 scipy以降。公式に使用例とプロットの実例があります ドキュメント.

このアルゴリズムは二次時間計算量に従います。対数線形は球の表面上のボロノイ図にとって理論的には最適ですが、これが現時点で実装できる最善のものです。さらに詳しく知り、開発作業を支援したい場合は、Python が球面ボロノイ図と関連するデータ構造を処理する方法の改善に関連する未解決の問題がいくつかあります。

この Python コードおよび関連する計算幾何学への取り組みに関連する理論/開発/課題の詳細な背景については、ニコライと私の講演もご覧ください。

元の回答:

実は私は最近、球面上のボロノイ図用のオープンソース Python コードをいくつか書きました。 https://github.com/tylerjereddy/py_sphere_Voronoi

使用法、アルゴリズム、および制限事項は、readthedocs (http://py-sphere-voronoi.readthedocs.org/en/latest/voronoi_utility.html）。詳細な例がいくつかありますが、以下に 1 つか 2 つ載せておきます。このモジュールはボロノイ領域の表面積の計算も処理しますが、現在の開発バージョンには数値的な弱点がいくつかあります。

球面ボロノイ図の十分に文書化されたオープンソース実装はあまり見たことがありませんが、Jason Davies の Web サイトで JavaScript 実装について少し話題になっています (http://www.jasondavies.com/maps/voronoi/）。ただし、彼のコードは公開されていないと思います。また、Python を使用して問題の一部に対処することに関するブログ投稿も見ました (http://jellymatter.com/2014/01/29/voronoi-tessellation-on-the-surface-of-a-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

球面上のドロネー三角形分割がちょうど凸包であることに注意してください。 したがって、あなたは、3D凸包を計算することができます（例えばCGALを使用して） デュアルを取ります。

球上にある点のドローネ三角形分割 (DT) に関する INRIA の論文があります。 カローリ、マヌエル、他球上または球に近い点の堅牢かつ効率的なドローネ三角形分割。2009年。 彼らが実装について話している場所 CGAL.

この論文では、DT アルゴリズムの利用可能なさまざまな実装について言及しています。

論文からの引用：

簡単で標準的な回答は、ポイントの3D凸式船体を計算することで構成されています。

論文では、凸包を計算するために次のように提案しています。

  1. Hull、凸包用のプログラム。
  2. ハル.
  3. 3 次元の凸包。 FORTRAN の 3 次元凸包。
  4. ストリップパック フォートランで。

CGAL の DT C++ クラスには次のメソッドがあります。 dual ボロノイ図を取得します。

によると この郵便受け Monique Teillaud (上記の論文の著者の 1 人) によると、2012 年 11 月時点では実装の準備がまだ整っていないようです。

質問に答えてからしばらく時間が経ちましたが、次のことを実装した 2 つの論文を見つけました。 フォーチュンのアルゴリズム 球の表面上の (効率 O(N lg N)、メモリ O(N))。おそらく、将来視聴する人にとって、この情報は役に立つでしょう。

  • Dinis と Mamede による「Sphereing the Sphere」は、2010 年の科学および工学におけるボロノイ図に関する国際シンポジウムで発表されました。で購入できます http://dx.doi.org/10.1109/ISVD.2010.32
  • Zheng らによる「球体のボロノイ テッセレーションのための平面スイープ アルゴリズム」最初のものなので公開されたかどうかはわかりませんが、日付は 2011 年 12 月 13 日です。で無料で入手できます http://www.e-lc.org/tmp/Xiaoyu__Zheng_2011_12_05_14_35_11.pdf

現在、私自身で検討中なので、うまく説明できません。基本的な考え方は、点の境界放物線を正しく計算している限り、Fortune のアルゴリズムは球の表面で機能するということです。球の表面がラップするため、円形リストを使用してビーチラインを含めることもでき、長方形の空間の端にあるセルの処理を気にする必要がなくなります。これにより、球の北極から南にスイープして、再び元に戻り、ビーチ ラインに新しいポイントを導入する (ビーチ ラインに放物線を追加する) か、セル頂点を導入する (ビーチ ラインを削除する) サイトにスキップすることができます。ビーチラインからの放物線）。

どちらの論文も、線形代数の概念を理解するために高度なレベルの快適さを期待していますが、どちらもアルゴリズム自体の説明を始める時点で私を失い続けています。残念ながら、どちらもソースコードは提供していません。

各点のボロノイ平面は非ユークリッド幾何学を使用して構築できると思います。通常は 2 次元平面上の線であったものが、球面上の「大円」になります (Wikipedia を参照:楕円形の幾何学）。2 点間の大円の反対側にある点を見つけるのは簡単です。分割する大円が赤道になるように球を回転させるだけで、すべての点が今いる点とは反対側の半球になります。のボロノイ平面を構築しています。

これがすべての答えではありませんが、ここから始めます。

CGAL は、この種のことを正確に計算できる「球状カーネル」パッケージに取り組んでいます。残念ながら、 まだリリースされていません, 、しかし、おそらくそれは彼らの次のリリースに含まれるでしょう、なぜなら彼らはすでに 3月のGoogle Tech Talkで言及しました

このリファレンスからの引用： http://www.qhull.org/html/qdelaun.htm の

  

は、球面上の点のドロネー三角形分割を計算し、それらの凸包を計算します。球体が原点に単位球である場合、面の法線は、入力のボロノイ頂点である。

あなたのポイントは、一方の半球内にある場合は、

、あなたは偉大-円は最短距離の直線になっているので、座標を平面的、そして三角測量する球状から球心投影を行うことができます。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top