ग्राहम स्कैन

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

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

एल्गोरिथम

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

इस एल्गोरिदम में पहला कदम सबसे कम 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. For the same choice of a pivot point for the sorting algorithm, connecting all of the other points in their sorted order around this point rather than performing the remaining steps of the Graham scan produces a star-shaped polygon, a polygonalization of the input.

The stack technique used in Graham's scan is very similar to that for the all nearest smaller values problem, and parallel algorithms for all nearest smaller values may also be used (like Graham's scan) to compute convex hulls of sorted sequences of points efficiently.

संख्यात्मक मजबूती

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

यह भी देखें

• उत्तल पतवार एल्गोरिदम

अग्रिम पठन

• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "33.3: Finding the convex hull". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 949–955. ISBN 0-262-03293-7.