| 1234567891011121314151617181920212223242526272829303132333435363738 |
- # Author: mozman
- # Purpose: convex hull algorithm
- # Created: 28.02.2010
- # License: MIT License
- from typing import TYPE_CHECKING, Iterable, List
- from ezdxf.math.construct2d import left_of_line
- if TYPE_CHECKING:
- from ezdxf.eztypes import Vertex
- def convex_hull_2d(points: Iterable['Vertex'])->List['Vertex']:
- def _convexhull(hull):
- while len(hull) > 2:
- start_point, check_point, destination_point = hull[-3:] # the last three points
- if not left_of_line(check_point, start_point, destination_point): # curve not turns right
- del hull[-2] # remove the penultimate point
- else:
- break
- return hull
- points = sorted(set(points)) # remove duplicate points
- if len(points) < 3:
- raise ValueError("ConvexHull(): Less than 3 unique points given!")
- upper_hull = points[:2] # first two points
- for next_point in points[2:]:
- upper_hull.append(next_point)
- upper_hull = _convexhull(upper_hull)
- lower_hull = [points[-1], points[-2]] # last two points
- for next_point in reversed(points[:-2]):
- lower_hull.append(next_point)
- lower_hull = _convexhull(lower_hull)
- upper_hull.extend(lower_hull[1:-1])
- return upper_hull
|
