Convex Hull

Geeks

Description:

Given a set of points in the plane. the convex hull of the set is the smallest convex polygon that contains all the points of it.

Example:

Note

Idea:

Time O(nlogn)

Using Graham’s scan algorithm, we can find Convex Hull in O(nLogn) time. Following is Graham’s algorithm

Let points[0..n-1] be the input array.

1) Find the bottom-most point by comparing y coordinate of all points. If there are two points with same y value, then the point with smaller x coordinate value is considered. Let the bottom-most point be P0. Put P0 at first position in output hull.

2) Consider the remaining n-1 points and sort them by polor angle in counterclockwise order around points[0]. If polor angle of two points is same, then put the nearest point first.

3 After sorting, check if two or more points have same angle. If two more points have same angle, then remove all same angle points except the point farthest from P0. Let the size of new array be m.

4) If m is less than 3, return (Convex Hull not possible)

5) Create an empty stack ‘S’ and push points[0], points[1] and points[2] to S.

6) Process remaining m-3 points one by one. Do following for every point ‘points[i]’ 4.1) Keep removing points from stack while orientation of following 3 points is not counterclockwise (or they don’t make a left turn). a) Point next to top in stack b) Point at the top of stack c) points[i] 4.2) Push points[i] to S

5) Print contents of S

https://www.geeksforgeeks.org/convex-hull-set-2-graham-scan/

Code:

Code