39

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

4

11 に答える 11

12

これは、球面ボロノイ図に関する論文です。

または、Fortran に精通している場合 (ひどい!)、このサイトがあります。

元のリンク (デッド): https://people.sc.fsu.edu/~jburkardt/f_src/sxyz_voronoi/sxyz_voronoi.html

于 2009-02-13T13:34:58.370 に答える
8

球上の Delaunay 三角形分割は単なる凸包であることに注意してください。したがって、3D 凸包を (たとえば CGAL を使用して) 計算し、双対をとることができます。

于 2012-12-20T10:32:38.810 に答える
3

質問に答えてからしばらく経ちましたが、Fortune のアルゴリズム(効率 O(N lg N)、メモリ O(N)) を球の表面に実装する 2 つの論文を見つけました。たぶん、将来の視聴者はこの情報が役立つと思うでしょう.

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

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

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

于 2013-09-23T00:50:08.813 に答える
3

つまり、 NCAR Graphicsのcssgridを試してみてください。codereview.stackexchange.com で、同様の質問に対してより長い回答を書きました。

于 2012-03-19T05:32:46.580 に答える
2

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

これは完全な答えではありませんが、ここから始めます..

于 2009-06-23T21:04:22.553 に答える
1

素敵なボロノイ図のサンプル プログラムがここにあります(Delphi 5/6 のソース コードを含む)。

「球面上の点」とは、最初にそれらを2D座標に再マッピングし、ボロノイ図を作成してから球面座標に再マッピングする必要があることを意味すると思います。ウィキペディアの UV マッピングの記事の 2 つの式はここで機能していますか?

また、ボロノイ図のトポロジーが間違っていることに注意してください (長方形の内側にあり、「ラップ アラウンド」していません)。ここでは、(0,0)-(x, y) からすべてのポイントを隣接するポイントにコピーすると役立ちます。 (0, -y * 2)-(x, 0) より上、(0, y)-(x, y * 2) より下、左 (-x, 0)-(0, y) および右 (x, 0) の領域0)-(x*2, y)。私が言いたいことを理解していただければ幸いです。お気軽にお尋ねください:)

于 2009-02-13T13:20:11.870 に答える
0

ポイントが 1 つの半球内にある場合、大円が最短距離の直線になるため、球座標から平面座標へのノモニック投影を実行してから三角形分割することができます。

于 2011-04-15T18:28:44.423 に答える