हम गिफ्ट रैपिंग एल्गोरिथम को दो आयामों में लागू करने के लिए एक C++ प्रोग्राम विकसित करेंगे। गिफ़्ट रैपिंग एल्गोरिथम किसी दिए गए बिंदुओं के उत्तल हल की गणना करने के लिए एक एल्गोरिथम है।
एल्गोरिदम
Begin function convexHull() to find convex hull of a set of n points: There must be at least three points. Initialize the result. Find the leftmost point. Starting from leftmost point, keep moving counterclockwise until reach the start point again. Print the result. End
उदाहरण कोड
#include <iostream>
using namespace std;
#define INF 10000
struct P {
int x;
int y;
};
int orient(P a, P b, P c) {
int v = (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y);
if (v == 0)
return 0; // colinear
return (v >0) ? 1 : 2; // clock or counterclock wise
}
void convexHull(P points[], int m) {
if (m < 3)//at least three points required
return;
int n[m];
for (int i = 0; i < m; i++)
n[i] = -1;
int l = 0;//initialize result.
for (int i = 1; i < m; i++)
if (points[i].x < points[l].x)
l = i; //find left most point
int p = l, q;
do {
q = (p + 1) % m;
for (int i = 0; i < m; i++)
if (orient(points[p], points[i], points[q]) == 2)
q = i;
n[p] = q;
p = q;
} while (p != l);
for (int i = 0; i < m; i++) {
if (n[i] != -1)
cout << "(" << points[i].x << ", " << points[i].y << ")\n";
}
}
int main() {
P points[] = {{0, 4}, {2, 1}, {2, 3}, {4, 1}, {3, 0}, {1, 1}, {7, 6}};
cout << "The points in the convex hull are: ";
int n = sizeof(points) / sizeof(points[0]);
convexHull(points, n);
return 0;
} आउटपुट
The points in the convex hull are: (0, 4) (4, 1) (3, 0) (1, 1) (7, 6)