import turtle, random,math
from Sklad import *

def jeLevi(tocka1, tocka2, tocka3):
    '''Preveri, če je obrat, ki ga naredijo točke tocka1, tocka2 in tocka3 levi
       obrat (torej obrat, v obratni smeri od urinega kazalca)'''
    (x1,y1) = tocka1
    (x2,y2) = tocka2
    (x3,y3) = tocka3
    izracun = (x2-x1)*(y3-y1)-(y2-y1)*(x3-x1)
    return izracun >= 0
##delamo s sorted!

def urediSeznam(sezTock, pivotna):
    (x1,y1) = pivotna
    nov = []
    koti = []
    for (x2,y2) in sezTock:
        kot = math.atan((y2-y1)/(x2-x1))
        if kot < 0:
            kot += math.pi
        nov.append([kot,x2,y2])
        
    nov = sorted(nov)
    sez = []
    for kot,x,y in nov:
        sez.append((x,y))
    return sez

def grahamovPregled(sezTock):
    pivot = min(sezTock,key = lambda tocka: tocka[1])
    sezTock.remove(pivot) #odstranimo pivot
    sez = urediSeznam(sezTock,pivot)
    sklad = Sklad()
    sklad.vstavi(pivot)
    sklad.vstavi(sez[0])
    sklad.vstavi(sez[1])
    for tocka in sez[2::]:
        if not jeLevi(sklad.predzadnji(),sklad.vrh(),tocka):
            sklad.odstrani()            
        sklad.vstavi(tocka)
            
    return sklad,pivot
            


#screen = turtle.Screen()
sezTock = []
turtle.setup(width=.999999999999, height =.999999999999 , startx = None, starty=None)
z = turtle.Turtle()
turtle.tracer(20,25)
z.speed("fastest")
i = 0
while i < 20:
    z.pu()
    x = random.randint(-500,500)
    y = random.randint(-500,500)
    sezTock.append( ( x,y) )
    z.goto(x,y)
    z.pd()
    z.dot(10)
    i += 1
    turtle.update()

print(sezTock)
(sklad,pivot) = grahamovPregled(sezTock)
z.pu()
z.goto(pivot[0],pivot[1])
z.pd()
while not sklad.prazen():
    (a,b) = sklad.vrh()
    z.goto(a,b)
    sklad.odstrani()
turtle.update()
print(sklad)
input("Press ANY key to exit")