In this post we will talk about convex hulls which have a broad range of applications in mathematics, computer science and surely image processing / computer vision. In mathematics the convex hull (sometimes also called the convex envelope) of a set of points X in the Euclidean plane or Euclidean space is the smallest convex set that contains X. More details about the convex hull theory can be found on this Wikipedia page which is always a very good start for learning things;-) Convex hulls are very common in image processing and computer vision though, I presume that almost every “image processor” has already faced in his career a need to find a polygon of a given point-set, no matter in what kind of application. Usually the convex hull needs to be built as fast as possible and the most common operation with the polygon is detection whether some random point is inside it or not. Exactly this problem we are going to solve now, and, as usual, we will write some Python code doing this for us.
There are various algorithms for building the convex hull of a finite set of points. A list of known convex hull algorithms can be found here. We will consider the general case when the input to the algorithm is a finite unordered set of points on a Cartesian plane using Andrew’s monotone chain convex hull algorithm. This approach constructs the convex hull in time. The full description of the algorithm including its implementations in Pseudo-code, Python, C/C++ can be found here. First of all it sorts all points lexicographically (first by x-coordinate, and in case of a tie, by y-coordinate) and then constructs upper and lower hulls of the points in time. An upper hull is the part of the convex hull, which is visible from above, while lower hull is the remaining part of the convex hull.
Let’s build the convex hull of a set of randomly generated 2D points. In our example we define a Cartesian grid of and generate points on this grid.
import matplotlib.pyplot as plt import random grid_dimension_x = 10 # X grid dimension grid_dimension_y = 10 # Y grid dimension nmb = 15 # number of points # generate points nx = [random.randint(0, grid_dimension_x) for i in range(nmb)] ny = [random.randint(0, grid_dimension_y) for i in range(nmb)] # store points as a list of tuples for convex hull computation points_input =  for ind in range(nmb): points_input.append( (nx[ind], ny[ind]) )
For building the convex hull we define one additional function. Once input points are lexicographically sorted, we build both the upper and lower hulls. For this we traverse points checking whether the sequence of last two points and a candidate point make a counter-clockwise turn. Only points making a counter-clockwise turn are taken. To figure out whether points make a clockwise or counter-clockwise turn we compute a 2D cross product of vectors OA and OB, where O is the first points, A is the second point and B is the third point, respectively. The cross product is computed here in two dimensions and the sign of the determinant is considered:
def cross(o, a, b): """ 2D cross product of OA and OB vectors, i.e. z-component of their 3D cross product. :param o: point O :param a: point A :param b: point B :return cross product of vectors OA and OB (OA x OB), positive if OAB makes a counter-clockwise turn, negative for clockwise turn, and zero if the points are colinear. """ return (a - o) * (b - o) -\ (a - o) * (b - o)
Now we are ready to build the convex hull:
hull_vertices = convex_hull(points_input)
def convex_hull(points): """ Computation of a convex hull for a set of 2D points. :param points: sequence of (x, y) pairs representing the points. :return a list of vertices of the convex hull in counter-clockwise order, starting from the vertex with the lexicographically smallest coordinates. """
# Sort the points lexicographically (tuples are compared # lexicographically). # Remove duplicates to detect the case we have just one # unique point. points = sorted(set(points)) # Boring case: no points or a single point, possibly # repeated multiple times. if len(points) <= 1: return points # Build lower hull lower =  for p in points: while len(lower) >= 2 and cross(lower[-2], lower[-1], p)\ <= 0: lower.pop() lower.append(p) # Build upper hull upper =  for p in reversed(points): while len(upper) >= 2 and cross(upper[-2], upper[-1], p) \ <= 0: upper.pop() upper.append(p) # Concatenation of the lower and upper hulls gives # the convex hull # The first point occurs in the list twice, since it's # at the same time the last point convex_hull_vertices = lower[:] + upper[:]
Since we store input points as a list of tuples, to plot data using Matplotlib we define a function for separating X and Y coordinates:
def get_coordinates(points_list): """ Extract x and y point coordinates from a list of tuples. :param points_list: points as a list of tuples :return x and y point coordinates as separate lists """ x =  y =  for ind in range(len(points_list)): x.append(points_list[ind]) y.append(points_list[ind]) return x, y
Here we plot input points (black) with the corresponding upper (red) and lower (blue) convex hulls:
# plot data plt.figure("Convex hull computation") # grid plt.axis( [-1, grid_dimension_x + 1, -1, grid_dimension_y + 1] ) # plot input points points_x, points_y = get_coordinates(points) plt.plot(points_x, points_y, 'ko') # draw lower convex hull lower_x, lower_y = get_coordinates(lower) plt.plot(lower_x, lower_y, linestyle='-', color='blue') # draw upper convex hull upper_x, upper_y = get_coordinates(upper) plt.plot(upper_x, upper_y, linestyle='-', color='red') return convex_hull_vertices
Since vertices of the convex hull are stored in the list convex_hull_vertices in counter-clockwise order, the check whether a random point on the grid is inside or outside the convex hull is quite straightforward: we just need to traverse all vertices of the convex hull checking that all of them make a counter-clockwise turn with the point under consideration. If it is not the case even for one vertex – the point is outside the convex hull.
# generate a point to be checked x = random.randint(0, grid_dimension_x) y = random.randint(0, grid_dimension_y) inside = True for ind in range(1, len(hull_vertices)): res = cross(hull_vertices[ind-1], hull_vertices[ind], (x,y)) print 'cross res = ', res if res < 0: inside = False if inside: str_output = 'Inside' else: str_output = 'Outside' # plot data fig = plt.figure("Checking a point") plt.axis( [-1, grid_dimension_x + 1, -1, grid_dimension_y + 1] ) # label with the check result ax = fig.add_subplot(111) ax.text(0.95, 0.01, str_output, verticalalignment='bottom', horizontalalignment='right', transform=ax.transAxes, color='green', fontsize=15) # obtained convex hull hull_x, hull_y = get_coordinates(hull_vertices) plt.plot(hull_x, hull_y, linestyle='-', color='blue') # point to be checked plt.plot(x, y, 'go') # do not forget to show both plots plt.show()
The final plot is shown below. In our run point was located outside the convex hull: