File size: 2,419 Bytes
dc2b6ec | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 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 94 95 96 97 98 99 100 | # Convex Hull
# point class with x, y as point
class Point:
def __init__(self, x, y):
self.x = x
self.y = y
def Left_index(points):
"""Finding the left most point"""
minn = 0
for i in range(1, len(points)):
if points[i].x < points[minn].x:
minn = i
elif points[i].x == points[minn].x:
if points[i].y > points[minn].y:
minn = i
return minn
def orientation(p, q, r):
"""
To find orientation of ordered triplet (p, q, r).
The function returns following values
0 --> p, q and r are colinear
1 --> Clockwise
2 --> Counterclockwise
"""
val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y)
if val == 0:
return 0
elif val > 0:
return 1
else:
return 2
def convexHull(points, n):
# There must be at least 3 points
if n < 3:
return
# Find the leftmost point
l = Left_index(points)
hull = []
"""
Start from leftmost point, keep moving counterclockwise
until reach the start point again. This loop runs O(h)
times where h is number of points in result or output.
"""
p = l
q = 0
while True:
# Add current point to result
hull.append(p)
"""
Search for a point 'q' such that orientation(p, x,
q) is counterclockwise for all points 'x'. The idea
is to keep track of last visited most counterclock-
wise point in q. If any point 'i' is more counterclock-
wise than q, then update q.
"""
q = (p + 1) % n
for i in range(n):
# If i is more counterclockwise than current q, then update q
if orientation(points[p], points[i], points[q]) == 2:
q = i
"""
Now q is the most counterclockwise with respect to p
Set p as q for next iteration, so that q is added to
result 'hull'
"""
p = q
# While we don't come to first point
if p == l:
break
# Print Result
result = []
for each in hull:
result.append([points[each].x, points[each].y])
return result
def apply_convex_hull(coordinates):
points = []
for coordinate in coordinates:
x, y = coordinate[0], coordinate[1]
points.append(Point(x, y))
return convexHull(points, len(points))
|