संदर्भ के लिए, मैं एक 3D भौतिकी इंजन में टकराव-विवरण को हल करने का प्रयास कर रहा हूं। निम्नलिखित दो उत्तल आकृतियों के पृथक्करण-तल पर 2D प्रक्षेपण के भीतर हो रहा है।

मेरे पास दो त्रिकोण हैं, चलो उन्हें ए और बी कहते हैं। उन्हें 3 बिंदुओं के सेट के रूप में संग्रहीत किया जाता है (उदाहरण के लिए। ए 1, ए 2, ए 3)। मुझे पहले से ही पता है कि ये दो त्रिकोण ओवरलैप करते हैं। मैं एक बिंदु 'पी' कैसे निर्धारित कर सकता हूं जो लगभग उस ओवरलैप के केंद्र में है?

सबसे अच्छा मैं सोच सकता था कि 6 लाइनों के चौराहे को खोजने की कोशिश कर रहा है, फिर, त्रिभुजों में से किसी भी बिंदु सहित, कौन से चौराहे मौजूद हैं, इसके आधार पर। चुने गए बिंदु, चौराहे-बिंदुओं के साथ, फिर एक बहुभुज बना सकते हैं, जिसे मैं तब केंद्र ढूंढ सकता था। हालांकि, मुझे पता है कि यह गणना की एक महत्वपूर्ण राशि होगी, और इसे वास्तविक समय के संदर्भ में उपयोग किया जाना है, मैं एक बेहतर तरीका खोजना चाहता हूं।

मैं जिस बात का जिक्र कर रहा हूं उसका एक उदाहरण नीचे दिया गया है: दो त्रिभुज जो अतिव्यापन के एक छोटे से क्षेत्र के साथ प्रतिच्छेद करते हैं, और केंद्र में एक बिंदु P है।  ओवरलैप का

1
Joel Hemphill 12 मई 2021, 02:02

3 जवाब

सबसे बढ़िया उत्तर

टूसेंट एल्गोरिथम (java के साथ कार्यान्वयन और विधि का मूल पेपर), आप के एल्गोरिथम का उपयोग कर सकते हैं यह पेपर (एक त्रिभुज-त्रिकोण प्रतिच्छेदन एल्गोरिथम) दो त्रिभुजों के बीच प्रतिच्छेदन क्षेत्र ज्ञात करने के लिए।

अब, चूंकि दो उत्तल वस्तुओं का प्रतिच्छेदन उत्तल है, आप यह सूत्र प्रतिच्छेदन क्षेत्र के शीर्षों पर आधारित है जो उपरोक्त एल्गोरिथम में से किसी एक से प्राप्त किया गया है।

2
OmG 12 मई 2021, 21:29

टूसेंट एल्गोरिथम जितना लगता है उससे कम आसान है, और दो त्रिकोणों के लिए पूर्ण ओवरकिल है। मैं सदरलैंड-हॉजमैन क्लिपिंग एल्गोरिदम का उपयोग करूंगा। यह त्रिभुजों में से एक पर तीन पास लेगा और उत्तल बहुभुज बनाने वाले तीन से छह कोने से आउटपुट होगा।

शीर्षों का औसत उस बहुभुज के अंदर होगा। तुम भी जूते का फीता सूत्र के विस्तार द्वारा क्षेत्र के केन्द्रक की गणना कर सकते हैं। https://en.wikipedia.org/wiki/Centroid#Of_a_polygon

कुछ गणनाओं को सरल बनाने के लिए, आप आधार के परिवर्तन को लागू करके शुरू कर सकते हैं जैसे कि त्रिभुजों में से एक को शिखर (0, 0), (0, 1), (1, 0) तक घटाया जाता है, ताकि आधे के समीकरण -प्लेन बस x≥0, y≥0, 1-xy≥0 हैं। इससे परीक्षण और चौराहे आसान हो जाएंगे।

0
Yves Daoust 14 मई 2021, 12:06

A2 और A3 का मध्य बिंदु प्राप्त करें, इसे P1 कहते हैं। लाइन B3 B2 पर प्रतिच्छेदन बिंदु प्राप्त करें। प्रतिच्छेदी बिंदुओं का मध्य बिंदु ज्ञात कीजिए, इसे P2 कहते हैं। अब रेखा P1 P2 का मध्य बिंदु ज्ञात कीजिए, यही वह बिंदु है जिसकी आपको तलाश है।

मुझे लगता है कि एक त्रिभुज के दो बिंदु दूसरे के अंदर हैं। अन्यथा, यदि एक बिंदु दूसरे त्रिभुज के अंदर है तो आप भी ऐसा ही करेंगे लेकिन प्रतिच्छेदन बिंदु को A2 या A3 में से एक मानेंगे।

0
Asbah Ishaq 12 मई 2021, 03:19