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)
Press return to continue

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

advertisement
advertisement

Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.