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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
####################################################################################################
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."""
# Reference: Graham Scan Algorithm
# 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