मान लीजिए हमारे पास बिंदुओं का एक समुच्चय है। हमें उन सभी बिंदुओं को कवर करने वाला एक सरल बंद पथ ढूंढना है। मान लीजिए बिंदु नीचे जैसे हैं, और अगली छवि उन बिंदुओं पर एक बंद पथ बना रही है।
पथ प्राप्त करने के लिए, हमें इन चरणों का पालन करना होगा -
नीचे-बाएं बिंदु को P के रूप में ढूंढें
अन्य n-1 बिंदुओं को P के चारों ओर ध्रुवीय कोण के आधार पर वामावर्त क्रम में सॉर्ट करें, यदि दो बिंदुओं का ध्रुवीय कोण समान है, तो उन्हें दूरी के आधार पर रखें जो सबसे छोटी हो
सॉर्ट की गई बिंदुओं की सूची को ट्रैवर्स करें, फिर पथ बनाएं
उदाहरण
#include <bits/stdc++.h> using namespace std; class Point { public: int x, y; }; Point p0; int euclid_dist(Point p1, Point p2) { return (p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y); } int orientation(Point p1, Point p2, Point p3) { int val = (p2.y - p1.y) * (p3.x - p2.x) - (p2.x - p1.x) * (p3.y - p2.y); if (val == 0) return 0; // colinear return (val > 0)? 1: 2; // clockwise or counterclock wise } int compare(const void *vp1, const void *vp2) { Point *p1 = (Point *)vp1; Point *p2 = (Point *)vp2; int o = orientation(p0, *p1, *p2); if (o == 0) return (euclid_dist(p0, *p2) >= euclid_dist(p0, *p1))? -1 : 1; return (o == 2)? -1: 1; } void findClosedPath(Point points[], int n) { int y_min = points[0].y, min = 0; for (int i = 1; i < n; i++) { int y = points[i].y; if ((y < y_min) || (y_min == y && points[i].x < points[min].x)) y_min = points[i].y, min = i; } swap(points[0], points[min]); p0 = points[0]; qsort(&points[1], n-1, sizeof(Point), compare); //sort on polar angle for (int i=0; i<n; i++) cout << "(" << points[i].x << ", "<< points[i].y <<"), "; } int main() { Point points[] = {{0, 3}, {1, 1}, {2, 2}, {4, 4},{0, 0}, {1, 2}, {3, 1}, {3, 3}}; int n = sizeof(points)/sizeof(points[0]); findClosedPath(points, n); }आउटपुट
(0, 0), (3, 1), (1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (0, 3),
