점 집합이 있다고 가정합니다. 우리는 모든 점을 포함하는 간단한 닫힌 경로를 찾아야 합니다. 포인트가 아래와 같으며 다음 이미지가 해당 포인트에 닫힌 경로를 만들고 있다고 가정합니다.
경로를 얻으려면 다음 단계를 따라야 합니다 -
-
왼쪽 하단 점을 P
로 찾습니다. -
P를 중심으로 시계 반대 방향으로 극각을 기준으로 다른 n – 1 점을 정렬하고 두 점의 극각이 같으면 거리가 가장 짧은 것으로 배치하십시오.
-
정렬된 포인트 목록을 탐색한 다음 경로를 만듭니다.
예시
#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),