What is Quickhull Algorithm for Convex Hull? Explain using program in Python

By Karan Mittal

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:

1. First, we find out the leftmost and the rightmost element on the coordinate system.
2. 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.
3. Then we join these 4 points.
4. 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.
5. 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