from matplotlib.pyplot import *
import random
            

points = []
N = 10
for i in range(N):
    points.append([random.random(),random.random()])
            

def point_segment(P1,P2,P):
    return (P2[0]-P1[0])*(P[1]-P1[1])-(P2[1]-P1[1])*(P[0]-P1[0])>0
            

def enveloppe_direct(points):
    enveloppe = []
    N = len(points)
    for i in range(N):
        for j in range(N):
            if i!=j:
                bord = True
                for k in range(N):
                    if k!=i and k!=j:
                        if point_segment(points[i],points[j],points[k]):
                            bord = False
                            break
                if bord:
                    enveloppe.append([points[i],points[j]])
    return enveloppe            
            

figure()
axis([0,1,0,1])
axes().set_aspect('equal')
for i in range(len(points)):
    P = points[i]
    plot([P[0]],[P[1]],"ko")
env = enveloppe_direct(points)
for i in range(len(env)):
    segment = env[i]
    P1 = segment[0]
    P2 = segment[1]
    plot([P1[0],P2[0]],[P1[1],P2[1]],"k-")
            

def enveloppe_inc(points):
    def cle(P):
        return P[1]
    points.sort(key=cle)
    def cle(P):
        return P[0]
    points.sort(key=cle)
    N=len(points)
    enveloppe = [points[0],points[1]]
    for i in range(2,N):
        enveloppe.append(points[i])
        valide = False
        while not(valide) and len(enveloppe)>2:
            P3 = enveloppe.pop()
            P2 = enveloppe.pop()
            P1 = enveloppe.pop()
            if point_segment(P1,P2,P3):
                enveloppe.append(P1)
                enveloppe.append(P3)
            else:
                enveloppe.append(P1)
                enveloppe.append(P2)
                enveloppe.append(P3)
                valide = True
    enveloppe.append(points[N-2])
    for i in range(N-3,-1,-1):
        enveloppe.append(points[i])
        valide = False
        while not(valide) and len(enveloppe)>2:
            P3 = enveloppe.pop()
            P2 = enveloppe.pop()
            P1 = enveloppe.pop()
            if point_segment(P1,P2,P3):
                enveloppe.append(P1)
                enveloppe.append(P3)
            else:
                enveloppe.append(P1)
                enveloppe.append(P2)
                enveloppe.append(P3)
                valide = True
    return enveloppe
            

env=enveloppe_inc(points)
figure()
axis([0,1,0,1])
axes().set_aspect('equal')
for i in range(len(points)):
    P = points[i]
    plot([P[0]],[P[1]],"ko")
env = enveloppe_inc(points)
for i in range(1,len(env)):
    P2 = env[i]
    P1 = env[i-1]
    plot([P1[0],P2[0]],[P1[1],P2[1]],"k-")