Notes

import math
from collections import namedtuple
import matplotlib.pyplot as plt
import random

Point = namedtuple('Point', 'x y')


def getDist(a, b):
return math.sqrt(abs(a.x - b.x) ** 2 + abs(a.y - b.y) ** 2)


class ConvexHull(object):
pts = []
hullpts = []

def __init__(self):
pass

def add(self, point):
self.pts.append(point)

def _get_orientation(self, origin, p1, p2):
'''
Returns the orientation of the Point p1 with regards to Point p2 using origin.
Negative if p1 is clockwise of p2.
'''
difference = (
((p2.x - origin.x) * (p1.y - origin.y))
- ((p1.x - origin.x) * (p2.y - origin.y))
)

return difference

def compute_hull(self):
'''
Computes the points that make up the convex hull.
:return:
'''
points = self.pts

start = points[0]
min_x = start.x
for p in points[1:]:
if p.x < min_x:
min_x = p.x
start = p

point = start
self.hullpts.append(start)

far_point = None
while far_point is not start:

# get the first point (initial max) to use to compare with others
p1 = None
for p in points:
if p is point:
continue
else:
p1 = p
break

far_point = p1

for p2 in points:
# ensure we aren't comparing to self or pivot point
if p2 is point or p2 is p1:
continue
else:
direction = self._get_orientation(point, far_point, p2)
if direction > 0:
far_point = p2

self.hullpts.append(far_point)
point = far_point

def get_hull_points(self):
if self.pts and not self.hullpts:
self.compute_hull()

return self.hullpts

def display(self):
# all points
x = [p.x for p in self.pts]
y = [p.y for p in self.pts]
plt.plot(x, y, marker='D', linestyle='None')

# hull points
hx = [p.x for p in self.hullpts]
hy = [p.y for p in self.hullpts]
plt.plot(hx, hy)

plt.title('Convex Hull')
plt.show()

def cost_to_add(self, node):
min_so_far = float("inf")
closest_hull_points = None
costs = []
for c, p1 in enumerate(self.hullpts):

if c == len(self.hullpts) - 1:
continue

p2 = self.hullpts[c + 1]

if p1 == p2:
continue

cost = (getDist(node, p1) + getDist(node, p2))/getDist(p1, p2)
# cost = (getDist(node, p1) + getDist(node, p2))-getDist(p1,p2)

costs += (cost, getDist(node, p1) + getDist(node, p2), p1, node, p2)
# print(cost, p1, p2)

if cost < min_so_far:
min_so_far = cost
closest_hull_points = (p1, p2)

return min_so_far, closest_hull_points

def test_cost_to_add(self, node):
min_so_far = float("inf")
closest_hull_points = None

for c, p1 in enumerate(self.hullpts):

p2 = None

if c != len(self.hullpts) - 1:
p2 = self.hullpts[c + 1]
else:
p2 = self.hullpts[0]

cost = getDist(node, p1)

if cost < min_so_far:
min_so_far = cost
closest_hull_points = (p1, p2)

print("a", p1)
return min_so_far, closest_hull_points

def get_circumference(self):
total = 0

for c, p1 in enumerate(self.hullpts):

p2 = None

if c != len(self.hullpts) - 1:
p2 = self.hullpts[c + 1]
else:
p2 = self.hullpts[0]

total += getDist(p1, p2)
return total

def points(self):
return self.pts

def convex_hull(tuples):
ch = ConvexHull()
# print([(random.randint(-100, 100), random.randint(-100, 100)) for _ in range(12)])

# for _ in range(n):
# ch.add(Point(random.randint(-100, 100), random.randint(-100, 100)))

# tuples = [(-44, -36), (-51, 97), (55, 62), (40, -99), (16, -67), (-24, 48), (-67, -38), (38, -74), (49, 96), (-85, -63), (76, 96), (-94, 15)]
for (x, y) in tuples:
ch.add(Point(x, y))

points = ch.pts.copy()

print(ch.get_hull_points())

for c, p1 in enumerate(ch.hullpts):

if c == len(ch.hullpts) - 1:
continue

p2 = ch.hullpts[c + 1]

print(getDist(p1,p2))

while points:
min_val = float("inf")
min_node, closest_hull_points = None, None

for node in points:
if node in ch.hullpts:
points.remove(node)
continue

cost_to_add, this_closest_hull_points = ch.cost_to_add(node)

if cost_to_add < min_val:
min_node, closest_hull_points = node, this_closest_hull_points
min_val = cost_to_add

where_to_add = ch.hullpts.index(this_closest_hull_points[1])

where_to_add = -1 if where_to_add == 0 else where_to_add

ch.hullpts.insert(where_to_add, min_node)

if min_node in points:
points.remove(min_node)

print(min_node, this_closest_hull_points)
print(ch.hullpts)
ch.display()

print("Points on hull:", ch.hullpts, ch.get_circumference())
# print(ch.getDist(ch.get_hull_points()[1],ch.get_hull_points()[2]))

ch.display()

def main():
convex_hull([(-44, -36), (-51, 97), (55, 62), (40, -99), (16, -67), (-24, 48), (-67, -38), (38, -74), (49, 96), (-85, -63), (76, 96), (-94, 15)])


if __name__ == '__main__':
main()