In [1]:

    

__author__ = "Víctor Adolfo Gallego Alcalá, Ana María Martínez Gómez"
%matplotlib inline
import matplotlib.pyplot as plt
import numpy as np

class Point:
    
    """ This class represents a point in the plane.
    
    __author__ = "Víctor Adolfo Gallego Alcalá, Ana María Martínez Gómez"
    
    __________
    Attributes
    __________
    
    x : float
        x-coordinate of the point
    y : float
        y-coordinate of the point
    name : string
        contains its coordinates
    """
    
    def __init__(self, x=None, y=None):
        """ Initialize the point by giving it its x and y coordinates
        """
        self.x = x
        self.y = y
        self.name = "( " + str(x) + ", " + str(y) + " )"
    
    def __repr__(self):
        """ Returns its name
        """
        return self.name
    
    def __le__(self, p):
        """ Method for <=
        """
        return self.x <= p.x
    
    def __lt__(self, p):
        """ Method for <
        """
        return self.x < p.x
    
    def isLeft(self, p2, p3):
        """ Returns 1 iff self is to the left of the segment p2p3, 0 iff it is
        collinear and -1 iff it is to the right. It computes the sign of the determinant of
        
        self.x self.y 1
         p2.x p2.y 1
         p3.x p3.y 1
        """
        return np.sign(-p2.x*self.y + p3.x*self.y + self.x*p2.y - p3.x*p2.y - self.x*p3.y + p2.x*p3.y)


    

In [5]:

    

P = [Point(20*np.random.rand() - 10,20*np.random.rand() - 10) for i in range(50)]
for p in P:
    plt.plot(p.x, p.y, 'ok')


    

In [6]:

    

def rightTurn(P):
    """ Helper function. Returns true iff the list of
    three points P is a turn to the right
    """
    return P[-1].isLeft(P[-3], P[-2]) == -1

def convexHull(P):
    """ Convex hull implemented using Graham's algorithm
    """
    P.sort()
    Lupper = P[:2]
    for p in P[2:]:
        Lupper.append(p)
        while len(Lupper)>2 and not rightTurn(Lupper[-3:]):
            del Lupper[-2]

    P.reverse()
    Llower = P[:2]
    for p in P[2:]:
        Llower.append(p)
        while len(Llower)>2 and not rightTurn(Llower[-3:]):
            del Llower[-2]
    del Llower[0]
    del Llower[-1]
    Lupper += Llower
    return Lupper


    

In [7]:

    

L = convexHull(P)
L.append(L[0])
plt.hold(True)
for i in range(len(L)-1):
    plt.plot([L[i].x, L[i+1].x], [L[i].y, L[i+1].y], 'r')
    
for p in P:
    plt.plot(p.x, p.y, 'ok')


    

In [ ]: