Vỏ lồi là vùng kín tối thiểu có thể bao phủ tất cả các điểm dữ liệu đã cho.
Thuật toán Graham’s Scan sẽ tìm các điểm góc của phần lồi của thân tàu. Trong thuật toán này, lúc đầu, điểm thấp nhất được chọn. Điểm đó là điểm bắt đầu của vỏ lồi. N-1 đỉnh còn lại được sắp xếp dựa trên hướng ngược chiều kim đồng hồ từ điểm bắt đầu. Nếu hai hoặc nhiều điểm tạo thành cùng một góc, thì xóa tất cả các điểm có cùng góc đó trừ điểm xa nhất từ đầu.
Từ các điểm còn lại, đẩy chúng vào ngăn xếp. Và xóa từng mục khỏi ngăn xếp một khi hướng không ngược chiều kim đồng hồ đối với điểm trên cùng của ngăn xếp, điểm trên cùng thứ hai và các điểm điểm mới được chọn [i], sau khi kiểm tra, hãy chèn điểm [i] vào ngăn xếp.
Đầu vào và Đầu ra
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) Thuật toán
findConvexHull(points, n)
Đầu vào - Tập hợp các điểm, số điểm.
Đầu ra - Các điểm biên của thân tàu lồi.
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
Ví dụ
#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 <<") ";
} Đầu ra
Boundary points of convex hull are: (-9, -5) (-10, 3) (-10, 4) (-7, 8) (8, 6) (8, -7) (6, -10)