मैं अंक के एक सेट के सबसे छोटे संलग्न आयत (मनमाने ढंग से गठबंधन) की गणना के साथ संघर्ष कर रहा हूं।क्या कोई मुझे घूर्णन कैलिपर समझा सकता है?
मैं ग्राहम के एल्गोरिदम का उपयोग करके उत्तल हल की गणना करने में सक्षम था।
जहां मैं अटक गया हूं अगला कदम है। मैंने घूर्णन कैलिपर विधि का उपयोग करने के बारे में सोचा, लेकिन मुझे एल्गोरिदम का पर्याप्त स्पष्टीकरण नहीं मिल रहा है।
यदि आपके पास उत्तल हल है, तो एक मूल एल्गोरिदम आसान है। आप केवल उत्तल हॉल के प्रत्येक किनारे से गुजरते हैं और अपने बिंदु घुमाते हैं ताकि किनारे एक प्रमुख अक्ष के साथ हो, चलो एक्स-अक्ष कहें। फिर आपको उन बिंदुओं के धुरी-गठबंधन बाउंडिंग बॉक्स मिलते हैं। चुनें कि जो भी बाउंडिंग बॉक्स सबसे छोटा है।
एक अक्ष-संरेखित बाध्यकारी बॉक्स प्रत्येक आयाम में न्यूनतम और अधिकतम प्राप्त करके पाया जा सकता है।
यदि आप अपने बाध्यकारी बॉक्स को विपरीत राशि से घुमाते हैं, तो यह अब आपके मूल बिंदुओं को घेर लेगा।
इसे और अधिक कुशल बनाने के लिए, ध्यान दें कि बाउंडिंग बॉक्स को प्रभावित करने वाले एकमात्र बिंदु उत्तल हॉल पर हैं।
इसे वास्तव में कुशल बनाने के लिए, ध्यान दें कि किसी भी समय बाध्यकारी बॉक्स को छूने वाले उत्तल हॉल के चारों ओर केवल चार बिंदु हैं (यह सख्ती से सच नहीं है, लेकिन अभी इसके लिए अनदेखा करें)। यदि आप अंक को घुमाते हैं तो अगले किनारे को बाउंडिंग बॉक्स के साथ गठबंधन किया जाता है, तो उनमें से तीन बिंदु समान होते हैं और बिंदुओं में से एक को उत्तल हॉल के आस-पास के अगले बिंदु के साथ बदल दिया जाता है। यह आपको एक एल्गोरिदम बनाने देता है जो उत्तल हॉल पर बिंदुओं की संख्या में रैखिक है।
अब ऐसे विशेष मामले हैं जहां दो किनारे समानांतर या लंबवत हैं। इससे किसी भी समय बाउंडिंग बॉक्स को छूने के लिए चार से अधिक अंक होंगे, लेकिन इससे कोई फर्क नहीं पड़ता। यदि आपके पास अगली बार उपयोग करने के लिए दो समानांतर किनारों के बीच कोई विकल्प है, तो आप केवल एक मनमाने ढंग से चुन सकते हैं।
इस विधि के साथ एकमात्र समस्या यह है कि यह ओ (एन^2) है, जो उत्तल होल में कई शिखर होने पर उपयुक्त नहीं हो सकता है। – mbeckish
@mbeckish: सच - मैंने अपने उत्तर को दो अनुकूलन के साथ बढ़ा दिया है। शायद इसे ऑप्टिमाइज़ेशन के साथ एक सरल एल्गोरिदम के रूप में सोचने से यह समझना आसान हो जाएगा। –
यह सच नहीं है कि उत्तल हॉल के चारों ओर केवल चार अंक हैं जो किसी भी समय बाउंडिंग बॉक्स को छू रहे हैं। कोलिनेर पॉइंट मानते हैं कि उत्तल हॉल में नहीं होता है, बाउंडिंग बॉक्स 8 अंक तक स्पर्श कर सकता है। उत्तल हॉल '(2,0), (3,0), (4,1), (4,2), (3,3), (2,3), (1,2), (1, 1) 'अक्ष के साथ गठबंधन बाध्यकारी बॉक्स (या एक झुका हुआ 45 डिग्री) सभी बिंदुओं को छूता है। –
[यह स्पष्टीकरण] देखें (http://cgm.cs.mcgill.ca/~orm/maer.html)। – mbeckish
क्या आपने [टॉसेंट का मूल पेपर] देखा है (http://cgm.cs.mcgill.ca/~godfried/publications/calipers.pdf)? पेज 1 और 2 एल्गोरिदम को स्पष्ट रूप से स्पष्ट रूप से समझाते हैं (आईएमओ)। ध्यान दें कि पेज नंबरिंग को उलट दिया गया है ... –