7

3D 空間の頂点の配列によって定義される凸多角形 (面) の配列によって定義される閉じた凸多面体があります。密度が一様であると仮定して、多面体の重心を見つけようとしています。現時点では、この疑似コードのアルゴリズムで計算しています。

public Vector3 getCentroid() {
    Vector3 centroid = (0, 0, 0);
    for (face in faces) {
        Vector3 point = face.centroid;
        point.multiply(face.area());
        centroid.add(point);
    }
    centroid.divide(faces.size());
    return centroid;
}

これは基本的に、顔の重心の加重平均を取ります。オンラインで正しいアルゴリズムを見つけることができなかったので、これが正しいと 100% 確信しているわけではありません。誰かが私のアルゴリズムを確認するか、正しいアルゴリズムを参照していただければ幸いです。

ありがとう。

[編集]

ここに、重心を見つけるために使用している実際の Java コードを示します。多面体をピラミッドに分割し、多面体内の任意の点に収束します。ピラミッド重心の加重平均は、次の式に基づいています。

C all =すべてのピラミッドの合計(Cピラミッド* ボリュームピラミッド) /すべてのボリューム

これが（コメント の多いコード）です：

    // Compute the average of the facial centroids.
    // This gives an arbitrary point inside the polyhedron.
    Vector3 avgPoint = new Vector3(0, 0, 0);
    for (int i = 0; i < faces.size(); i++) {
        avgPoint.add(faces.get(i).centroid);
    }
    avgPoint.divide(faces.size());

    // Initialise the centroid and the volume.
    centroid = new Vector3(0, 0, 0);
    volume = 0;

    // Loop through each face.
    for (int i = 0; i < faces.size(); i++) {
        Face face = faces.get(i);

        // Find a vector from avgPoint to the centroid of the face.
        Vector3 avgToCentroid = face.centroid.clone();
        avgToCentroid.sub(avgPoint);

        // Gives the unsigned minimum distance between the face and a parallel plane on avgPoint.
        float distance = avgToCentroid.scalarProjection(face.getNormal());

        // Finds the volume of the pyramid using V = 1/3 * B * h
        // where:   B = area of the pyramid base.
        //          h = pyramid height.
        float pyramidVolume = face.getArea() * distance / 3;

        // Centroid of a pyramid is 1/4 of the height up from the base.
        // Using 3/4 here because vector is travelling 'down' the pyramid.
        avgToCentroid.multiply(0.75f);
        avgToCentroid.add(avgPoint);
        // avgToCentroid is now the centroid of the pyramid.

        // Weight it by the volume of the pyramid.
        avgToCentroid.multiply(pyramidVolume);

        volume += pyramidVolume;
    }

    // Average the weighted sum of pyramid centroids.
    centroid.divide(volume);

ご不明な点がございましたら、お気軽にお問い合わせください。または、表示されたエラーをご指摘ください。

4

2 に答える 2

8

一般に、それは多面体の構造に依存します。次の 4 つのケースが考えられます。

  • 重みを持つのは頂点のみです。つまり、多面体は点のシステムです。次に、すべてのポイントの加重合計の平均値を計算できます。

    r_c = sum(r_i * m_i) / sum(m_i)

    r_ii 番目の頂点を表すベクトルは次のとおりですm_i。その質量です。質量が等しい場合は、より単純な式が得られます。

    r_c = sum(r_i) / n

    n頂点の数はどこにありますか。両方の合計がベクトル化されていることに注意してください。

  • 重みを持つのは辺だけであり、多面体は本質的に死体です。このケースは、各エッジをエッジの真ん中に位置し、エッジ全体の重みを持つ頂点に置き換えることで、前のケースに減らすことができます。

  • 顔だけに重みがあります。このケースも最初のケースに減らすことができます。各面は 2D 凸面図形であり、その重心を見つけることができます。各面をその重心で置き換えると、このケースが最初のケースになります。

  • 固体多面体（あなたの場合、「一様な密度を仮定する」から推測）。この問題には、より複雑なアプローチが必要です。最初のステップは、多面体を四面体に分割することです。これを行う方法の簡単な説明を次に示します。四面体の重心は、すべての中央線が交差する点に位置します。(四面体の中央値は、その頂点と反対面の重心を結ぶ線です。) 次のステップは、パーティション内の各四面体をその重心で置き換えることです。そして最後のステップは、結果として得られる重み付けされたポイントのセットの重心を見つけることです。これはまさに最初のケースです。

于 2012-02-17T09:32:39.150 に答える
2

固体の場合、多面体を四面体化しようとするよりもはるかに簡単な方法があります (これには落とし穴があります)。

これは疑似的なJavaっぽいコードです（適切なVector3実装を前提としています）：

// running sum for total volume
double vol = 0;
// running sum for centroid
Vector3 centroid = (0, 0, 0);
for each triangle (a,b,c)
{
  // Compute area-magnitude normal
  Vector3 n = (b-a).cross(c-a);
  vol += a.dot(n)/6.;
  // Compute contribution to centroid integral for each dimension
  for(int d = 0;d<3;d++)
    centroid[d] += n[d] * ((a[d]+b[d])^2 + (b[d]+c[d])^2 + (c[d]+a[d])^2);
}
// final scale by inverse volume
centroid *= 1./(24.*2.*vol);

三角形よりも次数の高い面がある場合は、ファンを使用して簡単に三角形分割することができ、これは引き続き機能することに注意してください。

これは、多面体が凸でない場合でも便利に機能します。

matlabコードも投稿しました

于 2014-02-18T20:36:33.933 に答える