8

球を形成する3D空間に点のセット（100万、おそらく将来的には1000万または100億）があり（それらは球を埋めます-それらは表面だけではありません）、私はしたいです各球を最初の隣接球に接続する四面体を構築するには...四面体化を探して、これまでのところ、私が見つけたのは次のとおりです。

  • メッシングのアルゴリズムですが、私が理解している限り、それらは空のスペースを埋めますが、私のポイントは固定されています。
  • まったく無関係な表面表示のアルゴリズム
  • 3D 画像を表示するためのアルゴリズム (主に医療分野) : これはより近いですが、うまくいきません。

これどうやってするの？

2014-08-09 まず、ご提案いただきありがとうございます。私は - そして今も - 休暇中で、誰かが答えたかどうかを確認するためにちょうど通りかかっていました... 私はがっかりしていません!!!! :-) 最初に CGAL を試してみて、そこから様子を見ようと思います。O(n2) 内の同じ点のセットに関する他のデータ計算があり、それは約 1 週間続くと予想されるため、数時間はそれほど悪くはありません。分は夢が叶うでしょう！

4

2 に答える 2

1

3 空間でDelaunay 三角形分割アルゴリズムを探しているようです。

1 億点の Delaunay 三角形分割にはかなりの時間がかかるため、しばらくお待ちください。

qhullには n 次元 Delaunay 実装があり、試すことができます。CGALもそうです。どちらのパッケージも、O(n log(n)) 漸近時間で Delaunay 三角形分割を計算します。CGAL は、ジオメトリ カーネルを適切に選択することで、数値的に堅牢な方法で計算できます。(つまり、不正確な算術演算によって不確かな結果が生じる計算では、正確な算術演算に自動的に切り替えることができます。)

2 次元であっても、高速な Delaunay 三角形分割を自分で実装しようとすることはお勧めしません。算術の結果に基づいて述語を評価する必要がある場合、恐ろしいことが起こる可能性があります。

于 2014-08-03T22:50:22.953 に答える
0

プロジェクトの 1 つにtetgenを使用して、四面体化を行います。それは非常にうまく機能し、十分に高速です

于 2015-07-22T14:49:16.137 に答える