convex hull

Data

Tags

geometry, mathematics

Source Code

``````__author__ = "Mahaveer Verma"
__email__ = "mahaveer.verma1@gmail.com"

'''
Convex Hull:
In mathematics, the convex hull or convex envelope of a set X of points in the Euclidean plane or Euclidean space is the smallest convex set that contains X.
For instance, when X is a bounded subset of the plane, the convex hull may be visualized as the shape enclosed by a rubber band stretched around X.
See : http://en.wikipedia.org/wiki/Convex_hull

Algorithm used: Gift Wrapping aka Jarvis March (2D)

Usage:
ConvexHull([(x1,y1),(x2,y2)...,(xn,yn)]) -- or -- ConvexHull([[x1,y1)],[x2,y2]...,[xn,yn]])
This will return a list of pts that define our convex hull. See convex_hull_test.py for a 40 point test case with output plot.
'''

import math
def ConvexHull(pts):
convex_hull=[] # Result array which gets appended over loops
start_pt=pts[0] # This array will (ultimately) store the value of bottom-right-most point in X-Y plane. This is where we start gift wrapping from.
start_id=0 # Just for swapping purpose
for x in range(1,len(pts)): # Loop to find out the bottom-right-most point.
if(pts[x][1]<start_pt[1]):
start_pt=pts[x]
start_id=x
elif (pts[x][1]==start_pt[1] and pts[x][0]>start_pt[0]):
start_pt=pts[x]
start_id=x
convex_hull.append(start_pt) # First element of convex hull
pts[0],pts[start_id]=pts[start_id],pts[0] # Modifying the input array so that our first element goes to the 0th array position. Done by swapping.
current_pt=start_pt # To store the last found point on convex hull. Necessary for calculating angles.
last_angle=math.pi # To store angle made by last 2 points on convex hull. Used for checking a condition which says that no new point on the hull paired with the last found point can make an angle larger than the 2nd last found point paired with the last point.
while(pts[0]==start_pt): # Main loop. Continues as long as a closed loop is not formed.
max_angle=-(math.pi) # Starting from -180 degree. This comes from the fact that we started with the bottom-right-most point.
for i in range(len(pts)):
angle=math.atan2((pts[i][1]-current_pt[1]),(pts[i][0]-current_pt[0]))
if(angle>=max_angle and angle<last_angle):
max_angle=angle
temp_pt=pts[i]
if(temp_pt!=current_pt):
convex_hull.append(temp_pt)
current_pt=temp_pt
pts.remove(temp_pt)
last_angle=max_angle
elif(temp_pt==start_pt):
break
del convex_hull[-1] # To remove last element in result array which is the same as the first element.
return convex_hull``````
``````__author__ = "Mahaveer Verma"
__email__ = "mahaveer.verma1@gmail.com"

import matplotlib.pyplot as plt
import convex_hull

pts=[[0.3215348546593775, 0.03629583077160248], [-0.4404289572876217, -0.2894855991839297],
[0.02402358131857918, -0.2356728797179394], [0.04590851212470659, -0.4156409924995536],
[0.3218384001607433, 0.1379850698988746], [0.11506479756447, -0.1059521474930943],
[0.2622539999543261, -0.29702873322836], [-0.161920957418085, -0.4055339716426413],
[0.1905378631228002, 0.3698601009043493], [0.2387090918968516, -0.01629827079949742],
[0.07495888748668034, -0.1659825110491202], [0.3319341836794598, -0.1821814101954749],
[0.07703635755650362, -0.2499430638271785], [0.2069242999022122, -0.2232970760420869],
[0.04604079532068295, -0.1923573186549892], [0.05054295812784038, 0.4754929463150845],
[-0.3900589168910486, 0.2797829520700341], [0.3120693385713448, -0.0506329867529059],
[0.01138812723698857, 0.4002504701728471], [0.009645149586391732, 0.1060251100976254],
[-0.03597933197019559, 0.2953639456959105], [0.1818290866742182, 0.001454397571696298],
[0.444056063372694, 0.2502497166863175], [-0.05301752458607545, -0.06553921621808712],
[0.4823896228171788, -0.4776170002088109], [-0.3089226845734964, -0.06356112199235814],
[-0.271780741188471, 0.1810810595574612], [0.4293626522918815, 0.2980897964891882],
[-0.004796652127799228, 0.382663812844701], [0.430695573269106, -0.2995073500084759],
[0.1799668387323309, -0.2973467472915973], [0.4932166845474547, 0.4928094162538735],
[-0.3521487911717489, 0.4352656197131292], [-0.4907368011686362, 0.1865826865533206],
[-0.1047924716070224, -0.247073392148198], [0.4374961861758457, -0.001606279519951237],
[0.003256207800708899, -0.2729194320486108], [0.04310378203457577, 0.4452604050238248],
[0.4916198379282093, -0.345391701297268], [0.001675087028811806, 0.1531837672490476]] # Test input of 40 points

convex_hull=convex_hull.ConvexHull(pts) # Function call
ip_x=[]
ip_y=[]
op_x=[]
op_y=[]
for ip_index in range(len(pts)):
ip_x.append(pts[ip_index][0])
ip_y.append(pts[ip_index][1])
for op_index in range(len(convex_hull)):
op_x.append(convex_hull[op_index][0])
op_y.append(convex_hull[op_index][1])
print "Convex Hull: "+str(convex_hull) # Print output
plt.plot(ip_x,ip_y,'bo',op_x,op_y,'ro') # Plot input and output for visual
plt.title('BLUE - Input Points | RED - Convex Hull')
plt.show()``````