Quickhull Algorithm for Convex Hull
The QuickHull algorithm is a Divide and Conquer algorithm similar to QuickSort. Let a[0…n-1] be the input array of points. Following are the steps for finding the convex hull of these points.
Algorithm:
- Find the point with minimum x-coordinate lets say, min_x and similarly the point with maximum x-coordinate, max_x.
- Make a line joining these two points, say L. This line will divide the whole set into two parts. Take both the parts one by one and proceed further.
- For a part, find the point P with maximum distance from the line L. P forms a triangle with the points min_x, max_x. It is clear that the points residing inside this triangle can never be the part of convex hull.
- The above step divides the problem into two sub-problems (solved recursively). Now the line joining the points P and min_x and the line joining the points P and max_x are new lines and the points residing outside the triangle is the set of points. Repeat point no. 3 till there no point left with the line. Add the end points of this point to the convex hull.
Convex Hull AlgorithmConvex Hull using Divide and Conquer Algorithm:Convex Hull using Jarvis’ Algorithm or Wrapping:Convex Hull using Graham Scan:
The Convex Hull Algorithm is used to find the convex hull of a set of points in computational geometry. The convex hull is the smallest convex set that encloses all the points, forming a convex polygon. This algorithm is important in various applications such as image processing, route planning, and object modeling.
Contact Us