Convex Hull Visualisation

import numpy as np
import matplotlib.pyplot as plt
from random import randint


def convex_hull(points):
    """Computes the convex hull of a set of 2D points.

    Input: an iterable sequence of (x, y) pairs representing the points.
    Output: a list of vertices of the convex hull in counter-clockwise order,
      starting from the vertex with the lexicographically smallest coordinates.
    Implements Andrew's monotone chain algorithm. O(n log n) complexity.
    """

    # Sort the points lexicographically (tuples are compared lexicographically).
    # Remove duplicates to detect the case we have just one unique point.
    points = sorted(set(points))

    # Boring case: no points or a single point, possibly repeated multiple times.
    if len(points) <= 1:
        return points

    # 2D cross product of OA and OB vectors, i.e. z-component of their 3D cross product.
    # Returns a positive value, if OAB makes a counter-clockwise turn,
    # negative for clockwise turn, and zero if the points are collinear.
    def cross(o, a, b):
        return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

    # Build lower hull
    lower = []
    for p in points:
        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)

    # Build upper hull
    upper = []
    for p in reversed(points):
        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)

    # Concatenation of the lower and upper hulls gives the convex hull.
    # Last point of each list is omitted because it is repeated at the beginning of the other list.
    return lower[:-1] + upper[:-1]


def rlist():
    retval = []
    for j in xrange(1, 3):
        for i in xrange((j+1)*5):
            limit = j*100
            retval.append((randint(limit, 1100-limit), randint(limit, 1100-limit)))
    return retval


def plot_list(lst, rim):
    x_list = []
    y_list = []
    for i in xrange(len(lst)):
        x_list.append(lst[i][0])
        y_list.append(lst[i][1])
    # fix, ax = plt.subplots()
    plt.plot(x_list, y_list, 'ro')
    plt.axis([0, 1100, 0, 1100])

    if rim:
        for start, stop in zip(rim[:-1], rim[1:]):
            x, y = zip(start, stop)
            # print(str(x) + ' ' + str(y))
            plt.plot(x, y, color=plt.cm.gist_ncar(1))
        # print(str(rim[0]) + ' ' + str(rim[-1]))
        x, y = zip(rim[0], rim[-1])
        plt.plot(x,y)


    plt.show()


data = rlist()

filtered = convex_hull(data)

# print(data)
# plot_list(data, None)
# print(filtered)
plot_list(data, filtered)