|
| 1 | +''' |
| 2 | +Layout: algorithms |
| 3 | +Title : Graham Scan Algorithm |
| 4 | +Author: RadientBrain |
| 5 | +''' |
| 6 | + |
| 7 | + |
| 8 | +from random import randint |
| 9 | +import matplotlib.pyplot as plt |
| 10 | + |
| 11 | + |
| 12 | +def orientation(m, n, o): |
| 13 | + val = ((n[1]-m[1])*(o[0]-n[0])) - ((o[1]-n[1])*(n[0]-m[0])) |
| 14 | + if val > 0: |
| 15 | + return 1 |
| 16 | + elif val < 0: |
| 17 | + return -1 |
| 18 | + else: |
| 19 | + return 0 |
| 20 | + |
| 21 | +def distance(m, n): |
| 22 | + return (n[0]-m[0])**2 + (n[1]-m[1])**2 |
| 23 | + |
| 24 | +def Sorting_with_bubble(coordinates, b): |
| 25 | + for coord_ith in range(len(coordinates)): |
| 26 | + for j in range(len(coordinates)-coord_ith-1): |
| 27 | + if (orientation(b, coordinates[j], coordinates[j+1]) > 0) or (orientation(b, coordinates[j], coordinates[j+1])==0 and (distance(b, coordinates[j]) > distance(b, coordinates[j+1]))): |
| 28 | + temp = coordinates[j+1] |
| 29 | + coordinates[j+1] = coordinates[j] |
| 30 | + coordinates[j] = temp |
| 31 | + |
| 32 | + return coordinates |
| 33 | + |
| 34 | + |
| 35 | +def Convex_hull_through_graham(coordinates): |
| 36 | + b = min(coordinates, key= lambda coord: (coord[1], coord[0])) |
| 37 | + coord_ith = coordinates.index(b) |
| 38 | + coordinates[coord_ith]=coordinates[0] |
| 39 | + coordinates[0] = b |
| 40 | + coordinates = [b] + Sorting_with_bubble(coordinates[1:], b) |
| 41 | + size_triplet = [coordinates[0], coordinates[1], coordinates[2]] |
| 42 | + for coord_ith in range(3, len(coordinates)): |
| 43 | + while len(size_triplet)>=3 and orientation(size_triplet[-2], size_triplet[-1], coordinates[coord_ith]) >= 0: |
| 44 | + size_triplet.pop() |
| 45 | + size_triplet.append(coordinates[coord_ith]) |
| 46 | + return size_triplet+[size_triplet[0]] |
| 47 | + |
| 48 | + |
| 49 | +def random_points(n=30): |
| 50 | + coordinates = [(randint(0, n), randint(0, n)) for _ in range(n)] |
| 51 | + print (coordinates) |
| 52 | + return coordinates |
| 53 | + |
| 54 | + |
| 55 | +if __name__ == "__main__": |
| 56 | + coordinates = random_points(120) |
| 57 | + |
| 58 | + X = [coord[0] for coord in coordinates] |
| 59 | + Y = [coord[1] for coord in coordinates] |
| 60 | + plt.plot(X, Y, '.b') |
| 61 | + |
| 62 | + boundary_poly = Convex_hull_through_graham(coordinates) |
| 63 | + |
| 64 | + X = [coord[0] for coord in boundary_poly] |
| 65 | + Y = [coord[1] for coord in boundary_poly] |
| 66 | + plt.plot(X, Y, '-og') |
| 67 | + |
| 68 | + plt.show() |
0 commit comments