<\/div>
#include <bits\/stdc++.h>using namespace std; struct Point{ int x, y;}; \/\/ To find orientation of ordered triplet (p, q, r).\/\/ The function returns following values\/\/ 0 --> p, q and r are colinear\/\/ 1 --> Clockwise\/\/ 2 --> Counterclockwiseint 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; \/\/ colinear return (val > 0)? 1: 2; \/\/ clock or counterclock wise} \/\/ Prints convex hull of a set of n points.void convexHull(Point points[], int n){ \/\/ There must be at least 3 points if (n < 3) return; \/\/ Initialize Result vector<Point> hull; \/\/ Find the leftmost point int l = 0; for (int i = 1; i < n; i++) if (points[i].x < points[l].x) l = i; \/\/ Start from leftmost point, keep moving counterclockwise \/\/ until reach the start point again. This loop runs O(h) \/\/ times where h is number of points in result or output. int p = l, q; do { \/\/ Add current point to result hull.push_back(points[p]); \/\/ Search for a point 'q' such that orientation(p, x, \/\/ q) is counterclockwise for all points 'x'. The idea \/\/ is to keep track of last visited most counterclock- \/\/ wise point in q. If any point 'i' is more counterclock- \/\/ wise than q, then update q. q = (p+1)%n; for (int i = 0; i < n; i++) { \/\/ If i is more counterclockwise than current q, then \/\/ update q if (orientation(points[p], points[i], points[q]) == 2) q = i; } \/\/ Now q is the most counterclockwise with respect to p \/\/ Set p as q for next iteration, so that q is added to \/\/ result 'hull' p = q; } while (p != l); \/\/ While we don't come to first point \/\/ Print Result for (int i = 0; i < hull.size(); i++) cout << "(" << hull[i].x << ", " << hull[i].y << ")\\n";} \/\/ Driver program to test above functionsint 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;}<\/code><\/pre> <\/div>\n<\/div>\n<\/div>\n <\/p>\n
Output:<\/strong> The output is points of the convex hull.<\/p>\n(0, 3)\r\n(0, 0)\r\n(3, 0)\r\n(3, 3)<\/pre>\nTime Complexity:<\/strong> For every point on the hull we examine all the other points to determine the next point. Time complexity is ?(m * n) where n is number of input points and m is number of output or hull points (m <= n). In worst case, time complexity is O(n 2<\/sup>). The worst case occurs when all the points are on the hull (m = n)<\/p>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"Convex Hull | Set 1 (Jarvis\u2019s Algorithm or Wrapping) – Geometric Algorithms – The idea of Jarvis\u2019s Algorithm is simple, we start from the leftmost point.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,73905,83572],"tags":[72929,76001,76002,76004,76005,76003,76000,76006],"class_list":["post-25897","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-geometric-algorithms","category-jarviss-algorithm","tag-convex-hull-algorithm","tag-convex-hull-c","tag-convex-hull-definition","tag-convex-hull-divide-and-conquer","tag-convex-hull-example","tag-convex-hull-geeksforgeeks","tag-convex-hull-graham-scan","tag-convex-hull-in-image-processing"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25897","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25897"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25897\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25897"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25897"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25897"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
![\"Convex](\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/convexHull1.png\")
![\"Convex](\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/convexHull1-1.png\")
<\/p>\n