| |
| |
| 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): |
| |
| if n < 3: |
| return |
|
|
| |
| 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: |
| |
| 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 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 |
|
|
| |
| if p == l: |
| break |
|
|
| |
| 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)) |
|
|
