# C++ Program to Find the Convex Hull using Jarvis March

«
»
This is a C++ Program to implement Jarvis March to find convex hull. The idea of Jarvis’s Algorithm is simple, we start from the leftmost point (or point with minimum x coordinate value) and we keep wrapping points in counterclockwise direction.

Here is source code of the C++ Program to Implement Jarvis March to Find the Convex Hull. 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);`
80. `    convexHull(points, n);`
81. `    return 0;`
82. `}`

Output:

```\$ g++ JarvisMarch.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.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now! 