What is Quickhull Algorithm for Convex Hull? Explain using program in Python
In this tutorial, we’ll be discussing the Quick hull algorithm for finding a convex hull in Python.
Before starting first let’s discuss what a convex hull is:
The convex hull is a shape formed by joining the elements of the smallest convex set. The convex set is a set of points in the given set of points which when joined together forms a shape. In the shape formed if any two lines connecting two points in the shape always lie within the shape.
It is not a convex shape. As there are two points such that when connected inside the shape a line outside the shape is formed.
While this is a convex shape. As whenever we take any two points inside this shape they always lie within the shape. Hence, this is a convex shape.
Quickhull is a method of computing the convex hull of a finite set of points in the plane.
The Quickhull algorithm goes as follows:
- First, we find out the leftmost and the rightmost element on the coordinate system.
- We join these points and find a point that is perpendicularly at the highest distance from the line on both the +y axis and -y axis.
- Then we join these 4 points.
- Now from the lines formed if there is any other point at a perpendicular distance to the outside of the shape, if yes we add that point to the list.
- We do this recursively until there doesn’t lie any point outside these lines.
Its average-case complexity is considered to be Θ(n * log(n)), whereas in the worst case it takes O(n^2).
def find_distance(p1,p2,p3): a=p1-p2 b=p2-p1 c=p1*p2-p2*p1 return abs((a*p3+b*p3+c)/((a*a+b*b)**0.5)) def create_segment(p1,p2,v): above= below= if(p1==p2==0): return above,below m=(p2-p1)/(p2-p1) c=-m*p1+p1 for co in v: if(co>m*co+c): above.append(co) elif(co<m*co+c): below.append(co) return above,below def quickhull2(p1,p2,segment,flag): if(segment== or p1 is None or p2 is None): return  convex_hull= farthest_distance=-1 farthest_point=None for point in segment: distance=find_distance(p1,p2,point) if(distance>farthest_distance): farthest_distance=distance farthest_point=point convex_hull=convex_hull + [farthest_point] segment.remove(farthest_point) p1a,p1b=create_segment(p1,farthest_point,segment) p2a,p2b=create_segment(p2,farthest_point,segment) if flag=='above': convex_hull=convex_hull+quickhull2(p1,farthest_point,p1a,'above') convex_hull=convex_hull+quickhull2(farthest_point,p2,p2a,'above') else: convex_hull=convex_hull+quickhull2(p1,farthest_point,p1b,'below') convex_hull=convex_hull+quickhull2(farthest_point,p2,p2b,'below') return convex_hull def quickhull(v): if(len(v)<=2): return v convex_hull= sort=sorted(v,key=lambda x:x) p1=sort p2=sort[-1] sort.pop(0) sort.pop(-1) above,below=create_segment(p1,p2,sort) convex_hull=convex_hull+quickhull2(p1,p2,above,'above') convex_hull=convex_hull+quickhull2(p1,p2,below,'below') return convex_hull points = [ (0.0, 0.0, 0.0), (0.0, 1.0, 0.0), (0.1, 0.1, 0.1), (0.2, 0.1, 0.4), (0.1, 0.4, 0.2), (0.3, 0.1, 0.2), (0.0, 0.0, 1.0), (1.0, 0.0, 0.0), ] print(quickhull(points))
Also read: Z algorithm in Python