Центроид выпуклого многогранника - PullRequest
Новая
       37

Центроид выпуклого многогранника

7 голосов
/ 17 февраля 2012

У меня есть замкнутый выпуклый многогранник, который определяется массивом выпуклых многоугольников (граней), которые определяются массивами вершин в трехмерном пространстве.Я пытаюсь найти центроид многогранника, предполагая однородную плотность.В настоящий момент я вычисляю это с помощью алгоритма в этом псевдокоде. 

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 все = SUM все пирамиды (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);

Пожалуйста, не стесняйтесьзадайте мне любые вопросы, которые могут у вас возникнуть, или укажите на любые ошибки, которые вы видите.

Ответы [ 2 ]

7 голосов
/ 17 февраля 2012

Обычно это зависит от структуры вашего многогранника. Есть 4 возможных случая:

  • Вес имеют только вершины, т. Е. Ваш многогранник - это система точек. Тогда вы можете просто рассчитать среднее значение взвешенной суммы всех точек: 

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

    Здесь r_i - вектор, представляющий i-ю вершину, m_i - ее массу. Случай равных масс оставляет нам более простую формулу: 

    r_c = sum(r_i) / n

    Где n - количество вершин. Обратите внимание, что обе суммы векторизованы.

  • Только ребра имеют вес, а многогранник по сути является каркасом. Этот случай можно свести к предыдущему, заменив каждое ребро вершиной, расположенной прямо в середине ребра и имеющей вес всего ребра.

  • Вес имеют только лица. Этот случай можно свести и к первому. Каждое лицо представляет собой двумерную выпуклую фигуру, в которой можно найти центроид. Подстановка каждого лица его центроидом приводит этот случай к первому.

  • Сплошной многогранник (ваш случай, выводя из «при условии равномерной плотности» ). Эта проблема требует более сложного подхода. Первый шаг - разделить многогранник на тетраэдры. Вот краткое описание о том, как это сделать. Для тетраэдра центроид расположен в точке, где пересекаются все его медианы. (Медиана тетраэдра - это линия, соединяющая его вершину и центроид противоположной грани.) Следующий шаг - замена каждого тетраэдра в разбиении его центроидом. И последний шаг - найти центр тяжести результирующего набора взвешенных точек, что является точно первым случаем.

2 голосов
/ 19 февраля 2014

Для твердого случая есть гораздо более простой метод , чем попытка тетраэдризации многогранника (который имеет ловушек ).

Вот псевдо-ish java-ishкод (при условии достойной реализации 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

...