Centroid của đa diện lồi

Question

Tôi có một đa diện lồi khép kín được xác định bởi một mảng đa giác lồi (mặt) được xác định bởi mảng các đỉnh trong không gian 3D. Tôi đang cố gắng để tìm thấy trung tâm của đa diện, giả sử mật độ thống nhất. Tại thời điểm này tôi tính toán nó với thuật toán trong mã giả này.

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

Điều này về cơ bản có trọng số trung bình của trọng tâm của khuôn mặt. Tôi không chắc chắn 100% điều này là chính xác vì tôi đã không thể tìm thấy một thuật toán chính xác trực tuyến. Nếu ai đó hoặc có thể xác nhận thuật toán của tôi hoặc giới thiệu tôi đến một chính xác tôi sẽ đánh giá cao nó.

Cảm ơn.

---

[EDIT]

Vì vậy, đây là mã Java thực tế tôi đang sử dụng để tìm ra trọng tâm. Nó phá vỡ đa diện thành kim tự tháp hội tụ trên một điểm tùy ý bên trong đa diện. Trọng số trung bình cho các kim tự tháp centroid dựa trên công thức sau đây.

C _{tất cả} = SUM _{tất cả các kim tự tháp} (C _{kim tự tháp} * khối lượng _{kim tự tháp})/khối lượng _{tất cả}

Đây là (nặng nề nhận xét code):

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

Vui lòng hỏi tôi bất kỳ câu hỏi nào bạn có thể có hoặc chỉ ra bất kỳ lỗi nào bạn thấy.

Answer 1

Nói chung phụ thuộc vào cấu trúc của đa diện của bạn. Có 4 trường hợp có thể:

• Chỉ các đỉnh có trọng số, tức là đa diện của bạn là hệ thống điểm. Sau đó, bạn chỉ có thể tính toán giá trị trung bình của tổng trọng số của tất cả các điểm:

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

  đây r_i là vector đại diện cho đỉnh thứ i, m_i - khối lượng của nó. Trường hợp khối lượng bằng nhau khiến chúng ta trở nên đơn giản hơn:

  r_c = sum(r_i)/n 
  

  Trường hợp n là số đỉnh. Lưu ý rằng cả hai tổng được vectorized.

• Chỉ các cạnh có trọng lượng và đa diện thực chất là thân thịt. Trường hợp này có thể được giảm xuống trước bằng cách thay thế mỗi cạnh bằng đỉnh nằm ngay giữa cạnh và có trọng số của toàn bộ cạnh.

• Chỉ các khuôn mặt có trọng lượng. Trường hợp này cũng có thể được giảm xuống lần đầu tiên. Mỗi khuôn mặt là một hình lồi 2D, trong đó có thể tìm thấy trung tâm. Thay thế mỗi khuôn mặt bằng trọng tâm của nó sẽ mang trường hợp này đến trường hợp đầu tiên.

• Đa diện rắn (trường hợp của bạn, suy ra từ "giả sử mật độ đồng nhất"). Vấn đề này đòi hỏi một cách tiếp cận phức tạp hơn.Bước đầu tiên là chia đa diện thành tứ diện. Đây là số short description về cách thực hiện việc này. Đối với một centrahedron centroid nằm ở điểm mà tất cả các trung vị của nó giao nhau. (Trung bình của một tứ diện là đường kết nối đỉnh của nó và trung tâm của khuôn mặt đối diện.) Bước tiếp theo là thay thế mỗi tứ diện trong phân vùng bằng centroid của nó. Và bước cuối cùng là tìm ra trọng tâm của tập hợp các điểm trọng số kết quả, đó chính xác là trường hợp đầu tiên.

Answer 2

Đối với trường hợp rắn, có một nhiều simpler method hơn là cố gắng tetrahedralize các đa diện (trong đó có pitfalls).

Đây là mã pseudo-ish java-ish (giả sử thực hiện Vector3 phong nha):

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

Lưu ý, nếu bạn có khuôn mặt mức độ cao hơn so với hình tam giác bạn trivially có thể kiểm tra chéo với một fan hâm mộ và điều này sẽ vẫn làm việc.

Điều này thuận tiện hoạt động ngay cả khi đa diện không lồi.

Tôi cũng đã đăng matlab code