उत्तल पॉलीहेड्रॉन का केंद्र

Question

मेरे पास एक बंद उत्तल पॉलीहेड्रॉन है जिसे उत्तल बहुभुज (चेहरे) की एक सरणी द्वारा परिभाषित किया गया है जिसे 3 डी स्पेस में शिखर के सरणी द्वारा परिभाषित किया जाता है। मैं समान घनत्व मानते हुए, पॉलीहेड्रॉन के केंद्र को खोजने की कोशिश कर रहा हूं। फिलहाल मैं इस छद्म कोड में एल्गोरिदम के साथ इसकी गणना करता हूं।

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% यकीन नहीं है कि यह सही है क्योंकि मैं ऑनलाइन एक सही एल्गोरिदम नहीं ढूंढ पा रहा हूं। अगर कोई मेरी एल्गोरिदम की पुष्टि कर सकता है या मुझे सही से संदर्भित कर सकता है तो मैं इसकी सराहना करता हूं।

धन्यवाद।

---

[संपादित करें]

तो यहाँ वास्तविक जावा कोड मैं केन्द्रक को खोजने के लिए उपयोग कर रहा हूँ है। यह पॉलीहेड्रॉन को पॉलीहेड्रोन के अंदर एक मनमानी बिंदु पर परिवर्तित पिरामिड में तोड़ देता है। पिरामिड सेंट्रॉइड के लिए भारित औसत निम्नलिखित सूत्र पर आधारित है।

सी _सब = SUM _{सब पिरामिड} (सी _{पिरामिड} * मात्रा _{पिरामिड})/मात्रा _सब

यहाँ (भारी कोड टिप्पणी की) है:

// 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 का प्रतिनिधित्व करता है: तो फिर तुम सिर्फ सभी बिंदुओं का भारित योग की औसत मूल्य की गणना कर सकते हैं। बराबर जनता का केस हमें सरल फार्मूले के साथ छोड़ देता है:

  r_c = sum(r_i)/n 
  

  कहाँ n कोने की संख्या है। ध्यान दें कि दोनों रकम वेक्टरकृत हैं।

• केवल किनारों के वजन होते हैं, और पॉलीहेड्रॉन अनिवार्य रूप से एक शव है। इस मामले को किनारे के बीच में स्थित चरम के साथ प्रत्येक किनारे को प्रतिस्थापित करके पिछले पूरे तक घटाया जा सकता है और पूरे किनारे का वजन होता है।

• केवल चेहरे का वजन होता है। इस मामले को पहले भी कम किया जा सकता है। प्रत्येक चेहरा 2 डी उत्तल आकृति है, जिसमें से सेंट्रॉइड पाया जा सकता है। अपने चेहरे के साथ प्रत्येक चेहरे को प्रतिस्थापित करने से यह मामला पहले को लाता है।

• सॉलिड पॉलीहेड्रॉन (आपका मामला, से "समान घनत्व मानता है")। इस समस्या के लिए एक और जटिल दृष्टिकोण की आवश्यकता है।पहला कदम पॉलीहेड्रॉन को टेट्राहेड्रॉन में विभाजित करना है। यह कैसे करें इस पर short description है। एक टेट्राहेड्रॉन केंद्र के लिए उस बिंदु पर स्थित है जहां इसके सभी मध्यस्थ अंतर करते हैं। (टेट्राहेड्रॉन का औसत वह रेखा है जो इसके चरम और विपरीत चेहरे के केंद्र को जोड़ती है।) अगला चरण विभाजन में प्रत्येक टेट्रैड्रॉन को अपने केंद्र के साथ प्रतिस्थापित करना है। और आखिरी कदम भारित बिंदुओं के परिणामी सेट के केंद्र को ढूंढना है, जो वास्तव में पहला मामला है।

Answer 2

ठोस मामले के लिए, वहाँ बहुतल tetrahedralize (जो pitfalls है) की कोशिश कर रहा की तुलना में काफी 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); 

नोट यदि आप उच्च डिग्री चेहरे त्रिकोण से आप तुच्छता से एक प्रशंसक के साथ त्रिकोणाकार कर सकते हैं और यह अभी भी काम करेंगे है:

यहाँ छद्म-ish जावा-ish कोड (सभ्य Vector3 कार्यान्वयन कल्पना करते हुए) है।

यह आसानी से काम करता है भले ही पॉलीहेड्रॉन उत्तल नहीं है।

मैं भी matlab code