-
Notifications
You must be signed in to change notification settings - Fork 2
/
convex-hull.py
110 lines (74 loc) · 2.89 KB
/
convex-hull.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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
'''
author: Jacob Egner
date: 2015-08-02
island: ice base
puzzle URLs:
http://www.checkio.org/mission/convex-hull/
https://github.com/Bryukh-Checkio-Tasks/checkio-task-convex-hull
for latest versions of my solutions, see my checkio solution github repo:
https://github.com/jmegner/CheckioPuzzles
Discussion:
I use the approach described at
https://www.topcoder.com/community/data-science/data-science-tutorials/geometry-concepts-line-intersection-and-its-applications/#convexhull
'''
import collections
import math
class Point(collections.namedtuple('Point', ['x', 'y'])):
def __neg__(self):
return Point(-self.x, -self.y)
def __add__(self, other):
return Point(self.x + other.x, self.y + other.y)
def __sub__(self, other):
return Point(self.x - other.x, self.y - other.y)
def __mul__(self, scale):
return Point(self.x * scale, self.y * scale)
def __truediv__(self, scale):
return Point(self.x / scale, self.y / scale)
def distTo(self, other):
return math.hypot(self.x - other.x, self.y - other.y)
@staticmethod
def crossProduct(p1, p2, p3):
del1 = p2 - p1
del2 = p3 - p2
return del1.x * del2.y - del1.y * del2.x
def checkio(coords):
pointToOrigIdx = {
Point(*coord) : coordIdx
for coordIdx, coord in enumerate(coords)
}
hullPoints = [min(pointToOrigIdx)]
unusedPoints = set(pointToOrigIdx)
while len(hullPoints) == 1 or hullPoints[0] != hullPoints[-1]:
nextHullPoint = None
for point in unusedPoints:
if point == hullPoints[-1]:
continue
shouldReplaceNextHullPoint = False
if nextHullPoint is None:
shouldReplaceNextHullPoint = True
else:
crossVal = Point.crossProduct(
nextHullPoint, hullPoints[-1], point)
if crossVal < 0:
shouldReplaceNextHullPoint = True
elif crossVal > 0:
shouldReplaceNextHullPoint = False
else:
newDist = hullPoints[-1].distTo(point)
oldDist = hullPoints[-1].distTo(nextHullPoint)
shouldReplaceNextHullPoint = newDist < oldDist
if shouldReplaceNextHullPoint:
nextHullPoint = point
hullPoints.append(nextHullPoint)
unusedPoints.remove(nextHullPoint)
return [pointToOrigIdx[hullPoint] for hullPoint in hullPoints[:-1]]
if __name__ == '__main__':
assert checkio(
[[7, 6], [8, 4], [7, 2], [3, 2], [1, 6], [1, 8], [4, 9]]
) == [4, 5, 6, 0, 1, 2, 3], "First example"
assert checkio(
[[3, 8], [1, 6], [6, 2], [7, 6], [5, 5], [8, 4], [6, 8]]
) == [1, 0, 6, 3, 5, 2], "Second example"
assert checkio(
[[7,4],[5,2],[4,7],[4,1],[3,6],[1,4]]
) == [5, 4, 2, 0, 1, 3], "Test 6 with collinearities"