-
Notifications
You must be signed in to change notification settings - Fork 1
/
16.11.py
59 lines (47 loc) · 1.77 KB
/
16.11.py
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
import math
def getConvexHull(myPoints):
# Step 1
h0 = getRightmostLowestPoint(myPoints)
H = [h0]
t0 = h0
# Step 2 and Step 3
while True:
t1 = myPoints[0]
for i in range(1, len(myPoints)):
status = whichSide(t0[0], t0[1], t1[0], t1[1], myPoints[i][0], myPoints[i][1])
if status < 0: # Right side of the line
t1 = myPoints[i]
elif status == 0:
if distance(myPoints[i][0], myPoints[i][1], t0[0], t0[1]) > distance(t1[0], t1[1], t0[0], t0[1]):
t1 = myPoints[i]
if t1[0] == h0[0] and t1[1] == h0[1]:
break; # A convex hull is found
else:
H.append(t1)
t0 = t1
return H
# Return the rightmost lowest point in S
def getRightmostLowestPoint(p):
rightMostIndex = 0;
rightMostX = p[0][0];
rightMostY = p[0][1];
for i in range(1, len(p)):
if rightMostY > p[i][1]:
rightMostY = p[i][1]
rightMostX = p[i][0]
rightMostIndex = i
elif rightMostY == p[i][1] and rightMostX < p[i][0]:
rightMostX = p[i][0]
rightMostIndex = i
return p[rightMostIndex]
def distance(x1, y1, x2, y2):
return math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2))
# Is (x2, y2) on the right side of [x0, y0] and [x1, y1]
def whichSide(x0, y0, x1, y1, x2, y2):
return (x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0)
coordinates = input("Enter the points: ")
c = coordinates.split()
points = [[eval(c[i]), eval(c[i + 1])] for i in range(0, len(c), 2)]
convexHull = getConvexHull(points)
print("The convex hull is ")
print(convexHull)