Source

geoalg / geoalg / convexhull.py

Full commit
#!/usr/bin/env python
#coding:utf-8
# Author:  mozman
# Purpose: convex hull algorithm
# Created: 28.02.2010

from __future__ import division
from __future__ import print_function
from __future__ import unicode_literals
from __future__ import absolute_import

__all__ = ['ConvexHull']

from geoalg import left_of_line

class ConvexHull(object):
    def __init__(self, points):
        self._points = ConvexHull._construct(points)

    def __iter__(self):
        return iter(self._points)

    def values(self):
        return self._points[:] # list shallow copy

    @staticmethod
    def _construct(points):
        def convex_hull(hull):
            while len(hull) > 2:
                start_point, check_point, destination_point = hull[-3:] # the last three points
                if not left_of_line(check_point, start_point, destination_point): # curve not turns right
                    del hull[-2] # remove the penultimate point
                else:
                    break
            return hull

        points = sorted(set(points)) #remove duplicate points

        if len(points) < 3:
            raise ValueError("ConvexHull(): Less than 3 unique points given!")

        upper_hull = points[:2] # first two points
        for next_point in points[2:]:
            upper_hull.append(next_point)
            upper_hull = convex_hull(upper_hull)
        lower_hull = [points[-1], points[-2]] # last two points

        for next_point in reversed(points[:-2]):
            lower_hull.append(next_point)
            lower_hull = convex_hull(lower_hull)
        upper_hull.extend(lower_hull[1:-1])
        return upper_hull