# # Convex hull algorithm - Library (Python) # # Copyright (c) 2021 Project Nayuki # https://www.nayuki.io/page/convex-hull-algorithm # # This program is free software: you can redistribute it and/or modify # it under the terms of the GNU Lesser 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 Lesser General Public License for more details. # # You should have received a copy of the GNU Lesser General Public License # along with this program (see COPYING.txt and COPYING.LESSER.txt). # If not, see . # from typing import List, Sequence, Tuple # Returns a new list of points representing the convex hull of # the given set of points. The convex hull excludes collinear points. # This algorithm runs in O(n log n) time. def make_hull(points: Sequence[Tuple[float,float]]) -> List[Tuple[float,float]]: return make_hull_presorted(sorted(points)) # Returns the convex hull, assuming that each points[i] <= points[i + 1]. Runs in O(n) time. def make_hull_presorted(points: Sequence[Tuple[float,float]]) -> List[Tuple[float,float]]: if len(points) <= 1: return list(points) # Andrew's monotone chain algorithm. Positive y coordinates correspond to "up" # as per the mathematical convention, instead of "down" as per the computer # graphics convention. This doesn't affect the correctness of the result. upperhull: List[Tuple[float,float]] = [] lowerhull: List[Tuple[float,float]] = [] for hull in (upperhull, lowerhull): for p in (points if (hull is upperhull) else reversed(points)): while len(hull) >= 2: qx, qy = hull[-1] rx, ry = hull[-2] if (qx - rx) * (p[1] - ry) >= (qy - ry) * (p[0] - rx): del hull[-1] else: break hull.append(p) del hull[-1] if not (len(upperhull) == 1 and upperhull == lowerhull): upperhull.extend(lowerhull) return upperhull