Centroide de poliedro convexo

Question

Tengo un poliedro convexo cerrado que se define mediante una matriz de polígonos (caras) convexos que se definen mediante matrices de vértices en el espacio 3D. Estoy tratando de encontrar el centroide del poliedro, suponiendo una densidad uniforme. Por el momento lo calculo con el algoritmo en este pseudo-código.

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; 
} 

Esto esencialmente toma el promedio ponderado de los centroides de las caras. No estoy 100% seguro de que esto sea correcto ya que no he podido encontrar un algoritmo correcto en línea. Si alguien pudiera confirmar mi algoritmo o referirme a uno correcto, lo agradecería.

Gracias.

---

[EDIT]

Así que aquí es el código Java real que estoy utilizando para encontrar el centro de gravedad. Rompe el poliedro en pirámides que convergen en un punto arbitrario dentro del poliedro. El promedio ponderado para los centroides de la pirámide se basa en la siguiente fórmula.

C _todo = SUM _{todas las pirámides} (C _pirámide * volumen _pirámide)/volumen _todo

Aquí está el (fuertemente código comentado):

// 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); 

No dude en hacerme cualquier pregunta que pueda tener ab sacarlo o señalar cualquier error que vea.

Answer 1

Generalmente, eso depende de la estructura de su poliedro. Hay 4 casos posibles:

• Solo los vértices tienen peso, es decir, su poliedro es el sistema de puntos. A continuación, sólo se puede calcular el valor medio de la suma ponderada de todos los puntos:

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

  Aquí r_i es el vector que representa el vértice i-ésimo, m_i - su masa. Caso de masas iguales nos deja con la fórmula más sencilla:

  r_c = sum(r_i)/n 
  

  Dónde n es el número de vértices. Tenga en cuenta que ambas sumas están vectorizadas.

• Solo los bordes tienen peso, y el poliedro es esencialmente una carcasa. Este caso se puede reducir al anterior sustituyendo cada borde con vértice situado en el medio del borde y teniendo el peso de todo el borde.

• Solo las caras tienen peso. Este caso se puede reducir al primero también. Cada cara es una figura convexa 2D, de la cual se puede encontrar el centroide. Sustituir cada cara con su centroide lleva este caso al primero.

• Poliedro sólido (su caso, infiriendo del "suponiendo densidad uniforme"). Este problema requiere un enfoque más complicado.El primer paso es dividir el poliedro en tetraedros. Aquí está el short description sobre cómo hacer esto. Para un centroide de tetraedro se encuentra en el punto donde todas sus medianas se cruzan. (La mediana de un tetraedro es la línea que conecta su vértice y el centroide de la cara opuesta). El siguiente paso es sustituir cada tetraedro en la partición con su centroide. Y el último paso es encontrar el centroide del conjunto resultante de puntos ponderados, que es exactamente el primer caso.

Answer 2

Para el caso sólido, hay una gran parte simpler method de tratar de tetrahedralize poliedro (que tiene pitfalls).

Aquí es código de pseudo-ish java-ish (suponiendo aplicación decente 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); 

Nota, si usted tiene caras grado más alto que los triángulos se puede triangular trivialmente con un ventilador y esto seguirá funcionando.

Esto funciona convenientemente incluso si el poliedro no es convexo.

También he publicado matlab code