कैसे पता लगाएं कि कोई 3 डी ऑब्जेक्ट किसी अन्य 3 डी ऑब्जेक्ट (कंटेनर) में फिट बैठता है या नहीं?

Question

दो 3 डी ऑब्जेक्ट्स देखते हुए, मैं कैसे पा सकता हूं कि कोई दूसरा के अंदर फिट बैठता है (और कंटेनर में ऑब्जेक्ट का स्थान ढूंढें)।

ऑब्जेक्ट का अनुवाद और कंटेनर फिट करने के लिए घुमाया जाना चाहिए - लेकिन अन्यथा संशोधित नहीं किया जाना चाहिए।

अतिरिक्त जटिलताओं:

1. एक ही स्थिति है - लेकिन सबसे उपयुक्त समाधान के लिए देखो, भले ही वह एक उचित मैच (उद्देश्य यह है कि कंटेनर में फिट नहीं करता है की मात्रा को कम से कम) नहीं है

   लोचदार वस्तुओं के लिए

2. समर्थन - जबकि वस्तुओं

यह एक बहुत सामान्य सवाल यह है कि में "विरूपण" कम से कम सबसे उपयुक्त लगता है - और मुझे पूरा समाधान की उम्मीद नहीं है। प्रासंगिक कागजात \ आलेख \ पुस्तकालय \ उपकरण के लिए कोई भी संकेत उपयोगी होगा

Answer 1

यहां आदर्श विधि से शायद एक शायद कम है।

आप 1 आकार की स्थिति (3 डी स्पेस में) को ठीक करने का प्रयास कर सकते हैं। उस आकार के शीर्ष पर दूसरे आकार को रखना। फिर ऐसे लिंक बनाएं जो आकार में एक बिंदु को दूसरे आकार में किसी बिंदु से कनेक्ट करें। फिर अनुकरण करें कि जब लिंक समान रूप से तंग खींचे जाते हैं तो क्या होता है। उस बिंदु का कारण बनना जो स्थिर होने तक घूमने और अनुवाद करने के लिए तय नहीं है।

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

Answer 2

यह काफी कठिन समस्या की तरह लगता है। संभावित दृष्टिकोण कुछ ह्युरिस्टिक है जो परिवर्तन का सुझाव देने के लिए है और जांच से यह अच्छा है। यदि रूपांतरण परिवर्तन को थोड़ा समायोजित करने और परीक्षण करने के बजाय इंटीरियर से थोड़ा सा (उदा। एक भाग पर) ऑब्जेक्ट को स्थानांतरित करता है। यदि ऑब्जेक्ट नया ह्युरिस्टिक अनुमान बनाने के बजाय 'बहुत' बाहर है (उदा। दोनों तरफ एक ही/सभी अक्ष पर)।

एक उदारवादी के लिए बस एक सामान्य विचार। एक ही पिक्सेल आकार के साथ एक वस्तु का एक rasterisation बनाओ। यह ऑब्जेक्ट वॉल्यूम का ऑक्टेट हो सकता है। पिक्सेल के बीच कनेक्टिविटी ग्राफ बनाओ। ग्राफ के बीच सबग्राफ आइसोमोर्फिज्म की जांच करें। यदि उस स्थिति की तुलना में कोई सबग्राफ है तो परीक्षण के लिए है।

यह दृष्टिकोण 90 डिग्री रोटेशन (ओं) का भी समर्थन करता है।

ग्राफ पर भी कुछ परीक्षण किए जा सकते हैं। यदि ऑब्जेक्ट की तुलना में सबग्राफ के सभी वॉल्यूम पड़ोस बड़े ग्राफ में हैं।

सामान्यतः यह 'परिष्कृत' सीमा बॉक्स दृष्टिकोण है।

Answer 3

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

Answer 4

लक्ष्य वस्तु में एक बहुभुज (त्रिकोण) पर विचार करें। इस बहुभुज के लिए, अन्य ज्यामिति (स्रोत), यानी समकक्ष बहुभुज को खोजें।किनारों की लंबाई, किनारों के बीच कोण, क्षेत्र सभी समान होना चाहिए। यदि केवल एक मैच है, तो कठोर ट्रांसफॉर्म मैट्रिक्स ढूंढें, जो इस तरह के शिखर को बदलता है: X' = M*X। चूंकि X' और X मिलान किए गए बहुभुजों के सभी बिंदुओं के लिए जाने जाते हैं, इसलिए यह रैखिक बीजगणित के साथ किया जा सकता है।

यदि आप बहुभुज के शिखर के बीच एक-एक मैपिंग चाहते हैं, तो उसी क्रम में बहुभुज के किनारों को पार करें, और एक लुकअप टेबल बनाएं जो प्रत्येक चरम पर एक पॉली को एक चरम पर एक पॉली में मैप करें। अगर आपके पास 3 डी ऑब्जेक्ट का half edge data structure है जो इस प्रक्रिया को सरल बना देगा।

यदि आपको एक से अधिक मिलान बहुभुज मिलते हैं, तो दोनों बिंदुओं से स्रोत बहुभुज को पार करें, और लक्षित बहुभुज के साथ अपने पड़ोसी बहुभुज से मेल खाते रहें। तब तक जारी रखें जब तक उनमें से कोई एक तोड़ न जाए, जिसके बाद आप एक-मैच संस्करण के समान कदम उठा सकते हैं।

अधिक गंभीर समाधान हैं जो here सूचीबद्ध हैं, लेकिन मुझे लगता है कि उपर्युक्त विधि भी काम करेगी।