### The Problem

Consider a flat board with pegs sticking out of one side. If you stretched a rubber band across the outermost pegs what is the set of pegs such that all other pegs are contained within the shape formed by the rubber band?

![alt text](https://upload.wikimedia.org/wikipedia/commons/b/bc/ConvexHull.png)

More specifically, for this kata you will be given a list of points represented as ```[x,y]``` co-ordinates. Your aim will be to return a sublist containing points that form the perimeter of a polygon that encloses all other points contained within the original list.

### Notes:

The tests may include duplicate and/or co-linear points. Co-linear points are a set of points which fall on the same straight line. Neither should be included in your returned sublist

For simplicity, there will always be at least 3 points

### Help:

Check out wikipedia's page on [convex hulls](https://en.wikipedia.org/wiki/Convex_hull)

```if:python
Note for python users: `scipy` module has been disabled.
```

Difficulty: interview

Starter code:

def hull_method(pointlist):
	

Solutions:
def hull_method(points):
    sorted_points = sorted(points)
    return half_hull(sorted_points) + half_hull(reversed(sorted_points))

def half_hull(sorted_points):
    hull = []
    for p in sorted_points:
        while len(hull) > 1 and not is_ccw_turn(hull[-2], hull[-1], p):
            hull.pop()
        hull.append(p)
    hull.pop()
    return hull

def is_ccw_turn(p0, p1, p2):
    return (p1[0] - p0[0]) * (p2[1] - p0[1]) - (p2[0] - p0[0]) * (p1[1] - p0[1]) > 0


def get_direction(a, b, c, d, e, f):
    x1, y1 = c - a, d - b
    x2, y2 = e - a, f - b
    return x1 * y2 - x2 * y1
    
def get_distance(a, b, c, d):
    return (abs(c - a) ** 2 + abs(d - b) ** 2) ** .5
        
def hull_method(points):
    index = points.index( min(points))
    length, border, track = len(points), [], index

    while True:
        nxt = (track + 1) % length
    
        for i in range(length):
            if i != track:
                d = get_direction(*points[track], *points[i], *points[nxt])
                if d > 0 or (d == 0 and get_distance(*points[track], *points[i]) > get_distance(*points[track], *points[nxt])) : nxt = i
        track = nxt
        border.append(points[track])
        if track == index : break
    
    return sorted(border)

import math


# Check for left turns in constant time
def is_ccw_turn(p0, p1, p2):
    return (p1[0] - p0[0]) * (p2[1] - p0[1]) - (p2[0] - p0[0]) * (p1[1] - p0[1]) > 0


"""
Iteratively generate a hull by finding items with the maximum distance from the current hull, adding them, and repeating.
Currently very inefficient.
"""
def quickhull(points):
    
    def dist(a, b, c):
        A = b[1]-a[1]
        B = a[0]-b[0]
        C = a[1]*b[0]-a[0]*b[1]
        return abs(A*c[0]+B*c[1]+C)
    
    def triangle_area(a, b, c):
        return a[0] * (b[1] - c[1]) + b[0] * (c[1] - a[1]) + c[0] * (a[1] - b[1])
    
    def quickhull_recurse(a, b, targets, indent=1):
        # Remove colinear points
        targets = [p for p in targets if dist(a, b, p) != 0]
        # If no targets exist, be done
        if len(targets) == 0:
            return []
        max_dist = max([dist(a, b, p) for p in targets])
        m = min([p for p in targets if dist(a, b, p) == max_dist])
        l_targets = quickhull_recurse(a, m, [p for p in targets if not is_ccw_turn(m, a, p)], indent+1)
        r_targets = quickhull_recurse(m, b, [p for p in targets if not is_ccw_turn(b, m, p)], indent+1)
        return l_targets + [m] + r_targets
    
    # Grab two extreme points
    least, most = min(points), max(points)
    # Split into those points above and below
    points = [p for p in points if p != most and p != least]
    top = quickhull_recurse(least, most, [p for p in points if is_ccw_turn(least, most, p)])
    bot = quickhull_recurse(most, least, [p for p in points if not is_ccw_turn(least, most, p)])
    # Generate the final result
    return [least] + top + [most] + bot


"""
Generate a merged hull by splitting the hull arbitrarily, generating two parting hulls, and reconciling.
First, remove all points in hull 2's inner edge, if the centroid of hull 1 is outside hull 2.
Then, reconcile all points into a single queue, ordered by angle, then distance.
Finally, run a graham scan on this new monotone ring.
DOESN'T CURRENTLY RUN TOO WELL.
"""
def unsorted_merge_hull(points):
    # If the number of points is small enough, crank out a solution.
    if len(points) <= 5:
        return double_half_hull(points)
    # If the number of points is high, divide and conquer.
    else:
        # Generate partial hulls
        a, b = unsorted_merge_hull(points[:len(points)//2]), unsorted_merge_hull(points[len(points)//2:])
        # Find a point inside the first partial hull
        c = (sum([x for x, y in a[:3]]) / 3, sum([y for x, y in a[:3]]) / 3)
        # Determine the targent line points of the second partial hull to the centroid, if applicable
        i = 0
        while i < len(b) or is_ccw_turn(c, b[i], b[(i + 1) % len(b)]) or is_ccw_turn(c, b[i], b[(i - 1) % len(b)]):
            i += 1
        # If one tangent is found, find the other
        if i < len(b):
            j = 0
            while j < len(b) or is_ccw_turn(c, b[j], b[(j + 1) % len(b)]) or is_ccw_turn(c, b[j], b[(j - 1) % len(b)]):
                j += 1
            # Kill the points between the tangents
            if i < j:
                b = b[i:j]
            else:
                b = b[j:] + b[:i]
        # Merge to partial hulls into a single queue
        q = []
        i_a, i_b = 0, 0
        while i_a < len(a) or i_b < len(b):
            pass
        if i_a < len(a): q.extend(a[i_a:])
        if i_b < len(b): q.extend(b[i_b:])
        # Run a graham scan on the queue
        # Return a valid hull


"""
Generate a merged hull by splitting the hull along a single axis, generating a series of partial hulls, and merging.
Has issues with colinear points, but that's fine. 
The main benefit of this is the ability to parallel process. 
So long as the final set of points is re-checked, you can still get great gains from this.
Sift 90%, then run a better algo on the final result.
"""
def x_laced_merge_hull(points):
    sorted_points = sorted(points)
    # Remove doubles along the x axis
    x_laced_points = []
    for p in sorted_points:
        x_laced_points.append(p)
        if len(x_laced_points) >= 3 and x_laced_points[-1][0] == x_laced_points[-2][0] == x_laced_points[-3][0]:
            x_laced_points.pop(-2)

    def sew(l_h, r_h, l_o, r_o, direction):
        # Start sewing at the extreme middle of the partial hulls.
        l_i, r_i = l_o, r_o
        found_both = False
        while not found_both:
            # If either the left or right is moved, re-loop.
            found_both = True
            # Shift the right pointer as much as possible toward the extreme
            moving_right = True
            while moving_right:
                if direction == "top":
                    m_res = is_ccw_turn(r_h[(r_i + 1) % len(r_h)], r_h[r_i], l_h[l_i])
                    p_res = is_ccw_turn(r_h[(r_i - 1) % len(r_h)], r_h[r_i], l_h[l_i])
                elif direction == "bot":
                    m_res = is_ccw_turn(l_h[l_i], r_h[r_i], r_h[(r_i + 1) % len(r_h)])
                    p_res = is_ccw_turn(l_h[l_i], r_h[r_i], r_h[(r_i - 1) % len(r_h)])
                if m_res == p_res == False:
                    moving_right = False
                else:
                    r_i = (r_i + (1 if direction == "top" else -1)) % len(r_h)
                    found_both = False
            # Shift the left pointer as much as possible towards the extreme
            moving_left = True
            while moving_left:
                if direction == "top":
                    m_res = is_ccw_turn(r_h[r_i], l_h[l_i], l_h[(l_i + 1) % len(l_h)])
                    p_res = is_ccw_turn(r_h[r_i], l_h[l_i], l_h[(l_i - 1) % len(l_h)])
                elif direction == "bot":
                    m_res = is_ccw_turn(l_h[(l_i + 1) % len(l_h)], l_h[l_i], r_h[r_i])
                    p_res = is_ccw_turn(l_h[(l_i - 1) % len(l_h)], l_h[l_i], r_h[r_i])
                if m_res == p_res == False:
                    moving_left = False
                else:
                    l_i = (l_i + (-1 if direction == "top" else 1)) % len(l_h)
                    found_both = False
        # Return indexes for the left and right nodes that will be bridged to merge the hulls.
        return l_i, r_i

    def x_laced_recurse(l_i=0, r_i=len(x_laced_points)):
        # If there are under 5 points, use an inefficient algo.
        if r_i - l_i <= 5:
            sub_points = x_laced_points[l_i:r_i]
            hull = double_half_hull(sub_points)
            return hull.index(min(hull)), hull.index(max(hull)), hull
        # If there are over 5 points, recurse.
        else:
            # Recurse until there are two half-hulls of equal heft
            l_min_i, l_max_i, l_h = x_laced_recurse(l_i, (l_i+r_i) // 2)
            r_min_i, r_max_i, r_h = x_laced_recurse((l_i+r_i) // 2, r_i)
            # Start with a line from the rightmost left point to the leftmost right point, move until can no longer
            # Move the two lines, one up, one down until they can no longer be rotated to increase their encompassings
            bot_i_l, bot_i_r = sew(l_h, r_h, l_max_i, r_min_i, 'bot')
            top_i_l, top_i_r = sew(l_h, r_h, l_max_i, r_min_i, 'top')
            # Join along the highlighted points, so as to merge the two partial hulls into a single spanning hull
            hull = []
            l_i = bot_i_l
            while l_i != top_i_l:
                hull.append(l_h[l_i])
                l_i = (l_i + 1) % len(l_h)
            hull.append(l_h[l_i])
            r_i = top_i_r
            while r_i != bot_i_r:
                hull.append(r_h[r_i])
                r_i = (r_i + 1) % len(r_h)
            hull.append(r_h[r_i])
            # Return the result
            return hull.index(min(hull)), hull.index(max(hull)), hull

    return double_half_hull(x_laced_recurse()[2])


def graham_scan_hull(points):
    # Get LTL
    m = max([n[1] for n in points])
    o = min(points, key=lambda p:(p[0]*m+p[1]))
    # Sort according to angle from origin
    points = sorted(points, key=lambda p:(p[0]*m+p[1]))
    points = sorted(points[1:], key=lambda p:math.atan2(p[0]-o[0],p[1]-o[1]))
    # Initialize the hull with origin and item with lowest or highest angle
    h, points = [points[-1], o, points[0]], points[1:]
    # Iterate over the points
    for p in points:
        # Append the next point
        h.append(p)
        # Kill 2nd-to-last until reaching a state of convexity
        done = False
        # Pop until not at a ccw turn
        while len(h) > 3 and not is_ccw_turn(h[-1], h[-2], h[-3]):
            h.pop(-2)
    h = [[p[0], p[1]] for p in h[:-1]]
    return (h[2:] + h[:2])[::-1]


# Generate a merged hull by generating two max-size, half-hulls with CW and CCW cardinality, then joining them.
def double_half_hull(points):
    # Sort the points along an axis to make them monotone.
    sorted_points = sorted(points)
    
    # Define a function to get half-hulls in a single direction.
    def half_hull(sorted_points):
        hull = []
        for p in sorted_points:
            # It's okay to only check CCW, as this function will be run on both an initial and a reversed list.
            while len(hull) > 1 and not is_ccw_turn(hull[-2], hull[-1], p):
                hull.pop()
            hull.append(p)
        hull.pop()
        return hull
        
    # Call the half-hull function twice - once to get the right side, once the left.
    return half_hull(sorted_points) + half_hull(reversed(sorted_points))


def hull_method(points):
    # Remove point doubles
    points = [list(p) for p in set([tuple(p) for p in points])]
    # Print the points
    print(points if len(points) < 80 else "{}...".format(points[:80]), '\n')
    # print("unsorted_merge_hull:")
    # res_unsorted_merge_hull = unsorted_merge_hull(points)
    # print(res_unsorted_merge_hull, '\n')
    print("quickhull:")
    res_quickhull = quickhull(points)
    print(res_quickhull, '\n')
    print("x_laced_merge hull:")
    res_x_laced_merge_hull = x_laced_merge_hull(points)
    print(res_x_laced_merge_hull, '\n')
    print("graham_scan_hull:")
    res_graham_scan_hull = graham_scan_hull(points)
    print(res_graham_scan_hull, '\n')
    print("double_half_hull:")
    res_double_half_hull = double_half_hull(points)
    print(res_double_half_hull, '\n')
    hash_checkers = []
    for hull in [res_quickhull, res_x_laced_merge_hull, res_graham_scan_hull, res_double_half_hull]:
        hash_checkers.append({tuple(p) for p in hull})
    fail_to_matches = sum(hash_checkers[i] != hash_checkers[i+1] for i in range(len(hash_checkers)-1))
    return [] if fail_to_matches > 0 else res_double_half_hull

import math

def hull_method(pointlist):
    workset = set(map(tuple, pointlist))
    basepoint = edge = max(workset)
    hull, ray = [], 0
    
    def seeker(p):
        dx, dy = p[0] - edge[0], p[1] - edge[1]
        turn = (math.atan2(dy, dx) - ray) % (2 * math.pi)
        sqdistance = dx * dx + dy * dy
        return turn, -sqdistance, p

    while not hull or basepoint != edge:
        turn, _, edge = min(list(map(seeker, workset - {edge})))
        ray  +=  turn
        hull += [edge]
    return list(map(list, hull))


def hull_method(points):
    """Computes the convex hull of a set of 2D points.

    Input: an iterable sequence of (x, y) pairs representing the points.
    Output: a list of vertices of the convex hull in counter-clockwise order,
      starting from the vertex with the lexicographically smallest coordinates.
    Implements Andrew's monotone chain algorithm. O(n log n) complexity.
    """

    # Sort the points lexicographically (tuples are compared lexicographically).
    # Remove duplicates to detect the case we have just one unique point.
    points =  sorted(points)
#     points = sorted(set(points))
    

    # Boring case: no points or a single point, possibly repeated multiple times.
    if len(points) <= 1:
        return points

    # 2D cross product of OA and OB vectors, i.e. z-component of their 3D cross product.
    # Returns a positive value, if OAB makes a counter-clockwise turn,
    # negative for clockwise turn, and zero if the points are collinear.
    def cross(o, a, b):
        return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

    # Build lower hull 
    lower = []
    for p in points:
        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)

    # Build upper hull
    upper = []
    for p in reversed(points):
        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)

    # Concatenation of the lower and upper hulls gives the convex hull.
    # Last point of each list is omitted because it is repeated at the beginning of the other list. 
    return lower[:-1] + upper[:-1]

# def hull_method(pointlist):

#     pass


import numpy as np

def slope(p1, p2):
    dx, dy = vectorize(p1, p2)
    return dy/dx if dx else float("inf")

def vectorize(p1, p2):         return [b-a for a,b in zip(p1, p2)]
def getArea  (p1, p2, p3):     return np.cross(vectorize(p1, p2), vectorize(p1, p3)) / 2
def isConcave(p1, pivot, p2):  return getArea(pivot, p1, p2) >= 0

def hull_method(points):
    if len(points) < 3: return 0
    
    Z = min(points)                                                         # Leftmost point in the graph (lowest if several ones at the same x)
    q = sorted( (pt for pt in points if pt != Z),
                key = lambda pt: (-slope(pt, Z), -np.linalg.norm(vectorize(Z,pt))))                             # sorted points accordingly to the slope of the line formed by "pt" and "Z" (in reversed order)
    
    hull = [Z, q.pop()]                                                     # Construct the convex hull (Graham Scan)
    while q:
        pt = q.pop()
        while len(hull) > 1 and isConcave(hull[-2], hull[-1], pt):
            hull.pop()
        hull.append(pt)
    return hull

from math import atan2, pi
tau=2*pi

def hull_method(pointlist):
    pointlist = sorted(set((x,y) for [x,y] in pointlist))
    s=min(pointlist, key=lambda p:p[1]); p=s; d=0; l=[]
    while (p!=s or len(l)<1):
        tp = min([(x-p[0],y-p[1]) for x,y in pointlist if x!=p[0] or y!=p[1]], key=lambda p:((atan2(p[1],p[0])-d+tau)%tau,-p[0]**2-p[1]**2))
        p = (tp[0]+p[0],tp[1]+p[1]); l.append(p); d=(atan2(tp[1],tp[0])+tau)%tau;
    return [[x,y] for x,y in l]

from functools import cmp_to_key
def hull_method(pointlist):
    # handles the duplicate inputs
    pointlist = list(set(map(tuple,pointlist)))
    # find the bottom most and left most point
    first_idx = min(range(len(pointlist)), key = lambda x: (pointlist[x][1], pointlist[x][0]))
    pointlist[first_idx], pointlist[0] = pointlist[0], pointlist[first_idx]
    # sort from the first
    p = pointlist[0]
    def custom_compare(q, r):
        px, py = p
        qx, qy = q
        rx, ry = r
        compare = (qy - py)*(rx - qx) - (qx - px)*(ry - qy)
        if compare < 0:
            return -1
        elif compare > 0:
            return 1
        else:
            return -1 if (rx-px)**2 + (ry-py)**2 >= (qx-px)**2 + (qy-py)**2 else 1
    def get_angle(p, q, r):
        px, py = p
        qx, qy = q
        rx, ry = r
        return (qy - py)*(rx - qx) - (qx - px)*(ry - qy)
        
    pointlist[1:] = sorted(pointlist[1:], key = cmp_to_key(custom_compare))
#     print("pointlist = ", pointlist)
    lst, i = [pointlist[0]], 2
    while i < len(pointlist):
        while i < len(pointlist) and get_angle(p, pointlist[i-1], pointlist[i]) == 0:
            i += 1
        if i < len(pointlist):
            lst.append(pointlist[i-1])
            i += 1
    lst.append(pointlist[i-1])
#     print("sorted list = ", lst)
    if len(lst) < 3:
        return []
    stck = [lst[0], lst[1], lst[2]]
    for i in range(3, len(lst)):
        while get_angle(stck[-2], stck[-1], lst[i]) >= 0:
            stck.pop()
        stck.append(lst[i])
    return list(map(list, stck))

import numpy as np
import itertools as it

def convertToPolar(points, refpoint):
    """Converts a list-like of 2D points to polar coordinates, first column containing the radii, second column containing the angles from [2, 2*pi]"""
    points = np.asarray(points)
    refpoint = np.asarray(refpoint)
    points_c = points - refpoint
    
    rads = np.linalg.norm(points_c, axis = 1)
    angles = np.angle(np.apply_along_axis(lambda args: [complex(*args)], 1, points_c))%(2*np.pi)
    return np.column_stack((rads, angles))


def getSorted(points):
    """Converts a list of 2D points to polar coordinates and then lexsorts the result list first by angle, then by radius."""
    points = np.asarray(points)
    midpoint = sum(points)/len(points)
    points_polar = convertToPolar(points, midpoint)
    lexsortindices = np.lexsort((points_polar[:,0], points_polar[:,1]))
    points_polar_sorted = points_polar[lexsortindices]
    points_sorted = points[lexsortindices]
    
    _, idx_start, count = np.unique(points_polar_sorted[:,1], return_counts=True, return_index=True)
    points_polar_sorted_oneperangle = points_polar_sorted[idx_start + count - 1]
    points_sorted_oneperangle = points_sorted[idx_start + count - 1]
    outmostidx = np.argmax(points_polar_sorted_oneperangle[:,0])
    
    return np.roll(points_sorted_oneperangle, -outmostidx, axis = 0)

def areCollinear(point1, point2, point3):
    point1, point2, point3 = np.asarray(point1), np.asarray(point2), np.asarray(point3)
    return np.linalg.det(np.column_stack((point1 - point2, point2 - point3))) == 0

def hull_method(pointlist):
    points = getSorted(pointlist)
    outlist = [points[0].tolist()]
    previous_idx, previous = 0, points[0]
    
    for current_idx, current in enumerate(points[1:], 1):
        
        #check that all other points are in the left halfplane specified by previous_point, current_point:
        hyperplanevector = current - previous
        normalvector = np.array([-hyperplanevector[1], hyperplanevector[0]])
        
        #check whether all points are in the left halfspace of the hyperplane (= line) defined by the point "previous" and the vector "hyperplanevector"
        halfspace_check = True
        for vec in it.chain(points[current_idx+1:,:], points[:previous_idx,:], points[previous_idx + 1: current_idx,:]):
            vec_c = vec - previous
            if np.dot(vec_c, normalvector) < 0:
                halfspace_check = False
                break
        
        if halfspace_check:
            #remove previous point if collinearity or duplicate would arise
            if len(outlist) >= 2:
                if areCollinear(current, outlist[-1], outlist[-2]):
                    outlist.pop(-1)
                    
            #add current point
            outlist.append(current.tolist())
            previous_idx, previous = current_idx, current
                
    #remove collinearities from last three outlist points or from connecting outlist points to a closed curve        
    if len(outlist) >= 3:        
        for i in (-2,-1,0): 
            if areCollinear(outlist[i-1], outlist[i], outlist[i+1]):
                outlist.pop(i)
       
    return outlist

from math import acos,sqrt,pi,atan2
eucelid = lambda a,b:((a[0]-b[0])**2+(a[1]-b[1])**2)**0.5
def cpd(x,y,z):
    cpd=(y[0]-x[0])*(z[1]-x[1])-(y[1]-x[1])*(z[0]-x[0])
    if cpd < 0 : return -1
    if cpd > 0 : return 1
    return 0
def cc(s,z):
    x_s,y_s=s[0]-z[0],s[1]-z[1]
    return atan2(y_s,x_s)

def hull_method(pointlist):
    d, stack = min(pointlist, key=lambda x: (x[1],x[0])), []
    pointlist.sort(key=lambda x: (cc(x,d),eucelid(x,d)))
    stack+=pointlist[:2]
    for i in range(2, len(pointlist)):
        nx, pp = pointlist[i], stack.pop()
        while len(stack) and stack[-1] and cpd(stack[-1], pp, nx) <= 0:
                pp = stack.pop()
        stack += [pp, nx]
    return stack