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.
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.
This is a(n):
Details:
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.
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.