#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Fri Oct 19 08:03:15 2018

@author: phjo
"""

import matplotlib.pyplot as mpl

P = [(1, 0), (0, 5), (6, 1), (8, 7), (3, 9), (7, 11), (11, 5), (13, 5), \
     (12, 1), (16, 3), (17, 6), (17, 10), (12, 10)]

def orientation(a, b, c):
    """ étant donné trois points a b et c (tuples ou listes)
    retourne >0 si (ab, ac) a une mesure dans ]0, pi[
            <0 si (ab, ac) a une mesure dans ]-pi, 0[
            et 0 si a, b et c sont alignés """
    return (b[0]-a[0])*(c[1]-a[1])-(c[0]-a[0])*(b[1]-a[1])     

def pointGauche(L):
    """ d'une liste non vide de points L, retourne l'indice de celui le plus 
    à gauche et en bas """
    imin = 0
    for i in range(1, len(L)):
        if L[i][0] < L[imin][0] or (L[i][0] == L[imin][0] and L[i][1] < L[imin][1]):
            # oui, on peut aussi écrire, tout simplement : if L[i] < L[imin] !
            imin = i
    return imin

def insertSort(L, comp):
    """ trie L dans l'ordre croissant, en supposant que la fonction comp
    fonctionne ainsi : comp(a, b) > 0 ssi a > b, comp(a,b) < 0 ssi
    a < b. La relation peut ne pas être antisymétrique cependant, comme
    c'est le cas dans l'application proposée (l'ordre obtenu pour les 
    éléments que la relation (de préordre) ne distingue pas est alors arbitraire
    a priori)"""
    n = len(L)
    for i in range(1, n):
        j = i - 1
        while j >= 0 and comp(L[j], L[j+1]) < 0:
            L[j], L[j + 1] = L[j+1], L[j]
            j -= 1
    return L

def merge(L1, L2, comp):
    L = []
    i, j = 0, 0
    n, p = len(L1), len(L2)
    while i < n and j < p:
        if comp(L1[i], L2[j]) > 0:
            L.append(L1[i])
            i += 1
        else:
            L.append(L2[j])
            j += 1
    if i < n:
        L += L1[i:]
    else:
        L += L2[j:]
    return L

def mergeSort(L, comp):
    if len(L) <= 1:
        return L
    m = len(L) // 2
    L1 = mergeSort(L[:m], comp)
    L2 = mergeSort(L[m:], comp)
    return merge(L1, L2, comp)

def prepare(L):
    """ retire le point d'indice i de L, et réordonne les points restants 
    de L par angle croissant.
    
    En cas de deux points alignés avec L[i], ne garde que le plus éloigné """
    i = pointGauche(L)
    Lcopy = L[:]
    p = Lcopy.pop(i)
    def compare(a, b):
        return orientation(p, a, b) # ou une fonction lambda directement donnée
    # en argument de la fonction qui suit
    #insertSort(Lcopy, compare)
    Lcopy = mergeSort(Lcopy, compare)
    return p, Lcopy

def menage(p, L):
    """ La liste L étant triée (en angles croissants depuis le point p), supprime
    lorsque deux points consécutifs se trouvent alignés avec p, le plus proche
    de p : on retournera une autre liste """
    L2 = []
    L2.append(L[0])
    for i in range(1, len(L)):
        if orientation(p, L[i], L2[-1]) != 0:
            L2.append(L[i])
        else:
            # on peut calculer des distances, mais on peut aussi remarquer
            # que le point le plus éloigné de p est celui le plus à droite
            # ou, le cas échéant, le plus haut...
            if L[i][0] - p[0] > L2[-1][0] - p[0] or L[i][1] > L2[-1][1]:
                L2.pop()
                L2.append(L[i])
    return L2
    
def enveloppe(p, L):
    P = [p, L[0]]
    i = 1
    while i < len(L):
        if orientation(P[-2], P[-1], L[i]) < 0:
            P.pop()
        else:
            P.append(L[i])
            i += 1
            
    return P

def traite(P):
    """ détermine l'enveloppe convexe de P, et trace le tout """
    """ premier tracé : le nuage de points seul"""
    X = [P[i][0] for i in range(len(P))]
    Y = [P[i][1] for i in range(len(P))]
    mpl.figure()
    mpl.axis("off")
    mpl.scatter(X, Y, c='black')
    
    """deuxième tracé : le point à gauche relié aux autres points """
    i = pointGauche(P)
    p, L = prepare(P)
    mpl.figure()
    mpl.axis("off")
    for i in range(len(L)):
        mpl.plot([p[0], L[i][0]], [p[1], L[i][1]], 'black')
    X = [L[i][0] for i in range(len(L))]
    Y = [L[i][1] for i in range(len(L))]
    X.append(p[0])
    Y.append(p[1])
    mpl.scatter(X, Y, c="black")
    
    """ troisième tracé : comme le précédent, mais ont été retirés
    les points alignés avec p """
    L = menage(p, L)
    mpl.figure()
    mpl.axis("off")
    for i in range(len(L)):
        mpl.plot([p[0], L[i][0]], [p[1], L[i][1]], 'black')
    X = [L[i][0] for i in range(len(L))]
    Y = [L[i][1] for i in range(len(L))]
    X.append(p[0])
    Y.append(p[1])
    mpl.scatter(X, Y, c="black")
    
    """nuage de points et son enveloppe convexe """
    L = enveloppe(p, L)
    X = [P[i][0] for i in range(len(P))]
    Y = [P[i][1] for i in range(len(P))]
    mpl.figure()
    mpl.axis("off")
    mpl.scatter(X, Y, c="black")
    X = [L[i][0] for i in range(len(L))]
    Y = [L[i][1] for i in range(len(L))]
    mpl.fill(X, Y, 'black', alpha = 0.3)
    mpl.plot(X, Y, 'black')
    mpl.plot([X[-1], X[0]], [Y[-1], Y[0]], 'black')