जब पॉलीहेड्रॉन दिया जाता है तो पॉलीहेड्रॉन के केंद्र और मात्रा की गणना

Question

एक उत्तल पॉलीहेड्रॉन (3 डी) के शिखर के स्थान को देखते हुए, मुझे पॉलीहेड्रॉन के केंद्र और मात्रा की गणना करने की आवश्यकता होती है। निम्नलिखित कोड Mathworks site पर उपलब्ध है।

function C = centroid(P) 
k=convhulln(P); 
if length(unique(k(:)))<size(P,1) 
    error('Polyhedron is not convex.'); 
end 
T = delaunayn(P); 
n = size(T,1); 
W = zeros(n,1); 
C=0; 
for m = 1:n 
    sp = P(T(m,:),:); 
    [null,W(m)]=convhulln(sp); 
    C = C + W(m) * mean(sp); 
end 
C=C./sum(W); 
return 
end 

कोड सुरुचिपूर्ण है लेकिन बहुत धीमी है। मुझे सैकड़ों बार हजारों पॉलीहेड्रॉन की मात्रा और केंद्र की गणना करने की आवश्यकता है। इस कोड का उपयोग वर्तमान स्थिति में करना संभव नहीं है। क्या कोई बेहतर दृष्टिकोण जानता है या क्या यह कोड तेजी से बनाया जा सकता है? कुछ मामूली परिवर्तन हैं जिनके बारे में मैं सोच सकता हूं, mean को अर्थ के लिए अभिव्यक्ति के साथ बदलना।

Answer 1

आप अपने कोड को कितनी तेज़ी से बढ़ा सकते हैं इस पर निर्भर करता है कि आप अपने सेंट्रॉइड की गणना कैसे करना चाहते हैं। अपने विकल्पों के लिए this answer about centroid calculation देखें। यह पता चला है कि यदि आपको ठोस पॉलीहेड्रॉन के केंद्र की आवश्यकता है, तो आप मूल रूप से भाग्य से बाहर हैं। अगर, हालांकि, केवल बहुतल के कोने वजन है, तो आप बस

[k,volume] = convhulln(P); 
centroid = mean(P(k,:)); 

Answer 2

अपने ही एकमात्र विकल्प सोच लिख सकता है अगर quickhull पर्याप्त नहीं होता cudahull है अगर आप सटीक समाधान चाहते हैं। हालांकि, फिर भी आप केवल 40x वृद्धि अधिकतम (ऐसा लगता है) प्राप्त करने जा रहे हैं।

मुझे लगता है कि आपके उत्तल उत्थान से आप कम से कम 10 कोष्ठक बनाते हैं (यदि यह उससे बहुत कम है, तो आप ऐसा नहीं कर सकते हैं)। यदि आपको "पर्याप्त बंद" समाधान नहीं है। आप quickhull का एक संस्करण बना सकते हैं जो प्रति बहुभुज के चरम सीमा को सीमित करता है। आपके द्वारा गणना की गई सीमाओं की संख्या को यदि आवश्यक हो तो अधिकतम त्रुटि की गणना करने की अनुमति भी दी जाएगी।

बात यह है कि उत्तल हॉल दृष्टिकोण पर शिखर की संख्या अनंतता तक पहुंच जाती है, तो आप एक क्षेत्र के साथ समाप्त होते हैं। इसका मतलब है कि त्वरित हल कार्य करने के तरीके के कारण, आप उत्तल हॉल में जो भी अतिरिक्त चरम जोड़ते हैं, उसके पहले से पहले की तुलना में कम प्रभाव पड़ता है।

* इस पर निर्भर करता है कि कैसे Quickhull कोड किया गया है, यह केवल सामान्य अर्थ में सच हो सकता है। अभ्यास में यह सच बनाने के लिए क्विकहुल के रिकर्सन एल्गोरिदम को संशोधित करने की आवश्यकता होगी, इसलिए "अगली कशेरुक" हमेशा गणना की जाती है (अंतिम चरम सीमा के बाद छोड़कर, या उस खंड के लिए कोई बिंदु नहीं रहता है), कोनेक्स वास्तव में उत्तल हल में जोड़ दिए जाते हैं ऑर्डर जो पॉलीहेड्रॉन वॉल्यूम में वृद्धि को अधिकतम करता है (संभवतः कम से कम दूर से दूर तक)। वर्टेक्स जोड़ने के क्रम को ट्रैक रखने के लिए आपको कुछ प्रदर्शन लागत लगेगी, लेकिन जब तक लंबित उत्तल बिंदु बनाम लंबित बिंदुओं का अनुपात काफी अधिक है, तो यह इसके लायक होना चाहिए। त्रुटि के लिए, सबसे अच्छा विकल्प शायद एल्गोरिदम को रोकने के लिए है जब वास्तविक उत्तल हॉल तक पहुंच जाता है, या वॉल्यूम में अधिकतम वृद्धि वर्तमान कुल मात्रा के एक निश्चित अंश से छोटी हो जाती है। यदि प्रदर्शन अधिक महत्वपूर्ण है, तो प्रति पॉलीगॉन के उत्तल हल बिंदुओं की संख्या को सीमित करें।

आप विभिन्न अनुमानित उत्तल हॉल एल्गोरिदम भी देख सकते हैं, लेकिन ऊपर उल्लिखित विधि को वॉल्यूम/सेंट्रॉइड सन्निकटन के लिए त्रुटि निर्धारित करने की क्षमता के साथ अच्छी तरह से काम करना चाहिए।

Answer 3

न्यूनतम प्रयास के साथ वॉल्यूम की गणना करने के लिए एक बहुत ही सरल दृष्टिकोण है। पहला स्वाद पॉलीहेड्रॉन के 3 स्थानीय टोपोलॉजिकल सूचना सेट, किनारों के टेंगेंट यूनिट वेक्टर, इस टेंगेंट पर इन-प्लेन सामान्य के यूनिट वैक्टर और पहलू के यूनिट वेक्टर (जो कि से निकालने के लिए बहुत आसान हैं) कोने)। अधिक जानकारी के लिए कृपया Volume of a Polyhedron देखें।

दूसरा स्वाद इस Wikipedia Article के अनुसार पॉलीहेड्रोन मात्रा की गणना करने के लिए चेहरे के क्षेत्रों, सामान्य वैक्टर और चेहरे की बैरीसेंटर्स का उपयोग करता है। दोनों एल्गोरिदम सरल और सरल बनाने के लिए बहुत आसान हैं और साधारण संक्षेप संरचना के माध्यम से भी वेक्टरिज़ करना आसान है। मुझे लगता है कि दोनों दृष्टिकोण पॉलीहेड्रॉन की पूरी तरह से विकसित छेड़छाड़ करने से बहुत तेज होंगे।

पॉलीहेड्रॉन का केंद्र तब पॉलीहेड्रॉन सतह पर एकीकरण में पूर्ण पॉलीहेड्रोन मात्रा पर एकीकरण को स्थानांतरित करने वाले विचलन प्रमेय को लागू करके गणना की जा सकती है। Calculating the volume and centroid of a polyhedron in 3d में एक विस्तृत विवरण मिल सकता है। मैंने यह जांच नहीं की कि क्या त्रिभुज में पॉलीहेड्रोन का टेस्सेलेशन वास्तव में जरूरी है या कोई भी पॉलीहेड्रोन की जटिल जटिल बहुभुज सतहों के साथ काम कर सकता है, लेकिन किसी भी मामले में चेहरों का क्षेत्र छेड़छाड़ वॉल्यूम टेस्सेलेशन से कहीं अधिक सरल है। कुल मिलाकर संयुक्त दृष्टिकोण वॉल्यूम दृष्टिकोण से बहुत तेज होना चाहिए।