Ở đây chúng ta sẽ xem một ví dụ về thân tàu lồi. Giả sử chúng ta có một tập hợp các điểm. Chúng ta phải tạo một đa giác bằng cách lấy ít điểm hơn, điều đó sẽ bao gồm tất cả các điểm đã cho. Trong phần này, chúng ta sẽ xem thuật toán Jarvis March để lấy phần thân lồi.
Thuật toán Jarvis March được sử dụng để phát hiện các điểm góc của thân tàu lồi từ một tập hợp các điểm dữ liệu nhất định.
Bắt đầu từ điểm bên trái nhất của tập dữ liệu, chúng tôi giữ các điểm trong vỏ lồi bằng cách quay ngược chiều kim đồng hồ. Từ điểm hiện tại, chúng ta có thể chọn điểm tiếp theo bằng cách kiểm tra hướng của những điểm đó từ điểm hiện tại. Khi góc lớn nhất, điểm được chọn. Sau khi hoàn thành tất cả các điểm, khi điểm tiếp theo là điểm bắt đầu, hãy dừng thuật toán.
Đầu vào - Tập hợp điểm:{(-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)}
Đầu ra - Các điểm tiếp giáp của vỏ lồi là -
(-9, -5) (6, -10) (8, -7) (8, 6) (-7, 8) (-10, 4) (-10, 3)
Thuật toán
findConvexHull(points, n) Input: The points, number of points. Output: Corner points of convex hull. Begin start := points[0] for each point i, do if points[i].x < start.x, then // get the left most point start := points[i] done current := start add start point to the result set. define colPts set to store collinear points while true, do //start an infinite loop next := points[i] for all points i except 0th point, do if points[i] = current, then skip the next part, go for next iteration val := cross product of current, next, points[i] if val > 0, then next := points[i] clear the colPts array else if cal = 0, then if next is closer to current than points[i], then add next in the colPts next := points[i] else add points[i] in the colPts done add all items in the colPts into the result if next = start, then break the loop insert next into the result current := next done return result End
Ví dụ
#include<iostream>
#include<set>
#include<vector>
using namespace std;
struct point{ //define points for 2d plane
int x, y;
bool operator==(point p2){
if(x == p2.x && y == p2.y)
return 1;
return 0;
}
bool operator<(const point &p2)const{ //dummy compare function used to sort in set
return true;
}
};
int crossProduct(point a, point b, point c){ //finds the place of c from ab vector
int y1 = a.y - b.y;
int y2 = a.y - c.y;
int x1 = a.x - b.x;
int x2 = a.x - c.x;
return y2*x1 - y1*x2; //if result < 0, c in the left, > 0, c in the right, = 0, a,b,c are collinear
}
int distance(point a, point b, point c){
int y1 = a.y - b.y;
int y2 = a.y - c.y;
int x1 = a.x - b.x;
int x2 = a.x - c.x;
int item1 = (y1*y1 + x1*x1);
int item2 = (y2*y2 + x2*x2);
if(item1 == item2)
return 0; //when b and c are in same distance from a
else if(item1 < item2)
return -1; //when b is closer to a
return 1; //when c is closer to a
}
set<point> findConvexHull(point points[], int n){
point start = points[0];
for(int i = 1; i<n; i++){ //find the left most point for starting
if(points[i].x < start.x)
start = points[i];
}
point current = start;
set<point> result; //set is used to avoid entry of duplicate points
result.insert(start);
vector<point> *collinearPoints = new vector<point>;
while(true){
point nextTarget = points[0];
for(int i = 1; i<n; i++){
if(points[i] == current) //when selected point is current point, ignore rest part
continue;
int val = crossProduct(current, nextTarget, points[i]);
if(val > 0){ //when ith point is on the left side
nextTarget = points[i];
collinearPoints = new vector<point>; //reset collinear points
}else if(val == 0){ //if three points are collinear
if(distance(current, nextTarget, points[i]) < 0){ //add closer one to collinear list
collinearPoints->push_back(nextTarget);
nextTarget = points[i];
}else{
collinearPoints->push_back(points[i]); //when ith point is closer or same as nextTarget
}
}
}
vector<point>::iterator it;
for(it = collinearPoints->begin(); it != collinearPoints->end(); it++){
result.insert(*it); //add allpoints in collinear points to result set
}
if(nextTarget == start) //when next point is start it means, the area covered
break;
result.insert(nextTarget);
current = nextTarget;
}
return result;
}
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;
set<point> result;
result = findConvexHull(points, n);
cout << "Boundary points of convex hull are: "<<endl;
set<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) (6, -10) (8, -7) (8, 6) (-7, 8) (-10, 4) (-10, 3)