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.
EG:
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[1]-p2[1] b=p2[0]-p1[0] c=p1[0]*p2[1]-p2[0]*p1[1] return abs((a*p3[0]+b*p3[1]+c)/((a*a+b*b)**0.5)) def create_segment(p1,p2,v): above=[] below=[] if(p1[0]==p2[0]==0): return above,below m=(p2[1]-p1[1])/(p2[0]-p1[0]) c=-m*p1[0]+p1[1] for co in v: if(co[1]>m*co[1]+c): above.append(co) elif(co[1]<m*co[1]+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[0]) p1=sort[0] 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
It work incorrectly when run it returns [(0.0, 1.0, 0.0)]. That is not the convex hull for this shape.