त्रिभुजों एल्गोरिदम के 3 डी चौराहे - शीर्षतम विमान

Question

प्रदर्शित करना मैं बिना किसी खुशी के विमानों की मनमानी संख्या के शीर्ष चौराहे की गणना करने की कोशिश कर रहा हूं! मैं क्रियालेख का उपयोग कर रहा हूं, लेकिन मुझे एक एल्गोरिदम खोजने की ज़रूरत है जिसे मैं कार्यान्वित कर सकता हूं।

समस्या:

• 3 ऊर्ध्वाधर अक्ष पर विचार करें।
• उपयोगकर्ता प्रत्येक त्रिकोण/विमान के लिए 3 अंक दर्ज करता है जैसे त्रिभुज के बिंदु धुरी में से एक पर झूठ बोलते हैं।
• उपयोगकर्ता एक मनमाना संख्या त्रिकोण
• दर्ज कर सकते हैं मुझे इन त्रिकोणों की सबसे ऊपरी परत खोजने की आवश्यकता है और इसे स्क्रीन पर और साथ ही साथ समन्वय के निर्देशांक भी प्रदर्शित करने की आवश्यकता है।

  

  हालांकि, जब हम अधिक से अधिक 2 त्रिकोण के लिए अनुमति देते हैं, मैं चौराहे के अजीब लाइनों मिलती है:

यहाँ स्पष्ट करने के लिए मैं 2 त्रिकोण के साथ क्या मतलब है एक तस्वीर है।

Answer 1

मुझे आपकी समस्या से बहुत दिलचस्पी है इसलिए मैंने एल्गोरिदम का वर्णन किया और इसे सी ++ में लागू किया (मुझे सी ++ के रूप में अच्छा नहीं पता है)। एल्गोरिदम का मुख्य विचार नए त्रिकोण जोड़ते समय शीर्ष सतह का पुनरावृत्ति पुनरावृत्ति है।

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

पॉलीगॉन सेट के रूप में शीर्ष सतह के बारे में सोचने दें। जबकि नया बहुभुज जोड़ रहा है, हमें सभी सतह बहुभुजों के चेहरे को पुन: गणना करना चाहिए। चेहरे के पुनर्मूल्यांकन के एल्गोरिदम में निम्नलिखित कदम शामिल हैं:

1. पॉलीगॉन के किनारे पर दो बिंदु और बहुभुज अवरोध की रेखा पर झूठ बोलना शामिल है। इसके अंक अपने कवर किए गए हिस्सों को हटाने के बाद माना बहुभुज के नए चरम बनना चाहिए। इन बिंदुओं में से प्रत्येक को 3 विमानों के चौराहे के रूप में गणना की जा सकती है: बहुभुज विमान, नया बहुभुज विमान माना जाता है, माना जाता है कि बहुभुज चेहरों में से एक है। बहुभुज के किनारे पर नहीं अंक को ध्यान में रखा जाना चाहिए।
2. यदि दो से कम अवरोध बिंदु हैं तो बहुभुजों में से एक दूसरे को पूरी तरह ओवरलैप कर रहा है। इस प्रकार हम ऊपरी को निर्धारित करना चाहिए। पॉलीगॉन अवरोध की रेखा पर बिछाए नहीं, वर्तमान बहुभुज के किसी भी बिंदु पर विचार करें। हम अपने एक्स और वाई निर्देशांक ले सकते हैं, नए बहुभुज विमान के अंदर बिंदु की गणना कर सकते हैं और उनके जेड निर्देशांक की तुलना कर सकते हैं।
3. यदि दो बिंदु हैं तो बहुभुज चेहरे सेट को संशोधित किया जाना चाहिए। बिंदु गणना के बाद हम पार चेहरों के सूचकांक भी जानते हैं। इंडेक्स रेंज के अंदर बिंदु को ध्यान में रखते हुए, चेहरे को हटाए जाने वाले हिस्से को निर्धारित किया जा सकता है।
4. बहुभुज से ओवरलैप्ड चेहरे निकालें और बहुभुज बिंदुओं पर गणना किए गए चेहरे बहुभुज में डालें।

इस पृष्ठ पर बाढ़ नहीं करने के लिए मैंने कोड को pastebin में रखा है।

Answer 2

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

Answer 3

आप इसे त्रिभुज B=[(0,0),(0,1),(1,0)] पर ऊंचाई फ़ील्ड के रूप में देख सकते हैं।

चूंकि विमान को B के कोनों पर ऊंचाई के रूप में परिभाषित किया गया है, B पर विमान की ऊंचाई को बैरेंट्रिक निर्देशांक के साथ गणना की जा सकती है। दिया साथ: barycentric साथ

• B में की B
• बिंदु P कोनों पर ऊंचाइयों (a,b,c) साथ विमान निर्देशांक (x,y,z) [x+y+z=1, x,y,z>=0], बिंदु पर विमान के

ऊंचाई Px*a + y*b + z*c है।

(x,y,1-x-y) में बिंदु P=(x,y) के लिए प्राकृतिक बैरीसेंट्रिक निर्देशांक।

इसके साथ बैरीसेंट्रिक निर्देशांक में 2 विमानों, (a1,b1,c1) और (a2,b2,c2) की चौराहे रेखा की गणना करना आसान है। बस बराबर जहां 2 विमानों 0 <= x,y <= 1 और x+y <= 1, 2 विमानों इस B में 2 विमानों चौराहे रेखा का समीकरण है के साथ एक ही ऊंचाई है

x*a1 + y*b1 + (1-x-y)*c1 = x*a2 + y*b2 + (1-x-y)*c2 
=> 
x*(a1-c1-(a2-c2)) + y*(b1-c1-(b2-c2)) + c1-c2 = 0 

।

मुझे लगता है कि 2 दृष्टिकोण है कि ऊंचाई क्षेत्र (ऊपर सबसे परत) जिसके परिणामस्वरूप के निर्माण के लिए इस्तेमाल किया जा सकता हैं कि:

नया त्रिकोण

यह समर्थन करने के लिए जोड़ने Iterative, यह आवश्यक है करने के लिए संरचना जो त्रिकोण के विभाजन B बहुभुज में है। बहुभुज त्रिभुज का क्षेत्र है जहां एक विमान उच्चतम है। चूंकि हम विमानों से निपट रहे हैं, बहुभुज उत्तल होंगे और एक विमान अधिकांश बहुभुज में उत्पादन कर सकता है। मौजूदा त्रिकोण क्षेत्र के साथ नए त्रिकोण और चौराहे की गणना जोड़ना नई बहुभुज (चौराहे रेखाएं और B की सीमा) का उत्पादन करेगा। यह नया बहुभुज ऊंचाई क्षेत्र में जोड़ा गया है। यदि मौजूदा बहुभुज को भाग से अलग किया गया है तो हटा दिया जाता है। यदि बहुभुज की तुलना में मौजूदा बहुभुज ओवरलैप किया गया है।

चौराहे सामने लाइन एक कोने से

1. प्रारंभ प्रचार और विमान उस पर heighest है कि लेने के (जैसे विमान wiht अधिकतम (a_i))। उस कोने में फ्रंट लाइन सेट करें।
2. उन विमानों को खोजें जो सामने के निकट चौराहे लाइनों के साथ विमान शुरू करने के लिए छेड़छाड़ करते हैं। इन चौराहे लाइनों के सामने आगे बढ़ें।
3. सामने वाले लाइन पर एक (कोई भी) विमान लें और आगे के नजदीकी चौराहे वाली लाइनों के साथ संसाधित विमानों के साथ छेड़छाड़ न करें। इन चौराहे लाइनों के सामने आगे बढ़ें।

दोहराना 3. जब तक फ्रंट लाइन त्रिभुज B शामिल नहीं हो जाती है।

मैं दूसरा एल्गोरिदम पसंद करता हूं।

Answer 4

आप तीन लंबवत "अक्ष" के बीच अपनी रुचि की सतह बना रहे हैं। सतह आधार से नीचे बाध्य है। इसे ऊपर से बांधें ताकि समस्या त्रिभुज प्रिज्म में निहित हो।

ऊपर अपने सतह मात्रा एक convex hull विमानों अन्तर्विभाजक (: टोपी, तीन तरफ, और त्रिकोण चौराहों बुद्धि के लिए) द्वारा गठित है। उत्तल हल्स के बारे में बहुत सारे सिद्धांत और कोड हैं।

मैं ActionScript पता नहीं है, लेकिन पर एक त्वरित इंटरनेट खोज "उत्तल विमानों अन्तर्विभाजक hulls" और ऐसी शर्तों मुझे इस कोड है जो आपकी समस्या का समाधान (जानने की कोशिश की) को जन्म दिया:

http://nauful.com/pages/convexhull.html

आशा यह मदद करता है, ग्लेन