ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมค้นหาส่วนนูนของชุดจุดที่กำหนดโดยใช้อัลกอริทึมของจาร์วิส
ตัวเรือนูนเป็นรูปนูนรูปหลายเหลี่ยมที่เล็กที่สุดที่มีจุดที่กำหนดทั้งหมดไม่ว่าจะอยู่ที่ขอบด้านในของรูปหรือไม่
ในอัลกอริธึมของจาร์วิส เราเลือกจุดซ้ายสุดและให้จุดตัดเคลื่อนที่ไปตามทิศทางตามเข็มนาฬิกา
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
//structure of the point
struct Point{
int x, y;
};
//calculating the position of the points
int cal_orientation(Point p, Point q, Point r){
int val = (q.y - p.y) * (r.x - q.x) -
(q.x - p.x) * (r.y - q.y);
if (val == 0) return 0; //collinear
return (val > 0)? 1: 2; //clock or counterclockwise
}
//printing convex hull
void convexHull(Point points[], int n){
if (n < 3) return;
vector<Point> hull;
//calculating the leftmost point
int l = 0;
for (int i = 1; i < n; i++)
if (points[i].x < points[l].x)
l = i;
//moving in the clockwise direction
int p = l, q;
do{
//adding current point to result
hull.push_back(points[p]);
q = (p+1)%n;
for (int i = 0; i < n; i++){
if (cal_orientation(points[p], points[i], points[q]) == 2)
q = i;
}
p = q;
} while (p != l); //if didn't reached the first point
for (int i = 0; i < hull.size(); i++)
cout << "(" << hull[i].x << ", "
<< hull[i].y << ")\n";
}
int main(){
Point points[] = {{0, 3}, {2, 2}, {1, 1}, {2, 1},
{3, 0}, {0, 0}, {3, 3}};
int n = sizeof(points)/sizeof(points[0]);
convexHull(points, n);
return 0;
} ผลลัพธ์
(0, 3) (0, 0) (3, 0) (3, 3)
