import random
import sys
import matplotlib.pyplot as plt
from matplotlib.image import BboxImage
from matplotlib.transforms import Bbox, TransformedBbox
import numpy as np
import time

CLOCKWISE = -1
COLLINEAR = 0
COUNTERCLOCKWISE = +1
eps = sys.float_info.epsilon


def orientation(a, b):
    x0, y0 = a
    x1, y1 = b
    cross = x0 * y1 - x1 * y0
    if cross > eps:
        return COUNTERCLOCKWISE
    elif cross < -eps:
        return CLOCKWISE
    else:
        return COLLINEAR


def same_halfplane(a, b):
    x0, y0 = a
    x1, y1 = b
    dot = x0 * x1 + y0 * y1
    if dot >= eps:
        return True
    elif dot < eps:
        return False


def jarvis(points):
    points = points[:]
    r0 = min(points)
    hull = [r0]
    r, u = r0, None
    remainingPoints = [x for x in points if x not in hull]
    while u != r0 and remainingPoints:
        u = random.choice(remainingPoints)
        for t in points:
            a = (u[0] - r[0], u[1] - r[1])
            b = (t[0] - u[0], t[1] - u[1])
            if (t != u and
                (orientation(a, b) == CLOCKWISE or
                 (orientation(a, b) == COLLINEAR and
                  same_halfplane(a, b)))):
                u = t
        r = u
        points.remove(r)
        hull.append(r)
        try:
            remainingPoints.remove(r)
        except ValueError:
            # ValueError: list.remove(x): x not in list
            pass
    return hull

#if __name__ == '__main__':

X = random.sample(range(100), 30)
Y = random.sample(range(100), 30)

points = list(zip(X, Y))
print(points)
hull = jarvis(points)
px, py = zip(*points)
hx, hy = zip(*hull)

plt.plot(hx, hy, 'g-', markersize=10)
plt.plot(px,py, 'p')


plt.show()