kopia lustrzana https://github.com/AfBu/k40whisperer_turbo
71 wiersze
2.5 KiB
Python
71 wiersze
2.5 KiB
Python
"""
|
|
2D Convex Hull Code from Wikibooks
|
|
https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain
|
|
"""
|
|
|
|
class hull2D:
|
|
|
|
def convex_hull(self,points):
|
|
"""Computes the convex hull of a set of 2D points.
|
|
|
|
Input: an iterable sequence of (x, y) pairs representing the points.
|
|
Output: a list of vertices of the convex hull in counter-clockwise order,
|
|
starting from the vertex with the lexicographically smallest coordinates.
|
|
Implements Andrew's monotone chain algorithm. O(n log n) complexity.
|
|
"""
|
|
|
|
# Sort the points lexicographically (tuples are compared lexicographically).
|
|
# Remove duplicates to detect the case we have just one unique point.
|
|
points = sorted(set(points))
|
|
|
|
# Boring case: no points or a single point, possibly repeated multiple times.
|
|
if len(points) <= 1:
|
|
return points
|
|
|
|
# 2D cross product of OA and OB vectors, i.e. z-component of their 3D cross product.
|
|
# Returns a positive value, if OAB makes a counter-clockwise turn,
|
|
# negative for clockwise turn, and zero if the points are collinear.
|
|
def cross(o, a, b):
|
|
return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
|
|
|
|
# Build lower hull
|
|
lower = []
|
|
for p in points:
|
|
while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
|
|
lower.pop()
|
|
lower.append(p)
|
|
|
|
# Build upper hull
|
|
upper = []
|
|
for p in reversed(points):
|
|
while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
|
|
upper.pop()
|
|
upper.append(p)
|
|
|
|
# Concatenation of the lower and upper hulls gives the convex hull.
|
|
# Last point of each list is omitted because it is repeated at the beginning of the other list.
|
|
return lower[:-1] + upper[:-1]
|
|
|
|
|
|
def convexHullecoords(self,ecoords):
|
|
p=[]
|
|
for line in ecoords:
|
|
p.append((line[0],line[1]))
|
|
|
|
hull_data = self.convex_hull(p)
|
|
ecoords=[]
|
|
for i in range(0,len(hull_data)):
|
|
ecoords.append([hull_data[i][0],hull_data[i][1],1])
|
|
ecoords.append(ecoords[0])
|
|
return ecoords
|
|
|
|
######################################################################
|
|
|
|
|
|
if __name__ == '__main__':
|
|
my_hull=hull2D()
|
|
p = [(1,1),(0,3),(0,0),(4,5),(10,10)]
|
|
c = my_hull.convex_hull(p)
|
|
print(p)
|
|
print(c)
|