### 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: MEDIUM
Tags: Geometry

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) ** 0.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

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 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):
		targets = [p for p in targets if dist(a, b, p) != 0]
		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
	(least, most) = (min(points), max(points))
	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)])
	return [least] + top + [most] + bot

def unsorted_merge_hull(points):
	if len(points) <= 5:
		return double_half_hull(points)
	else:
		(a, b) = (unsorted_merge_hull(points[:len(points) // 2]), unsorted_merge_hull(points[len(points) // 2:]))
		c = (sum([x for (x, y) in a[:3]]) / 3, sum([y for (x, y) in a[:3]]) / 3)
		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 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
			if i < j:
				b = b[i:j]
			else:
				b = b[j:] + b[:i]
		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:])

def x_laced_merge_hull(points):
	sorted_points = sorted(points)
	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):
		(l_i, r_i) = (l_o, r_o)
		found_both = False
		while not found_both:
			found_both = True
			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
			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 (l_i, r_i)

	def x_laced_recurse(l_i=0, r_i=len(x_laced_points)):
		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)
		else:
			(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)
			(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')
			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 (hull.index(min(hull)), hull.index(max(hull)), hull)
	return double_half_hull(x_laced_recurse()[2])

def graham_scan_hull(points):
	m = max([n[1] for n in points])
	o = min(points, key=lambda p: p[0] * m + p[1])
	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]))
	(h, points) = ([points[-1], o, points[0]], points[1:])
	for p in points:
		h.append(p)
		done = False
		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]

def double_half_hull(points):
	sorted_points = 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
	return half_hull(sorted_points) + half_hull(reversed(sorted_points))

def hull_method(points):
	points = [list(p) for p in set([tuple(p) for p in points])]
	print(points if len(points) < 80 else '{}...'.format(points[:80]), '\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):
	points = sorted(points)
	if len(points) <= 1:
		return points

	def cross(o, a, b):
		return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
	lower = []
	for p in points:
		while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
			lower.pop()
		lower.append(p)
	upper = []
	for p in reversed(points):
		while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
			upper.pop()
		upper.append(p)
	return lower[:-1] + upper[:-1]


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)
	q = sorted((pt for pt in points if pt != Z), key=lambda pt: (-slope(pt, Z), -np.linalg.norm(vectorize(Z, pt))))
	hull = [Z, q.pop()]
	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):
	pointlist = list(set(map(tuple, pointlist)))
	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])
	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))
	(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])
	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):
	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):
	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):
		hyperplanevector = current - previous
		normalvector = np.array([-hyperplanevector[1], hyperplanevector[0]])
		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:
			if len(outlist) >= 2:
				if areCollinear(current, outlist[-1], outlist[-2]):
					outlist.pop(-1)
			outlist.append(current.tolist())
			(previous_idx, previous) = (current_idx, current)
	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