Newer
Older
####################################################################################################
#
# Patro - A Python library to make patterns for fashion design
# Copyright (C) 2017 Fabrice Salvaire
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program. If not, see <http://www.gnu.org/licenses/>.
#
####################################################################################################
"""Module to compute bounding box and convex hull for a set of points.
"""
####################################################################################################
__all__ = [
'bounding_box_from_points',
'convex_hull',
]
####################################################################################################
import functools
####################################################################################################
def bounding_box_from_points(points):
"""Return the bounding box of the list of points."""
bounding_box = None
for point in points:
if bounding_box is None:
bounding_box = point.bounding_box
else:
bounding_box |= point.bounding_box
####################################################################################################
def _sort_point_for_graham_scan(points):
def sort_by_y(p0, p1):
return p0.x < p1.x if (p0.y == p1.y) else p0.y < p1.y
# sort by ascending y
sorted_points = sorted(points, key=functools.cmp_to_key(sort_by_y))
# sort by ascending slope with p0
p0 = sorted_points[0]
x0 = p0.x
y0 = p0.y
def slope(p):
# return (p - p0).tan
return (p.y - y0) / (p.x - x0)
def sort_by_slope(p0, p1):
s0 = slope(p0)
s1 = slope(p1)
return p0.x < p1.x if (s0 == s1) else s0 < s1
return sorted_points[0] + sorted(sorted_points[1:], key=cmp_to_key(sort_by_slope))
####################################################################################################
def _ccw(p1, p2, p3):
"""Three points are a counter-clockwise turn if ccw > 0, clockwise if ccw < 0, and collinear if ccw
= 0 because ccw is a determinant that gives twice the signed area of the triangle formed by p1,
p2 and p3.
"""
return (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x)
####################################################################################################
def convex_hull(points):
"""Return the convex hull of the list of points using Graham Scan algorithm.
References
* https://en.wikipedia.org/wiki/Graham_scan
# convex_hull is a stack of points beginning with the leftmost point.
convex_hull = []
sorted_points = _sort_point_for_graham_scan(points)
for p in sorted_points:
# if we turn clockwise to reach this point,
# pop the last point from the stack, else, append this point to it.
while len(convex_hull) > 1 and _ccw(convex_hull[-1], convex_hull[-2], p) >= 0: # Fixme: check
convex_hull.pop()
convex_hull.append(p)
# the stack is now a representation of the convex hull, return it.
return convex_hull