Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Appearance settings

Commit 2e5bbae

Browse filesBrowse files
authored
Merge pull request #95 from RadientBrain/master
2 parents da0ca9b + 360943b commit 2e5bbae
Copy full SHA for 2e5bbae

File tree

Expand file treeCollapse file tree

1 file changed

+68
-0
lines changed
Filter options
Expand file treeCollapse file tree

1 file changed

+68
-0
lines changed
+68Lines changed: 68 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,68 @@
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

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.