Centroide di poliedro convesso

Question

Ho un poliedro convesso chiuso che è definito da una matrice di poligoni convessi (facce) che sono definiti da matrici di vertici nello spazio 3D. Sto cercando di trovare il centroide del poliedro, assumendo una densità uniforme. Al momento lo calcolo con l'algoritmo in questo pseudo-codice.

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

prende questo essenzialmente la media ponderata dei centroidi delle facce. Non sono sicuro al 100% che ciò sia corretto in quanto non sono stato in grado di trovare un algoritmo corretto online. Se qualcuno potesse confermare il mio algoritmo o farmi riferimento a uno corretto, lo apprezzerei.

Grazie.

---

[EDIT]

ecco il codice Java vero e proprio che sto usando per trovare il baricentro. Rompe il poliedro in piramidi che convergono su un punto arbitrario all'interno del poliedro. La media ponderata per i centroidi piramidali si basa sulla seguente formula.

C _tutti = SUM _{tutte le piramidi} (C _piramide * Volume _piramide)/Volume _tutti

Ecco la (pesantemente commentato codice):

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

Non esitate a farmi tutte le domande che potreste avere fuori o segnalare eventuali errori che vedi.

Answer 1

Generalmente ciò dipende dalla struttura del poliedro. Esistono 4 possibili casi:

• Solo i vertici hanno un peso, ovvero il poliedro è il sistema di punti. Poi si può solo calcolare il valore medio della somma ponderata di tutti i punti:

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

  Qui r_i è il vettore che rappresenta il vertice i-esimo, m_i - la sua massa. Caso di masse uguali ci lascia con la formula più semplice:

  r_c = sum(r_i)/n 
  

  Dove n è il numero di vertici. Nota che entrambe le somme sono vettorizzate.

• Solo i bordi hanno un peso e il poliedro è essenzialmente una carcassa. Questo caso può essere ridotto a quello precedente sostituendo ciascun bordo con il vertice situato proprio al centro del bordo e avendo il peso dell'intero bordo.

• Solo i volti hanno un peso. Questo caso può essere ridotto anche al primo. Ogni faccia è una figura convessa 2D, di cui è possibile trovare il centroide. Sostituendo ciascuna faccia con il suo centroide si porta questo caso al primo.

• Poliedro solido (il tuo caso, inferendo dal "assumendo densità uniforme"). Questo problema richiede un approccio più complicato.Il primo passo è dividere il poliedro in tetraedri. Ecco lo short description su come farlo. Per un tetraedro il centroide si trova nel punto in cui tutte le sue mediane si intersecano. (La mediana di un tetraedro è la linea che collega il suo vertice e il centroide della faccia opposta.) Il passo successivo è sostituire ogni tetraedro nella partizione con il suo centroide. E l'ultimo passo è trovare il centroide della serie risultante di punti ponderati, che è esattamente il primo caso.

Answer 2

Per il caso solido, c'è un gran simpler method che cercare di tetrahedralize poliedro (che ha pitfalls).

Ecco il codice pseudo-ish java-ish (assumendo implementazione 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, se avete le facce grado superiore a triangoli si può banalmente triangolare con un ventilatore e questo continuerà a funzionare.

Questo funziona comodamente anche se il poliedro non è convesso.

ho anche postato matlab code