ตัวเรือนูนเป็นพื้นที่ปิดขั้นต่ำที่สามารถครอบคลุมจุดข้อมูลทั้งหมดที่กำหนดได้
อัลกอริธึม Scan ของ Graham จะค้นหาจุดมุมของตัวเรือนูน ในอัลกอริธึมนี้ อันดับแรกจะเลือกจุดต่ำสุด จุดนั้นเป็นจุดเริ่มต้นของตัวเรือนูน จุดยอด n-1 ที่เหลือจะถูกจัดเรียงตามทิศทางทวนเข็มนาฬิกาจากจุดเริ่มต้น หากจุดสองจุดขึ้นไปก่อตัวเป็นมุมเดียวกัน ให้ลบจุดที่มีมุมเดียวกันทั้งหมดยกเว้นจุดที่ไกลที่สุดจากจุดเริ่มต้น
จากจุดที่เหลือ ดันเข้าไปในกอง และนำรายการออกจากสแต็กทีละรายการ เมื่อการวางแนวไม่ทวนเข็มนาฬิกาสำหรับจุดบนสุดของสแต็ก จุดบนสุดที่สอง และจุดที่เลือกใหม่[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(แต้ม, 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)
