볼록 다면체의 중심체

Question

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 % 확신하지 못했습니다. 누군가 내 알고리즘을 확인하거나 올바른 알고리즘을 사용할 수 있다면 감사하게 생각합니다.

감사합니다.

---

[편집] 그래서 여기

내가 중심을 찾기 위해 사용하고있는 실제 자바 코드입니다. 다면체를 임의의 점에서 수렴하는 피라미드로 분할합니다. 피라미드 중심의 가중 평균은 다음 공식을 기반으로합니다.

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

을

내가 가질 수있는 질문이 있으시면 언제든지 문의 해주십시오. 오류를 지적하거나 오류를 지적하십시오.

Answer 1

일반적으로 다각형의 구조에 따라 다릅니다. 다음과 같은 4 가지 경우가 있습니다.

• 정점에만 가중치가 있습니다. 즉, 다면체는 점 시스템입니다. - 질량

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

  다음

  r_i는 i 번째 정점, m_i을 나타내는 벡터이다 : 그럼 그냥 모든 점의 가중 합계의 평균 값을 계산할 수 있습니다. 동일한 질량의 케이스는 간단한 공식으로 우리를 잎 : n 정점의 수입니다

  r_c = sum(r_i)/n 
  

  합니다. 두 합계는 벡터화됩니다.

• 가장자리에만 무게가 있고, 다면체는 본질적으로 시체입니다. 이 경우는 각 모서리를 모서리의 중앙에있는 꼭지점으로 대체하고 전체 모서리의 무게를 가짐으로써 이전 모 델로 줄일 수 있습니다.

• 얼굴에만 무게가 있습니다. 이 경우 첫 번째로 줄일 수 있습니다. 각면은 2D 볼록한 도형이며 중심은 발견 될 수 있습니다. 각면을 중심에 대입하면이 경우가 첫 번째면으로 이동합니다.

• 단색 다면체 (귀하의 경우, 에서 "균일 밀도 가정")을 추측하십시오. 이 문제는보다 복잡한 접근 방식을 필요로합니다.첫 번째 단계는 다면체를 사면체로 분리하는 것입니다. 이렇게하는 방법은 short description입니다. 중력선은 모든 중선들이 교차하는 지점에 위치한다. (정사면체의 중앙값은 꼭지점과 반대면의 중심을 연결하는 선입니다.) 다음 단계는 파티션의 각 정사면체를 중심점으로 대체하는 것입니다. 그리고 마지막 단계는 정확한 가중치 세트의 중심을 찾는 것입니다. 정확히 첫 번째 경우입니다.

Answer 2

고체의 경우를 들어, (pitfalls이있는) 다면체를 tetrahedralize하는 것보다 훨씬 simpler method이 있습니다. 당신은 당신이 하찮게 팬과 삼각 측량 할 수 있으며이 여전히 작동 삼각형보다 높은 수준의 얼굴이있는 경우,

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

참고 : 여기에

는 의사 흉내 자바 틱 코드 (괜찮은 Vector3 구현을 가정)을합니다.

다면체가 볼록하지 않은 경우에도 편리합니다.

나는 또한 그것을 위해 보증 할 수 있지만 http://www.cs.berkeley.edu/~jfc/mirtich/massProps.html을보고 가치가있을 수도