# geoalg / geoalg / convexhull.py

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52``` ```#!/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 ```