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

एक न्यूनतम उत्तल पतवार की अवधारणा

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

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

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

def rotate(A,B,C): return (B[0]-A[0])*(C[1]-B[1])-(B[1]-A[1])*(C[0]-B[0])

ग्राहम का एल्गोरिथम (ग्राहम स्कैन)

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

 def grahamscan(A): n = len(A) #   P = range(n) #    for i in range(1,n): if A[P[i]][0]<A[P[0]][0]: #  P[i]-    P[0]-  P[i], P[0] = P[0], P[i] #

ग्राहम एल्गोरिथ्म में दूसरा चरण सभी बिंदुओं की छंटाई है (पी [0] वें को छोड़कर), उनके वामपंथ की डिग्री द्वारा प्रारंभिक बिंदु आर = ए _{पी [0] के} सापेक्ष। हम कहते हैं कि B <C यदि बिंदु C, वेक्टर RB के बाईं ओर है।

इस तरह के आदेश को निष्पादित करने के लिए, तत्वों की जोड़ीवार तुलना के आधार पर किसी भी छंटाई एल्गोरिथ्म, उदाहरण के लिए, त्वरित छंटाई, का उपयोग किया जा सकता है। किसी कारण के लिए (मुख्य एक अनाड़ी ^* हाथ), मैं सम्मिलन छँटाई का उपयोग करूँगा।
* _{मैं उन लोगों का बहुत आभारी रहूंगा जो मुझे समझा सकते हैं कि इस मामले में अंतर्निहित पायथन को कैसे लागू किया जाए ...}
इसलिए, आवेषण द्वारा छंटनी (अप्रत्यक्ष पते के बारे में मत भूलो और शून्य बिंदु को हल नहीं किया जाता है):

  for i in range(2,n): j = i while j>1 and (rotate(A[P[0]],A[P[j-1]],A[P[j]])<0): P[j], P[j-1] = P[j-1], P[j] j -= 1

छँटाई के परिणाम को निम्न आकृति द्वारा चित्रित किया जा सकता है।

यदि हम अब इस क्रम में बिंदुओं को जोड़ते हैं, तो हमें एक बहुभुज मिलता है, जो, हालांकि, उत्तल नहीं है।

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

  S = [P[0],P[1]]

फिर हम सभी अन्य कोने के माध्यम से देखते हैं, और एस स्टैक में अंतिम दो कोने के दृष्टिकोण से उनमें रोटेशन की दिशा को ट्रैक करते हैं: यदि यह दिशा नकारात्मक है, तो आप स्टैक से अंतिम शीर्ष को हटाकर कोण काट सकते हैं। जैसे ही मोड़ सकारात्मक होता है, कोनों को काटना पूरा हो जाता है, वर्तमान शीर्ष को स्टैक पर धकेल दिया जाता है।

  for i in range(2,n): while rotate(A[S[-2]],A[S[-1]],A[P[i]])<0: del S[-1] # pop(S) S.append(P[i]) # push(S,P[i])

नतीजतन, स्टैक एस (जिसे अब एक सूची के रूप में देखा जा सकता है) में वांछित अनुक्रम में वर्टीकल, इसके अलावा वांछित अनुक्रम होता है, जो अंकों के एक सेट के एमबीओ को निर्धारित करता है।

  return S

एल्गोरिथ्म के पहले और आखिरी चरणों की जटिलता n में रैखिक है (हालांकि बाद के मामले में एक नेस्टेड लूप है, हालांकि, इस चक्र के अंदर प्रत्येक शीर्ष को एक बार स्टैक पर धकेल दिया जाता है, और वहां से एक बार से अधिक नहीं हटाया जाता है), इसलिए, पूरे एल्गोरिथ्म की जटिलता दूसरे चरण से निर्धारित होती है - छँटाई, यही वजह है कि प्रविष्टि छँटाई बड़े n के लिए सबसे अच्छा विकल्प नहीं है। यदि हम इसे त्वरित छँटाई के साथ प्रतिस्थापित करते हैं, तो हमें O (nlogn) एल्गोरिथ्म की कुल जटिलता मिलती है। क्या इस समय को सुधारा जा सकता है? यदि एल्गोरिथ्म बिंदुओं (जैसे हमारे) की जोड़ीदार तुलना पर आधारित है, तो यह साबित होता है कि यह अनुमान आमतौर पर सुधार नहीं हुआ है। इस दृष्टिकोण से, ग्राहम एल्गोरिथम इष्टतम है। फिर भी, इसकी एक बहुत अच्छी विशेषता नहीं है - यह इस अर्थ में अनुकूल नहीं है कि इससे कोई फर्क नहीं पड़ता कि कितने कोने अंततः एमबीओ (तीन, पांच, दस या एन) में प्रवेश करते हैं, सभी एक ही समय में रैखिक-लघुगणक होंगे। जार्विस एल्गोरिथ्म में ऐसी अनुकूलन क्षमता होती है, जिससे हम आसानी से आगे बढ़ते हैं।

पूर्ण ग्राहम एल्गोरिथम कोड

 def grahamscan(A): n = len(A) #   P = range(n) #    for i in range(1,n): if A[P[i]][0]<A[P[0]][0]: #  P[i]-    P[0]-  P[i], P[0] = P[0], P[i] #      for i in range(2,n): #   j = i while j>1 and (rotate(A[P[0]],A[P[j-1]],A[P[j]])<0): P[j], P[j-1] = P[j-1], P[j] j -= 1 S = [P[0],P[1]] #   for i in range(2,n): while rotate(A[S[-2]],A[S[-1]],A[P[i]])<0: del S[-1] # pop(S) S.append(P[i]) # push(S,P[i]) return S

जार्विस एल्गोरिथ्म

जार्विस एल्गोरिथ्म (दूसरा नाम गिफ्ट रैपिंग एल्गोरिदम है) वैचारिक रूप से ग्राहम एल्गोरिदम की तुलना में सरल है। यह दो-चरणीय है और इसमें छंटाई की आवश्यकता नहीं है। पहला चरण बिल्कुल वैसा ही है - हमें एक प्रारंभिक बिंदु की आवश्यकता है, जिसे एमबीओ में शामिल करने की गारंटी है, बाएं बिंदु को ए से ले जाएं।

 def jarvismarch(A): n = len(A) P = range(n) for i in range(1,n): if A[P[i]][0]<A[P[0]][0]: P[i], P[0] = P[0], P[i]

एल्गोरिथ्म के दूसरे चरण में, एमबीओ बनाया गया है। विचार: प्रारंभिक शीर्ष को चालू करें, वर्तमान शीर्ष के सापेक्ष A के सबसे दाहिने बिंदु को देखें, इसे वर्तमान करें, आदि। प्रक्रिया तब समाप्त होती है जब शुरुआती वर्टिक्स फिर से चालू होता है। जैसे ही बिंदु ने एमबीओ को मारा, उसे अब ध्यान में नहीं लिया जा सकता है। इसलिए, हमारे पास एक और सूची एच है जिसमें एमबीओ के कोने सही क्रम में संग्रहीत किए जाएंगे। हम तुरंत इस सूची में प्रारंभिक शीर्ष दर्ज करते हैं, और सूची P में हम इस शीर्ष को अंत में स्थानांतरित करते हैं (जहां हम अंततः इसे खोज लेंगे और एल्गोरिथम को पूरा करेंगे)।

  H = [P[0]] del P[0] P.append(H[0])

अब हम एक अनंत लूप का आयोजन करते हैं, जिसके प्रत्येक पुनरावृत्ति में हम P के सबसे बाएँ बिंदु P से अंतिम बिंदु के लिए H पर देखते हैं। यदि यह शीर्ष रेखा शुरू हो रही है, तो हम चक्र को बाधित करते हैं, यदि नहीं, तो हम P से H पर पाया गया शीर्ष स्थानान्तरण करते हैं। चक्र पूरा होने के बाद, वांछित शेल H में होता है। जिसके परिणामस्वरूप हम वापस लौटते हैं।

  while True: right = 0 for i in range(1,len(P)): if rotate(A[H[-1]],A[P[right]],A[P[i]])<0: right = i if P[right]==H[0]: break else: H.append(P[right]) del P[right] return H

हम्म, मैं चित्रों का उपयोग किए बिना जार्विस एल्गोरिथ्म के बारे में बात करने में कामयाब रहा। निम्नलिखित आंकड़ा सब कुछ दिखाता है!

हम जार्विस एल्गोरिथ्म की जटिलता का अनुमान लगाते हैं। पहला कदम n में रैखिक है। दूसरा अधिक दिलचस्प है। हमारे पास एक नेस्टेड लूप है, बाह्य पुनरावृत्तियों की संख्या एमबीओ में ज की संख्या के बराबर है, आंतरिक पुनरावृत्तियों की संख्या n से अधिक नहीं है। इसलिए, पूरे एल्गोरिथ्म की जटिलता हे (एचएन) है। इस सूत्र में जो असामान्य है वह यह है कि जटिलता न केवल इनपुट डेटा की लंबाई से निर्धारित होती है, बल्कि आउटपुट की लंबाई (आउटपुट-सेंसिटिव एल्गोरिदम) द्वारा भी निर्धारित की जाती है। और फिर, ~~कार्ड के~~ रूप में , अंक गिर जाएंगे। सबसे खराब स्थिति में, ए से सभी अंक एमबीओ में प्रवेश करते हैं (यानी, ए खुद एक उत्तल बहुभुज है), फिर h = n और जटिलता द्विघात में कूद जाती है। सर्वोत्तम मामले में (बशर्ते कि ए से अंक एक सीधी रेखा पर न पड़ें) h = 3 और जटिलता रैखिक हो जाती है। यह पहले से ही समझ में आता है कि हमारे पास क्या मामला है, क्या करना इतना आसान नहीं है (यदि आपके पास समय मशीन ^{** नहीं है} ), तो हम केवल समस्या की प्रकृति से आगे बढ़ सकते हैं - यदि बहुत सारे बिंदु हैं और वे समान रूप से एक निश्चित क्षेत्र को भरते हैं, तो (शायद) जार्विस तेज़ हो जाएगा यदि क्षेत्र की सीमा पर डेटा एकत्र किया जाता है, तो ग्राहम तेज़ होगा, कुछ इस तरह ...
** _{एक टाइम मशीन आम तौर पर एल्गोरिदम के दृष्टिकोण से एक उपयोगी चीज है, किसी भी कार्य के लिए एक खरब वर्षों की गणना की आवश्यकता होती है जिसे लगभग तुरंत इसकी मदद से हल किया जा सकता है - हम एक कार्यक्रम शुरू करते हैं, एक टाइम मशीन में शामिल होते हैं, भविष्य के लिए "उड़ान" करते हैं, परिणाम पढ़ें, वापस जाएं।} _{यह जानने के लिए रहता है कि ट्रिलियन वर्षों के एक जोड़े के लिए कंप्यूटर के सुचारू संचालन को कैसे सुनिश्चित किया जाए ...}

पूर्ण जार्विस एल्गोरिथ्म कोड

 def jarvismarch(A): n = len(A) P = range(n) # start point for i in range(1,n): if A[P[i]][0]<A[P[0]][0]: P[i], P[0] = P[0], P[i] H = [P[0]] del P[0] P.append(H[0]) while True: right = 0 for i in range(1,len(P)): if rotate(A[H[-1]],A[P[right]],A[P[i]])<0: right = i if P[right]==H[0]: break else: H.append(P[right]) del P[right] return H

एक निष्कर्ष के बजाय

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

आपका ध्यान देने के लिए आप सभी का धन्यवाद!

न्यूनतम उत्तल हल का निर्माण

एक न्यूनतम उत्तल पतवार की अवधारणा

ग्राहम का एल्गोरिथम (ग्राहम स्कैन)

जार्विस एल्गोरिथ्म

एक निष्कर्ष के बजाय

More articles: