दो 3 डी सर्कल पर निकटतम बिंदुओं की एक जोड़ी की गणना कैसे करें?

Question

मेरे पास 3 डी स्पेस (एक केंद्र, सामान्य, और त्रिज्या द्वारा परिभाषित) में दो 2 डी सर्कल हैं और मैं अंक की एक जोड़ी के साथ आने की कोशिश कर रहा हूं जो बिंदुओं के निकटतम जोड़े के सेट में से एक है। मुझे पता है कि 1 से कहीं भी अनंत जोड़ों की संख्या है, मुझे बस एक मिलान करने वाली जोड़ी की आवश्यकता है।

क्या ऐसा करने का कोई आसान तरीका है? प्रेसिजन आवश्यक नहीं है। दोनों सर्किलों का त्रिज्या एक ही, गैर-शून्य मान है।

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

---

सभी प्रतिक्रियाओं यहाँ के लिए धन्यवाद .. परियोजना के इस हिस्से, एक छोटे से देरी हो गई जिसके कारण मैं अभी तक सभी जवाब का परीक्षण नहीं किया। मैं यहां कुछ छवियों को टॉस करना सुनिश्चित करता हूं और जब मैं इस पर काम करता हूं तो एक जवाब चिह्नित करता हूं।

Answer 1

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

मुझे paper ऑनलाइन (this site पर) मिला है जो कठोर रूप से गणनाओं के माध्यम से जाता है लेकिन अंतिम परिणाम 8 वें क्रम बहुपद समीकरण को हल कर रहा है। आप समीकरणों को सरल बनाने की कोशिश कर सकते हैं और कम सटीक समाधान के साथ आ सकते हैं जो आपकी आवश्यकताओं को पूरा करता है।

एक paper भी है जो 3 डी में दो सर्कल के बीच की दूरी खोजने के लिए एक तेज़ एल्गोरिदम का दावा करता है; हालांकि, मैं सामग्री को नहीं देख सकता और, इस प्रकार, यह नहीं बता सकता कि क्या यह आपको उन बिंदुओं की जोड़ी देता है जो उस शर्त को पूरा करते हैं।

अद्यतन: करने के बाद अपने प्रश्न फिर से पढ़ें, मुझे लगता है कि भले ही आप एक तरह से के लिए पूछ रहे हैं 3 आयामों में दो हलकों पर अंक के निकटतम जोड़ी को खोजने के लिए देखते हैं, मुझे लगता है, आप के लिए और अधिक ध्यान देना चाहिए NURBS वक्र के गुण जो आप 2 डी बहुभुज को बाहर निकालने की कोशिश कर रहे हैं। आप उल्लेख करते हैं कि वक्र पर किसी दिए गए बिंदु पर सर्कल का अभिविन्यास उस बिंदु पर टेंगेंट वेक्टर द्वारा निर्दिष्ट किया जाता है। हालांकि, टेंगेंट वेक्टर की तुलना में 3 डी वक्र के लिए और भी कुछ है; वहाँ सामान्य (या वक्रता) वेक्टर है कि एक भी बिंदु पर वक्र की वक्रता के केंद्र की ओर इशारा करता है और फिर वहाँ मरोड़ वेक्टर कि मूल रूप से से वक्र के "उठाना" की राशि को निर्दिष्ट करता है टेंगेंट और सामान्य वैक्टर द्वारा दिया गया विमान। इनमें से सभी एक (जिसे कहा जाता है) फ्रेनेट फ्रेम परिभाषित करते हैं। आप Wikipedia article पर इन पर और अधिक पढ़ सकते हैं।

मेरा संदेह यह है कि आप लगातार सर्कल के बिंदुओं में शामिल होने के द्वारा इच्छित प्रभाव को प्राप्त कर सकते हैं जो प्रत्येक अंतर्निहित 3 डी वक्र की सामान्य वेक्टर दिशा के साथ झूठ बोलता है। इस तरह, आप वक्र घुमाएंगे जब वक्र वास्तव में घुमाएगा, यानी जब टोरसन वेक्टर गैर-शून्य होता है और सामान्य वेक्टर भी दिशा बदल रहा है। अन्य परिस्थितियों में, यह आपकी वास्तविक आवश्यकता को पूरा करना चाहिए।

आपको शायद लगातार सर्कल पर निकटतम बिंदु खोजने की अत्यधिक आवश्यकता नहीं है।

Answer 2

क्या यह सिर्फ मंडलियों/क्षेत्रों के दो केंद्रों के बीच रेखा बनाने और रेखा और मंडलियों के चौराहे को खोजने का मामला नहीं है? निकटतम समाधान यह हैं (जब तक सर्कल छेड़छाड़ न हो, तब उत्तर इस बात पर निर्भर करता है कि आप उस मामले की व्याख्या कैसे करना चाहते हैं)।

Answer 3

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

http://www.physicsforums.com/showthread.php?t=123168

वह लिंक से पता चलता 3 डी अंतरिक्ष में प्रत्येक चक्र के समीकरण पाने के लिए है, तो उन समीकरणों के बीच की दूरी को कम करने के लिए सूत्र। हालांकि सुंदर नहीं है, उम्मीद है कि कोई और अधिक चालाक के साथ आएगा।

Answer 4

जो आप वर्णन करते हैं, उसके लिए पहले सर्कल के परिधि पर एक बिंदु चुनने के लिए पर्याप्त है और प्रत्येक सर्कल के परिधि पर बिंदु ढूंढें जो पिछले सर्कल के लिए चुने गए एक के निकट है; यह पॉलीगोनिज़ेशन को पूरी तरह से बाधित नहीं करेगा, बिना किसी घुमाव के, और सामान्य मामले की तुलना में हल करने के लिए बहुत आसान होना चाहिए - बस दूसरे सर्कल वाले विमान पर बिंदु ढूंढें जो पहले चयनित में सबसे नज़दीक है, और लाइन से गुजरने वाली रेखा को अलग करता है उस बिंदु और दूसरे सर्कल के केंद्र दूसरे सर्कल के परिधि के साथ।

हालांकि, यह बहुभुज क्षेत्र को यथासंभव स्थिर रखने के रूप में निकाले गए सिलेंडर के लिए बहुभुजीकरण के रूप में उत्पन्न नहीं हो सकता है, और ऐसा करने के लिए निकटवर्ती मंडलियों के बीच कुछ घुमाव की आवश्यकता होगी।

Answer 5

मुझे लगता है कि दो निकटतम बिंदुओं के साथ आपको अभी भी अजीब घुमाव मिल सकता है ... एक चरम उदाहरण: मान लीजिए कि दोनों सर्किलों में आर = 1 है। यदि पहला सर्कल का केंद्र ओ है, और यह एक्सवाई विमान पर बैठा है, और दूसरा सर्कल का केंद्र एक्स = 1, वाई = 0, जेड = 0.01 पर बैठा है, और यह एक्स की बढ़ती दिशा में थोड़ा सा झुका हुआ है, निकटतम दो सर्कल पर अंक निश्चित रूप से "अजीब मोड़" प्राप्त करने के लिए करेंगे जो आप टालने की कोशिश कर रहे हैं। चूंकि निकटतम बिंदु आपको अजीब मोड़ नहीं मिलेंगे क्योंकि दूसरा सर्कल एक्स = 0, वाई = 0, जेड = 0.01 पर है और समान रूप से झुका हुआ है, फिर कुछ बिंदुओं पर "दो मंडलियों पर दो निकटतम बिंदुओं के साथ गठबंधन" और "कोई अजीब घुमावदार नहीं देखा" अब एक-दूसरे से मेल नहीं खाता है।

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

अगले संरेखण बिंदुओं के लिए आप "पिछले सर्कल" के संरेखण बिंदु ले लेंगे, और "पिछले सर्कल" के केंद्र के बीच विमान को आकर्षित करेंगे, यह संरेखण बिंदु, और "नया सर्कल" का केंद्र होगा। इससे आपको दूसरे सर्कल के साथ छेड़छाड़ के आधार पर "अगला संरेखण बिंदु" मिलता है।

अगला चरण - "पिछला सर्कल" = "नया सर्कल", और "नया सर्कल" - आपका अगला एक NURBS वक्र के अनुसार।

यदि चयनित संरेखण बिंदुओं पर मंडलियों के केंद्रों से त्रिज्या पार हो जाती है, तो आप जानते हैं कि तस्वीर थोड़ा बदसूरत दिखाई देगी - यह परिदृश्य है जहां "निकटतम बिंदु" एल्गोरिदम के साथ आपको अभी भी अजीब घुमाव मिल जाएगा ।

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

मेरे पास उपर्युक्त रूप से पूरी तरह से दावा करने या इनकार करने के लिए कठोर प्रमाण नहीं है - लेकिन उम्मीद है कि यह बिल्कुल मदद करता है, और मुझे लगता है कि यह दो सर्किलों पर कोठरी बिंदुओं की गणना करने की तुलना में सत्यापित करने के लिए पर्याप्त तेज़ होना चाहिए .. (यदि मेरे तर्क में कोई गड़बड़ी है, तो टिप्पणियों में सुधार बहुत स्वागत है)।

Answer 6

विमानों को मंडल (केंद्र बिंदुओं और मानदंडों का उपयोग करके) बढ़ाएं। यदि विमान समानांतर हैं, तो कोई भी अंक करेगा। यदि विमान समानांतर नहीं हैं, तो वे एक पंक्ति में छेड़छाड़ करते हैं। लाइन के लंबवत सर्कल के दो केंद्रों के माध्यम से विमान का निर्माण। दो सर्किल इस नए विमान को चार बिंदुओं में छेड़छाड़ करते हैं। ये चार बिंदु दो निकटतम बिंदु और मंडलियों पर दो सबसे दूर बिंदु हैं।

Answer 7

धागा here, किसी अन्य उत्तर में वर्णित एक 3 डी सर्कल के लिए पैरामीटरकरण सूत्र देता है: पी = आर कॉस (टी) यू + आर पाप (टी) nxu + c, जहां आप केंद्र के केंद्र से एक इकाई वेक्टर है परिधि पर किसी भी बिंदु पर सर्कल; आर त्रिज्या है; एन विमान के लिए लंबवत एक इकाई वेक्टर है और सी सर्कल का केंद्र है, टी 0 से 2pi तक जाता है, और nxu से मेरा मतलब है "एन क्रॉस यू"। इस तरह एक सर्कल को पैरामीटरेट करें, और दूसरा एक अलग पैरामीटर के साथ, एस कहें। फिर पहले सर्कल पर प्रत्येक बिंदु पीटी में वेरिएबल टी में निर्देशांक होंगे, और दूसरे बिंदु पर प्रत्येक बिंदु Ps को चर के एस में निर्देशांक होंगे।

सामान्य रूप से Ps और Pt के बीच दूरी फ़ंक्शन डी (एस, टी) लिखें (या बेहतर, यूक्लिडियन दूरी का वर्ग ताकि आपको डेरिवेटिव लेने पर स्क्वायर रूट के साथ गड़बड़ न हो)। दो चर के इस फ़ंक्शन डी का आलेख एस, टी प्लेन में 2pi वर्ग द्वारा 2pi से अधिक सतह है, और यह न्यूनतम है जो आप बाद में हैं। आप इसे मानक कैलकुंस विधियों के साथ निर्धारित कर सकते हैं, उदा। जैसा कि here समझाया गया है।