বিবেচনা করুন আমাদের একটি পয়েন্ট সেট আছে। আমাদের সকল পয়েন্ট কভার করে একটি সিম্পল ক্লোজড পাথ বের করতে হবে। নিচে পয়েন্টগুলো এবং বन्द পাথের চিত্র দেওয়া হলো:
পাথ পেতে নিচের ধাপগুলো অনুসরণ করতে হবে:
- সবচেয়ে নিচের বাম পয়েন্টটি খুঁজে বের করুন (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),
