# C++ Program to Implement Gift Wrapping Algorithm in Two Dimensions

This is a C++ Program to implement Gift Wrapping algorithm to find convex hull in two dimensional space. In computational geometry, the gift wrapping algorithm is an algorithm for computing the convex hull of a given set of points. In the two-dimensional case the algorithm is also known as Jarvis march, after R. A. Jarvis, who published it in 1973; it has O(nh) time complexity, where n is the number of points and h is the number of points on the convex hull. Its real-life performance compared with other convex hull algorithms is favorable when n is small or h is expected to be very small with respect to n. In general cases the algorithm is outperformed by many others.

Here is source code of the C++ Program to Implement Gift Wrapping Algorithm in Two Dimensions. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

1. `// A C++ program to find convex hull of a set of points`
2. `// Refer http://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/`
3. `// for explanation of orientation()`
4. `#include <iostream>`
5. `using namespace std;`
6. ` `
7. `// Define Infinite (Using INT_MAX caused overflow problems)`
8. `#define INF 10000`
9. ` `
10. `struct Point`
11. `{`
12. `        int x;`
13. `        int y;`
14. `};`
15. ` `
16. `// To find orientation of ordered triplet (p, q, r).`
17. `// The function returns following values`
18. `// 0 --> p, q and r are colinear`
19. `// 1 --> Clockwise`
20. `// 2 --> Counterclockwise`
21. `int orientation(Point p, Point q, Point r)`
22. `{`
23. `    int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);`
24. ` `
25. `    if (val == 0)`
26. `        return 0; // colinear`
27. `    return (val > 0) ? 1 : 2; // clock or counterclock wise`
28. `}`
29. ` `
30. `// Prints convex hull of a set of n points.`
31. `void convexHull(Point points[], int n)`
32. `{`
33. `    // There must be at least 3 points`
34. `    if (n < 3)`
35. `        return;`
36. ` `
37. `    // Initialize Result`
38. `    int next[n];`
39. `    for (int i = 0; i < n; i++)`
40. `        next[i] = -1;`
41. ` `
42. `    // Find the leftmost point`
43. `    int l = 0;`
44. `    for (int i = 1; i < n; i++)`
45. `        if (points[i].x < points[l].x)`
46. `            l = i;`
47. ` `
48. `    // Start from leftmost point, keep moving counterclockwise`
49. `    // until reach the start point again`
50. `    int p = l, q;`
51. `    do`
52. `    {`
53. `        // Search for a point 'q' such that orientation(p, i, q) is`
54. `        // counterclockwise for all points 'i'`
55. `        q = (p + 1) % n;`
56. `        for (int i = 0; i < n; i++)`
57. `            if (orientation(points[p], points[i], points[q]) == 2)`
58. `                q = i;`
59. ` `
60. `        next[p] = q; // Add q to result as a next point of p`
61. `        p = q; // Set p as q for next iteration`
62. `    }`
63. `    while (p != l);`
64. ` `
65. `    // Print Result`
66. `    for (int i = 0; i < n; i++)`
67. `    {`
68. `        if (next[i] != -1)`
69. `            cout << "(" << points[i].x << ", " << points[i].y << ")\n";`
70. `    }`
71. `}`
72. ` `
73. `// Driver program to test above functions`
74. `int main()`
75. `{`
76. `    Point points[] = { { 0, 3 }, { 2, 2 }, { 1, 1 }, { 2, 1 }, { 3, 0 },`
77. `            { 0, 0 }, { 3, 3 } };`
78. `    cout << "The points in the convex hull are: ";`
79. `    int n = sizeof(points) / sizeof(points[0]);`
80. `    convexHull(points, n);`
81. `    return 0;`
82. `}`

Output:

```\$ g++ GiftWrapping2D.cpp
\$ a.out

The points in the convex hull are: (0, 3)
(3, 0)
(0, 0)
(3, 3)

------------------
(program exited with code: 0)

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.