Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #!/usr/bin/python
- # -*- encoding: utf-8 -*-
- # pylint: disable=invalid-name,missing-docstring,bad-builtin,star-args
- from operator import itemgetter
- from math import atan2
- from functools import partial
- def polar(x, origin):
- # atan2 range -> [-π, π]
- # return range -> [0, π] as our origin has the minimum y coordinate
- # CAUTION: based on the assumption that origin has the min-y-coordinate
- return atan2(x[1] - origin[1], x[0] - origin[0])
- def ccw(a, b, c):
- """
- 1 | ax ay 1 |
- area(a, b, c) = - * | bx by 1 |
- 2 | cx cy 1 |
- a vector calculus application,
- counter-clockwise turn positive area.
- colckwise turn negative area.
- collinear zero area.
- """
- return ((b[0] - a[0])*(c[1] - a[1]) - (b[1] - a[1])*(c[0] - a[0])) > 0
- def grahams(points):
- """
- :points:
- [(x1, y1), (x2, y2), (x3, y3), ..., (xn, yn)]
- """
- n = len(points)
- start = min(points, key=itemgetter(1))
- points = sorted(points, key=partial(polar, origin=start))
- hull = []
- for x in xrange(n):
- while len(hull) >= 2 and not ccw(hull[-2], hull[-1], points[x]):
- hull.pop()
- hull.append(points[x])
- return hull
- def main():
- from random import randrange
- points = [(randrange(20), randrange(10)) for _ in xrange(30)]
- hull = grahams(points)
- print 'original points'
- out = []
- for y in xrange(10, -1, -1):
- for x in xrange(20):
- out.append('*' if (x, y) in points else ' ')
- out.append('\n')
- print ''.join(out)
- print 'convex hull points'
- out = []
- for y in xrange(10, -1, -1):
- for x in xrange(20):
- out.append('*' if (x, y) in hull else ' ')
- out.append('\n')
- print ''.join(out)
- main()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement