볼록 껍질은 주어진 모든 데이터 포인트를 포함할 수 있는 최소 폐쇄 영역입니다.
Graham의 스캔 알고리즘은 볼록 껍질의 모서리 지점을 찾습니다. 이 알고리즘에서는 처음에 가장 낮은 지점을 선택합니다. 그 점은 볼록 껍질의 시작점입니다. 나머지 n-1 정점은 시작점에서 반시계 방향을 기준으로 정렬됩니다. 2개 이상의 점이 같은 각을 형성하고 있는 경우 시작점에서 가장 먼 점을 제외하고 같은 각의 모든 점을 제거합니다.
나머지 포인트에서 스택으로 푸시합니다. 그리고 스택 맨 위 포인트, 두 번째 맨 위 포인트 및 새로 선택한 포인트 포인트[i]의 방향이 반시계 방향이 아닐 때 스택에서 항목을 하나씩 제거하고, 확인 후 포인트[i]를 스택에 삽입합니다.
입력 및 출력
Input: Set of points: {(-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)} Output: Boundary points of convex hull are: (-9, -5) (-10, 3) (-10, 4) (-7, 8) (8, 6) (8, -7) (6, -10)
알고리즘
findConvexHull(points, n)
입력 - 포인트 세트, 포인트 수.
출력 - 볼록 껍질의 경계점입니다.
Begin minY := points[0].y min := 0 for i := 1 to n-1 do y := points[i].y if y < minY or minY = y and points[i].x < points[min].x, then minY := points[i].y min := i done swap points[0] and points[min] p0 := points[0] sort points from points[1] to end arrSize := 1 for i := 1 to n, do when i < n-1 and (p0, points[i], points[i+1]) are collinear, do i := i + 1 done points[arrSize] := points[i] arrSize := arrSize + 1 done if arrSize < 3, then return cHullPoints push points[0] into stack push points[1] into stack push points[2] into stack for i := 3 to arrSize, do while top of stack, item below the top and points[i] is not in anticlockwise rotation, do delete top element from stack done push points[i] into stack done while stack is not empty, do item stack top element into cHullPoints pop from stack done End
예
#include<iostream> #include<stack> #include<algorithm> #include<vector> using namespace std; struct point { //define points for 2d plane int x, y; }; point p0; //used to another two points point secondTop(stack<point>&stk) { point tempPoint = stk.top(); stk.pop(); point res = stk.top(); //get the second top element stk.push(tempPoint); //push previous top again return res; } int squaredDist(point p1, point p2) { return ((p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y)); } int direction(point a, point b, point c) { int val = (b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y); if (val == 0) return 0; //colinear else if(val < 0) return 2; //anti-clockwise direction return 1; //clockwise direction } int comp(const void *point1, const void*point2) { point *p1 = (point*)point1; point *p2 = (point*)point2; int dir = direction(p0, *p1, *p2); if(dir == 0) return (squaredDist(p0, *p2) >= squaredDist(p0, *p1))?-1 : 1; return (dir==2)? -1 : 1; } vector<point>findConvexHull(point points[], int n) { vector<point> convexHullPoints; int minY = points[0].y, min = 0; for(int i = 1; i<n; i++) { int y = points[i].y; //find bottom most or left most point if((y < minY) || (minY == y) && points[i].x < points[min].x) { minY = points[i].y; min = i; } } swap(points[0], points[min]); //swap min point to 0th location p0 = points[0]; qsort(&points[1], n-1, sizeof(point), comp); //sort points from 1 place to end int arrSize = 1; //used to locate items in modified array for(int i = 1; i<n; i++) { //when the angle of ith and (i+1)th elements are same, remove points while(i < n-1 && direction(p0, points[i], points[i+1]) == 0) i++; points[arrSize] = points[i]; arrSize++; } if(arrSize < 3) return convexHullPoints; //there must be at least 3 points, return empty list. //create a stack and add first three points in the stack stack<point> stk; stk.push(points[0]); stk.push(points[1]); stk.push(points[2]); for(int i = 3; i<arrSize; i++) { //for remaining vertices while(direction(secondTop(stk), stk.top(), points[i]) != 2) stk.pop(); //when top, second top and ith point are not making left turn, remove point stk.push(points[i]); } while(!stk.empty()) { convexHullPoints.push_back(stk.top()); //add points from stack stk.pop(); } } int main() { point points[] = {{-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}}; int n = 18; vector<point> result; result = findConvexHull(points, n); cout << "Boundary points of convex hull are: "<<endl; vector<point>::iterator it; for(it = result.begin(); it!=result.end(); it++) cout << "(" << it->x << ", " <<it->y <<") "; }
출력
Boundary points of convex hull are: (-9, -5) (-10, 3) (-10, 4) (-7, 8) (8, 6) (8, -7) (6, -10)