| |
My Implementation
Utility functions
- calc_angle(pt1,pt2): calculate the angle between a line defined by two points and the horizontal
- dist(pt1,pt2): calculate the Euclidean distance between two points
- clockwise(): more detail in prior section
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
| # convenience functions to get the x,y value from a tuple,
# and avoid using the wrong tuple index
# (sacrifice a bit of performance for legibility)
def x(tp):
return tp[0]
def y(tp):
return tp[1]
# calculate the angle for a line between two points and the horizontal
def calc_angle(pt1, pt2):
dy=float( y(pt2) - y(pt1) )
dx=float( x(pt2) - x(pt1) )
angle=0.0
if dx!=0:
angle=math.atan(dy/dx)
else:
if dy==0:
angle=0.0
elif dy<0:
angle=math.atan(float('-inf'))
else:
angle=math.atan(float('inf'))
# if the calculated angle is negative, make it positive
while (angle<0):
angle=angle+2*math.pi;
return angle
# calculate the distance between two points
def dist(pt1,pt2):
dx=float( x(pt2) - x(pt1) )
dy=float( y(pt2) - y(pt1) )
return math.sqrt( dx*dx + dy*dy)
# does moving from point pts[i0] -> pts[i1] -> i2 describe a counterclockwise motion ?
def clockwise(pt1, pt2, pt3):
area = (x(pt2)-x(pt1))*(y(pt3)-y(pt1))-(y(pt2)-y(pt1))*(x(pt3)-x(pt1))
rv=0 # collinear
if area<0: rv=-1 # clockwise
elif area>0: rv=+1 # counter clockwise
return rv
|
Main body
Data: the location of the sheep.
1
| points= [ (9,2), (5,6), (3,10), (11,13), (7,6), (15,18), (19,16), (13,4), (23,8), (17,12) ]
|
Step 1: identify the starting point
1
2
3
4
| # identify the point with the lowest y coordinate and put it first in the list of points
# special case: in case of a tie, decide by lowest x coordinate
points=sorted( points, key=lambda a: a[0]) # secondary sort on x
points=sorted( points, key=lambda a: a[1]) # primary sort on y (python sort is stable)
|
Step 2: put the points in the correct order
1
2
3
4
5
6
7
8
9
| # enrich the tuple list with the angle between the line through (point, first point)
# and the horizontal
points = [ (x(pt),y(pt),calc_angle(points[0],pt)) for pt in points ]
# order the points by angle
points=sorted(points, key=lambda a: a[2])
# after sorting we don't need the angles anymore, let's drop them
points = [ (x(pt),y(pt)) for pt in points ]
|
Step 3: the core of the Graham scan
- iterate over the points in ascending angle order
- check if pt1-> pt2 -> pt3 makes a counterclockwise turn
- if NOT, then discard pt2
1
2
3
4
5
6
7
8
9
10
| hull=copy.deepcopy(points) # deep copy, because we are going to delete points
i=0
while True:
if clockwise(hull[i],hull[i+1],hull[i+2])<=0: # clockwise or collinear
del hull[i+1]
i-=1 # take a step back
else:
i+=1 # step forward
if (i+2)>=len(hull): # are we done?
break
|
Epilogue: print the list of points on the hull, calculate the perimeter and plot the points
1
2
3
4
5
6
7
8
9
10
11
12
| print "Points on the hull" ,hull
# to close the polygon, (for drawing, and calculating distance) append the first point
hull.append(hull[0])
print "Perimeter distance: ", sum( [ dist( hull[i],hull[i+1] ) for i in range(len(hull)-1) ] )
# plotting the points and the hull
plt.scatter(*zip(*points),s=20) # plot all the points
plt.plot(*zip(*hull),linestyle='-') # plot the hull
plt.savefig("convex_hull.png")
|
| |