## Wednesday, 1 June 2016

### Quick Hull in Python

So my assignment for Algorithms was on creating an implementation for  convex hulls using the Giftwrap Algorithm, the Graham-Scan Algorithm, and also another of our choosing.

Many chose to monotone hull as their third, i thought i would give another a go, searched around a bit and came up with an implementation called Quick hull which is based around the Quicksort algorithm for those who have come across it, where a part point is formed and sorted items go on one side and the part point is incremented as it continues through the items.

I found a few posts on the Internet about how it sort of works, but thought i would post my own commentary about it and hopefully provide some help to some poor person that comes across this.

So first up Quick hull uses recursion... if you aren't a fan of recursion, or don't enjoy it... you should go here

The algorithm needs a part line to split the points in your point cloud. So we choose the minimum x value and then the maximum x value. This essentially gives us a line through which to split the points left and right on.

Once we have found that line, we now need all the points on the left hand side of the line. At this point in time we don't care about the right hand side points. So we check each point min, max, pt to see if it does a counter clockwise turn (CCW), if it does then it's on the left side of the line, so we include it in our points list.

When that is finished, we now find in that points list, the point that has the furthest distance from the line, lets call that point ptC. Every point that is now in the  triangle formed by the points min,max,ptC can be ignored since they will never be part of the convex hull.

Call our quick hull function again with the new points list and change our line end points to that of min, ptc. This will then again find the points on the left and furthest point etc, eventually leaving us with just 2 sets of points, the minimum and the maximum, of which we want the maximum because that was the last furthest point from the line. Return the max and append to the convex hull points.

Now - that does the left hand side, all we have to do is to call the quick hull function again, passing in our points list and reverse the max, min points, and append that to the previous hull list.

And we're done.

Time for some Pseudocode i think, should see what i described a bit clearer:

`````` Def Get Hull Points (point list):
Find the min x, max in list of points
Hull pts = Quick Hull (point list, min, max)
Hull pts = Hull pts + Quick Hull (point list, max, min)
Return Hull pts

Def Quick Hull (point list, min, max)
New pt list = Find all the points left of the line (min, max)
ptC = A point on the left side with the greatest distance from the line
then return the max point
Hull points = Quick Hull (New pt list, min, ptC)
Hull points = Hull points + Quick Hull (New pt list, max, ptC)
Return Hull points  ``````

Ok - now we have the Psuedocode, we need some real code.

The language i implemented this in is python (version 3), but with the Psuedoocode above you should be able to translate it into which ever code you wish.
```'''
Quick Hull in Python

Date: 01/06/2016
Written by: Grant McEwan

This program produces a set of hull points using a similar method to the quick
Sort Algorithm, so runs in O(n log n) time
'''
```
```
```
```
```
```'''
When called returns a list of points that forms a convex hull around ```
```    the listPts Given
'''```
```def get_hull_points(listPts):

# get the min, and max from the list of points
min, max = get_min_max_x(listPts)

hullpts = quickhull(listPts, min, max)

hullpts = hullpts + quickhull(listPts, max, min)

return hullpts

'''
Does the sorting for the quick hull sorting algorithm
'''
def quickhull(listPts, min, max):
left_of_line_pts = get_points_left_of_line(min, max, listPts)

ptC = point_max_from_line(min, max, left_of_line_pts)

if len(ptC) < 1:
return [max]

hullPts = quickhull(left_of_line_pts, min, ptC)

hullPts = hullPts + quickhull(left_of_line_pts, ptC, max)

return hullPts

'''
Reterns all points that a LEFT of a line start->end
'''
def get_points_left_of_line(start, end, listPts):
pts = []

for pt in listPts:
if isCCW(start, end, pt):
pts.append(pt)

return pts

'''
Returns the maximum point from a line start->end
'''
def point_max_from_line(start, end, points):
max_dist = 0

max_point = []

for point in points:
if point != start and point != end:
dist = distance(start, end, point)
if dist > max_dist:
max_dist = dist
max_point = point

return max_point

def get_min_max_x(list_pts):
min_x = float('inf')
max_x = 0
min_y = 0
max_y = 0

for x,y in list_pts:
if x < min_x:
min_x = x
min_y = y
if x > max_x:
max_x = x
max_y = y

return [min_x,min_y], [max_x,max_y]

'''
Given a line of start->end, will return the distance that
point, pt, is from the line.
'''
def distance(start, end, pt): # pt is the point
x1, y1 = start
x2, y2 = end
x0, y0 = pt
nom = abs((y2 - y1) * x0 - (x2 - x1) * y0 + x2 * y1 - y2 * x1)
denom = ((y2 - y1)**2 + (x2 - x1) ** 2) ** 0.5
result = nom / denom
return result

```

1. What is isCCW()?

1. is counter clock wise, determines if our next point is inside or outside of the hull.

2. Where is isCCW()?

It's nowhere to be found.

1. Hi there, That's a purposely left out. Is counter clock wise (isCCW) returns the answer to the question - If we travel from start->end and then to next, do we take left turns? do a quick google for the line function and you'll have your answer :)

3. where is the defination of isCCW()?