We read every piece of feedback, and take your input very seriously.
1 parent 562219f commit 0b73567Copy full SHA for 0b73567
convex-hull/convex-hull.py
@@ -2,7 +2,6 @@
2
import matplotlib.pyplot as plt
3
import random
4
5
-
6
Point = namedtuple('Point', 'x y')
7
8
@@ -19,26 +18,34 @@ def add(self, point):
19
18
def _get_orientation(self, origin, p1, p2):
20
'''
21
Returns the orientation of the Point p1 with regards to Point p2 using origin.
+ Negative if p1 is clockwise of p2.
22
:param p1:
23
:param p2:
24
:return: integer
25
26
difference = (
27
- ((p2.x - origin.x) * (p1.y - origin.y))
28
- - ((p1.x - origin.x) * (p2.y - origin.y))
29
- )
+ ((p2.x - origin.x) * (p1.y - origin.y))
+ - ((p1.x - origin.x) * (p2.y - origin.y))
+ )
30
31
return difference
32
33
def compute_hull(self):
34
35
- Computes the convex hull and returns the points on the hull.
+ Computes the points that make up the convex hull.
36
:return:
37
38
- points = sorted(self._points, key=lambda temp_point: temp_point.x)
+ points = self._points
39
40
+ # get leftmost point
41
start = points[0]
- point = points[0]
42
+ min_x = start.x
43
+ for p in points[1:]:
44
+ if p.x < min_x:
45
+ min_x = p.x
46
+ start = p
47
+
48
+ point = start
49
self._hull_points.append(start)
50
51
far_point = None
@@ -72,10 +79,12 @@ def get_hull_points(self):
72
79
return self._hull_points
73
80
74
81
def display(self):
82
+ # all points
75
83
x = [p.x for p in self._points]
76
84
y = [p.y for p in self._points]
77
85
plt.plot(x, y, marker='D', linestyle='None')
78
86
87
+ # hull points
88
hx = [p.x for p in self._hull_points]
89
hy = [p.y for p in self._hull_points]
90
plt.plot(hx, hy)
@@ -86,23 +95,10 @@ def display(self):
95
96
def main():
97
ch = ConvexHull()
- # for _ in range(10):
- # ch.add(Point(random.randint(0, 100), random.randint(0, 100)))
91
92
- ch.add(Point(1, 4))
93
- ch.add(Point(3, 12))
94
- ch.add(Point(5, 7))
- ch.add(Point(3, 6))
- ch.add(Point(12, 19))
- ch.add(Point(4, 8))
98
99
- ch.add(Point(9, 3))
100
- ch.add(Point(9, 6))
101
- ch.add(Point(10, 6))
102
- ch.add(Point(8, 16))
103
- ch.add(Point(2, 6))
104
105
- ch.compute_hull()
+ for _ in range(50):
+ ch.add(Point(random.randint(0, 100), random.randint(0, 100)))
+ print("Points on hull:", ch.get_hull_points())
106
ch.display()
107
108