6

凸多面体 (3D) の頂点の位置を考えると、多面体の重心と体積を計算する必要があります。次のコードは、Mathworks サイトで入手できます。

function C = centroid(P)
k=convhulln(P);
if length(unique(k(:)))<size(P,1)
    error('Polyhedron is not convex.');
end
T = delaunayn(P);
n = size(T,1);
W = zeros(n,1);
C=0;
for m = 1:n
    sp = P(T(m,:),:);
    [null,W(m)]=convhulln(sp);
    C = C + W(m) * mean(sp);
end
C=C./sum(W);
return
end

コードはエレガントですが、非常に遅いです。何千もの多面体の体積と重心を何百回も計算する必要があります。このコードを現在の状態で使用することは現実的ではありません。誰かがより良いアプローチを知っていますか、またはこのコードをより速くすることができますか? mean意味の表現に置き換えるなど、私が考えることができるいくつかの小さな変更があります。

4

3 に答える 3

3

最小限の労力でボリュームを計算するためのはるかに簡単な方法があります。最初のフレーバーは、多面体の 3 つのローカル トポロジ情報セット、エッジの接線単位ベクトル、この接線の面内法線の単位ベクトル、およびファセット自体の単位ベクトルを使用します (これらは、から抽出するのが非常に簡単です)。頂点)。詳細については、多面体の体積を参照してください。

2 番目のフレーバーは、顔の領域、法線ベクトル、および顔の重心を使用して、このウィキペディアの記事に従って多面体の体積を計算します。どちらのアルゴリズムも単純で実装が非常に簡単で、単純な加算構造によりベクトル化も簡単です。どちらのアプローチも、本格的な多面体のテッセレーションを行うよりもはるかに高速になると思います。

多面体の重心は、発散定理を適用して、多面体のボリューム全体にわたる積分を多面体表面にわたる積分に変換することによって計算できます。詳細な説明は、3d での多面体の体積と重心の計算にあります。多面体の三角形へのテッセレーションが本当に必要かどうか、または多面体のより複雑なポリゴン サーフェスでも機能するかどうかは確認しませんでしたが、いずれにせよ、面のエリア テッセレーションはボリューム テッセレーションよりもはるかに単純です。全体として、このような複合アプローチは、ボリューム アプローチよりもはるかに高速になるはずです。

于 2013-11-12T15:57:17.250 に答える
1

正確な解決策が必要な場合は、 quickhullが十分でない場合に唯一のオプションを考えることはcudahull です。ただし、それでも最大で約 40 倍の増加しか得られません (らしい)。

作成する凸包にはそれぞれ少なくとも 10 個の頂点があると想定しています (それよりはるかに少ない場合、できることはあまりありません)。「十分に近い」ソリューションを気にしない場合。ポリゴンごとの頂点数を制限するバージョンのクイックハルを作成できます。計算を制限する頂点の数により、必要に応じて最大誤差の計算も可能になります。

問題は、凸包の頂点の数が無限に近づくと、最終的に球体になるということです。これは、クイック ハルの動作方法により、凸包に追加する各頂点の効果*が、その前のものよりも少ないことを意味します。

*quickhull のコーディング方法によっては、これは一般的な意味でのみ当てはまる場合があります。実際にこれを実現するには、quickhull の再帰アルゴリズムを変更する必要があるため、「次の頂点」は常に計算されますが (最後の頂点が追加された後、またはそのセクションにポイントが残っていない場合を除く)、頂点は実際には凸包に追加されます。多面体の体積の増加を最大化する順序 (最も遠いものから最も遠いものへの順序である可能性が高い)。頂点を追加する順序を追跡するためにいくらかのパフォーマンス コストが発生しますが、保留中の凸包ポイントと保留中のポイントの比率が十分に高い限り、それだけの価値があります。エラーに関しては、実際の凸包に到達したときにアルゴリズムを停止するのがおそらく最善の選択肢です。または、ボリュームの最大増加が、現在の合計ボリュームの特定の割合よりも小さくなります。パフォーマンスがより重要な場合は、ポリゴンごとの凸包ポイントの数を単純に制限します。

さまざまな近似凸包アルゴリズムを調べることもできますが、上で概説した方法は、エラーを判断する機能を備えたボリューム/セントロイド近似でうまく機能するはずです。

于 2013-01-07T00:39:33.317 に答える
0

コードをどれだけ高速化できるかは、セントロイドの計算方法に大きく依存します。オプションの重心計算に関するこの回答を参照してください。立体多面体の重心が必要な場合は、基本的に運が悪いことがわかります。ただし、多面体の頂点のみに重みがある場合は、単純に次のように記述できます。

[k,volume] = convhulln(P);
centroid = mean(P(k,:));
于 2013-01-06T22:56:47.873 に答える