जार्विस मार्च एल्गोरिथम का उपयोग डेटा बिंदुओं के दिए गए सेट से उत्तल पतवार के कोने बिंदुओं का पता लगाने के लिए किया जाता है।
डेटा सेट के सबसे बाएं बिंदु से शुरू करते हुए, हम उत्तल पतवार में बिंदुओं को वामावर्त घुमाकर रखते हैं। वर्तमान बिंदु से, हम वर्तमान बिंदु से उन बिंदुओं के उन्मुखीकरण की जाँच करके अगला बिंदु चुन सकते हैं। जब कोण सबसे बड़ा होता है, तो बिंदु चुना जाता है। सभी बिंदुओं को पूरा करने के बाद, जब अगला बिंदु प्रारंभ बिंदु हो, तो एल्गोरिथम को रोकें।
इनपुट और आउटपुट
इनपुट:अंकों का सेट:{(-7,8), (-4,6), (2,6), (6,4), (8,6), (7,-2), ( 4,-6), (8,-7),(0,0), (3,- 2),(6,-10),(0,6),(-9,-5),(-8 ,-2),(-8,0),(-10,3),(-2,2),(-10,4)}आउटपुट:उत्तल पतवार के सीमा बिंदु हैं:(-9, -5) ( 6, -10) (8, -7) (8, 6) (-7, 8) (-10, 4) (-10, 3) एल्गोरिदम
findConvexHull(points, n)
इनपुट: अंक, अंकों की संख्या।
आउटपुट: उत्तल पतवार के कोने बिंदु।
प्रारंभ प्रारंभ:=अंक[0] प्रत्येक बिंदु के लिए i, यदि अंक[i].x0, तो अगला:=अंक [i] colPts सरणी को साफ़ करें और यदि cal =0 है, तो यदि अगला अंक से वर्तमान के करीब है [i] , फिर अगले colPts में अगला जोड़ें:=अंक [i] और colPts में अंक जोड़ें [i] किए गए colPts में सभी आइटम जोड़ें यदि अगला =प्रारंभ होता है, तो परिणाम वर्तमान में लूप डालने के बगल में तोड़ें:=अगला किया वापसी परिणामअंत
उदाहरण
#शामिल करें बूल ऑपरेटर ==(बिंदु p2) { अगर (x ==p2.x &&y ==p2.y) वापसी 1; वापसी 0; } बूल ऑपरेटर <(कॉन्स्ट पॉइंट और पी 2) कॉन्स्ट {// डमी तुलना फ़ंक्शन सेट रिटर्न ट्रू में सॉर्ट करने के लिए उपयोग किया जाता है; }};int crossProduct(point a, point b, point c) { // ab वेक्टर से c का स्थान ढूँढता है int y1 =a.y - b.y; इंट y2 =a.y - c.y; इंट x1 =a.x - b.x; इंट x2 =a.x - c.x; वापसी y2*x1 - y1*x2; // यदि परिणाम <0, सी बाईं ओर,> 0, सी दाईं ओर, =0, ए, बी, सी कॉललाइनर हैं} अंतर दूरी (बिंदु ए, बिंदु बी, बिंदु सी) { int y1 =ay - by; इंट y2 =a.y - c.y; इंट x1 =a.x - b.x; इंट x2 =a.x - c.x; इंट आइटम1 =(y1*y1 + X1*x1); इंट आइटम2 =(y2*y2 + x2*x2); अगर (आइटम 1 ==आइटम 2) वापसी 0; // जब बी और सी एक और से समान दूरी पर हों अगर (आइटम 1 <आइटम 2) रिटर्न -1; // जब b रिटर्न 1 के करीब हो; // जब सी एक के करीब है सेट <बिंदु> findConvexHull (बिंदु बिंदु [], int n) {बिंदु प्रारंभ =अंक [0]; for(int i =1; i परिणाम; // सेट का उपयोग डुप्लिकेट बिंदुओं के प्रवेश से बचने के लिए किया जाता है result.insert(start); वेक्टर<बिंदु> *collinearPoints =नया वेक्टर<बिंदु>; जबकि (सच) {बिंदु अगला लक्ष्य =अंक [0]; for(int i =1; i 0) {// जब ith बिंदु बाईं ओर है अगला लक्ष्य =अंक [i]; CollinearPoints =नया वेक्टर <बिंदु>; // कोलीनियर पॉइंट्स को रीसेट करें} और अगर (वैल ==0) {//अगर तीन पॉइंट कॉललाइनर हैं अगर (दूरी (करंट, नेक्स्ट टार्गेट, पॉइंट्स [i]) <0) {// कोलीनियर लिस्ट कोलीनियर पॉइंट्स में करीब एक जोड़ें-> पुश_बैक (अगला लक्ष्य); अगला लक्ष्य =अंक [i]; } और { CollinearPoints-> push_back (अंक [i]); // जब ith बिंदु अगले लक्ष्य के करीब या समान हो } } सदिश <बिंदु> ::iterator; for(it =collinearPoints->begin(); it !=collinearPoints->end(); it++) { result.insert(*it); // परिणाम सेट करने के लिए कोलिनियर पॉइंट्स में सभी बिंदुओं को जोड़ें} अगर (अगला लक्ष्य ==प्रारंभ) // जब अगला बिंदु शुरू होता है तो इसका मतलब है, क्षेत्र को तोड़ना; result.insert (अगला लक्ष्य); वर्तमान =अगला लक्ष्य; } वापसी परिणाम;} इंट मुख्य () {बिंदु बिंदु [] ={{-7,8}, {-4,6}, {2,6}, {6,4}, {8,6}, {7 ,-2},{4,-6},{8,-7},{0,0}, {3,-2},{6,-10},{0,-6},{-9, -5},{-8,-2},{-8,0},{-10,3},{-2,2},{-10,4}}; इंट एन =18; सेट <बिंदु> परिणाम; परिणाम =findConvexHull (अंक, n); cout <<"उत्तल पतवार के सीमा बिंदु हैं:"< ::इसे पुनरावृत्त करें; for(it =result.begin(); it!=result.end(); it++) cout <<"(" <x <<"," <y <<") "; } आउटपुट
उत्तल पतवार के सीमा बिंदु हैं:(-9, -5) (6, -10) (8, -7) (8, 6) (-7, 8) (-10, 4) (-10, 3)