ग्राहम स्कैन

File:GrahamScanDemo.gif

2डी उत्तल पतवार खोजने के लिए ग्राहम के स्कैन का डेमो।

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

ने और उन्हें हटाने के लिए स्टैक (अमूर्त डेटा प्रकार) का उपयोग करता है।

एल्गोरिथम

File:Graham Scan.svg

जैसा कि कोई देख सकता है, पीएबी और एबीसी वामावर्त हैं, लेकिन बीसीडी नहीं है। एल्गोरिदम इस स्थिति का पता लगाता है और पहले से चुने गए खंडों को तब तक हटा देता है जब तक कि लिया गया मोड़ वामावर्त (इस मामले में एबीडी) न हो जाए।

इस एल्गोरिदम में पहला कदम सबसे कम y-निर्देशांक वाला बिंदु ढूंढना है। यदि सेट में एक से अधिक बिंदुओं पर सबसे कम y-निर्देशांक मौजूद है, तो उम्मीदवारों में से सबसे कम x-निर्देशांक वाले बिंदु को चुना जाना चाहिए। इस बिंदु P पर कॉल करें। यह चरण बिग O नोटेशन (n) लेता है, जहां n प्रश्न में अंकों की संख्या है।

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

कोण के क्रम में क्रमबद्ध करने के लिए कोण की गणना करने की आवश्यकता नहीं होती है। कोण के किसी भी फ़ंक्शन का उपयोग करना संभव है जो अंतराल (गणित) में मोनोटोनिक है $[0,\pi ]$ . डॉट उत्पाद का उपयोग करके कोसाइन की गणना आसानी से की जाती है, या रेखा के ढलान का उपयोग किया जा सकता है। यदि संख्यात्मक परिशुद्धता दांव पर है, तो सॉर्टिंग एल्गोरिदम द्वारा उपयोग किया जाने वाला तुलना फ़ंक्शन सापेक्ष कोण निर्धारित करने के लिए क्रॉस उत्पाद के संकेत का उपयोग कर सकता है।

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

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

फिर, यह निर्धारित करने के लिए कि क्या तीन बिंदु बाएं मोड़ या दाएं मोड़ का गठन करते हैं, दो रेखा खंडों के बीच वास्तविक कोण की गणना करने की आवश्यकता नहीं है, और वास्तव में केवल सरल अंकगणित के साथ प्राप्त किया जा सकता है। तीन अंक के लिए $P_{1}=(x_{1},y_{1})$, $P_{2}=(x_{2},y_{2})$ और $P_{3}=(x_{3},y_{3})$, दो वेक्टर (ज्यामितीय) के क्रॉस उत्पाद के z-निर्देशांक की गणना करें ${\overrightarrow {P_{1}P_{2}}}$ और ${\overrightarrow {P_{1}P_{3}}}$, जो अभिव्यक्ति द्वारा दिया गया है $(x_{2}-x_{1})(y_{3}-y_{1})-(y_{2}-y_{1})(x_{3}-x_{1})$. यदि परिणाम 0 है, तो बिंदु संरेख हैं; यदि यह सकारात्मक है, तो तीन बिंदु बाएं मोड़ या वामावर्त अभिविन्यास का गठन करते हैं, अन्यथा दाएं मोड़ या दक्षिणावर्त अभिविन्यास (वामावर्त क्रमांकित बिंदुओं के लिए) का गठन करते हैं।

यह प्रक्रिया अंततः उसी बिंदु पर वापस आ जाएगी जहां से यह शुरू हुई थी, जिस बिंदु पर एल्गोरिदम पूरा हो गया है और स्टैक में अब उत्तल पतवार पर वामावर्त क्रम में बिंदु शामिल हैं।

समय जटिलता

बिंदुओं को क्रमबद्ध करने में समय जटिलता O(n log n) होती है। हालांकि ऐसा लग सकता है कि लूप की समय जटिलता O(n) है²), क्योंकि प्रत्येक बिंदु के लिए यह जांचने के लिए वापस जाता है कि क्या पिछले बिंदुओं में से कोई दाहिनी ओर मुड़ता है, यह वास्तव में O(n) है, क्योंकि प्रत्येक बिंदु को कुछ अर्थों में अधिकतम दो बार माना जाता है। प्रत्येक बिंदु एक बिंदु के रूप में केवल एक बार ही प्रकट हो सकता है $(x_{2},y_{2})$ बाएं मोड़ में (क्योंकि एल्गोरिदम अगले बिंदु पर आगे बढ़ता है $(x_{3},y_{3})$ इसके बाद), और एक बिंदु के रूप में $(x_{2},y_{2})$ दाएँ मोड़ में (क्योंकि बिंदु $(x_{2},y_{2})$ हटा दिया गया)। इसलिए समग्र समय जटिलता O(n log n) है, क्योंकि क्रमबद्ध करने का समय वास्तव में उत्तल पतवार की गणना करने के समय पर हावी होता है।

स्यूडोकोड

नीचे दिया गया छद्मकोड फ़ंक्शन ccw का उपयोग करता है: ccw > 0 यदि तीन बिंदु वामावर्त घुमाते हैं, यदि ccw < 0 है तो दक्षिणावर्त घुमाएँ, और यदि ccw = 0 है तो संरेख। (वास्तविक अनुप्रयोगों में, यदि निर्देशांक मनमाने ढंग से वास्तविक संख्याएँ हैं, तो फ़ंक्शन की आवश्यकता होती है फ़्लोटिंग-पॉइंट संख्याओं की सटीक तुलना, और लगभग संरेख बिंदुओं के लिए संख्यात्मक विलक्षणताओं से सावधान रहना होगा।)

फिर परिणाम को इसमें संग्रहीत होने दें stack.

अंकों को अंकों की सूची बनने दें
चलो स्टैक = खाली_स्टैक ()

सबसे निचला y-निर्देशांक और सबसे बायां बिंदु खोजें, जिसे P0 कहा जाता है
बिंदुओं को P0 के साथ ध्रुवीय कोण के आधार पर क्रमबद्ध करें, यदि कई बिंदुओं का ध्रुवीय कोण समान है तो केवल सबसे दूर रखें

बिंदुओं में बिंदु के लिए:
 # यदि हम इस बिंदु तक पहुंचने के लिए दक्षिणावर्त मुड़ते हैं तो स्टैक से अंतिम बिंदु पॉप करें
 जबकि गिनती स्टैक > 1 और ccw(next_to_top(stack), शीर्ष(स्टैक), पॉइंट) <= 0:
 पॉप स्टैक
 स्टैक करने के लिए पुश पॉइंट
अंत

अब स्टैक में उत्तल पतवार है, जहां बिंदु वामावर्त उन्मुख हैं और P0 पहला बिंदु है।

यहाँ, next_to_top() स्टैक को बदले बिना, आइटम को स्टैक के शीर्ष के नीचे प्रविष्टि में वापस करने का फ़ंक्शन है, और इसी तरह, top() सर्वोच्च तत्व को वापस करने के लिए।

यह छद्म कोड एल्गोरिदम के परिचय से अनुकूलित है।

टिप्पणियाँ

The same basic idea works also if the input is sorted on x-coordinate instead of angle, and the hull is computed in two steps producing the upper and the lower parts of the hull respectively. This modification was devised by A. M. Andrew. It has the same basic properties as Graham's scan.

Graham's original description involved sorting around an interior point of the convex hull, rather than one of its vertices.