Source code for tryalgo.convex_hull

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""\
Convex hull by Andrew
jill-jênn vie et christoph dürr - 2014-2019
"""

# pylint: disable=redefined-outer-name

from random import randint


__all__ = ["andrew"]


# snip{ left-turn
def left_turn(a, b, c):
    """function left-turn"""
    return ((a[0] - c[0]) * (b[1] - c[1]) -
            (a[1] - c[1]) * (b[0] - c[0]) > 0)
# snip}


# snip{
[docs]def andrew(S): """Convex hull by Andrew :param S: list of points as coordinate pairs :requires: S has at least 2 points :returns: list of points of the convex hull :complexity: `O(n log n)` """ S.sort() top = [] bot = [] for p in S: while len(top) >= 2 and not left_turn(p, top[-1], top[-2]): top.pop() top.append(p) while len(bot) >= 2 and not left_turn(bot[-2], bot[-1], p): bot.pop() bot.append(p) return bot[:-1] + top[:0:-1]
# snip} # pylint: disable=missing-docstring if __name__ == "__main__": def gnuplot(L): for x, y in L: print(x, y) def tikz_points(S): for p in S: print('\\filldraw[black] (%f, %f) circle (1pt);' % p) def tikz_polygone(S): for i, _ in enumerate(S): print('\\draw[blue] (%f, %f) -- (%f, %f);' % (S[i - 1] + S[i])) S = [(randint(0, 25)/10., randint(0, 25)/10.) for _ in range(32)] tikz_points(S) tikz_polygone(andrew(S))