Convex hull: how to tell whether a point is inside or outside?

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.

UpperAndLowerConvexHulls

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 O(n \log n) 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 O(n) 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 \bf{10 \times 10} and generate \bf{15} 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[0] - o[0]) * (b[1] - o[1]) -\
           (a[1] - o[1]) * (b[0] - o[0])

Now we are ready to build the convex hull:


hull_vertices = convex_hull(points_input)

where


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.
    """

looks like:


# 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][0])
        y.append(points_list[ind][1])

    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

convex_hull_computation

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:

checking_a_point

Best wishes,
Alexey

This entry was posted in Uncategorized. Bookmark the permalink.

2 Responses to Convex hull: how to tell whether a point is inside or outside?

  1. Chang says:

    Hi your algorithme to determine whether a point is in convex hull is fausse. your cross function just compute cross product, the positive negative dépends only on the angle of oa and ob, not the clockwise or counterclockwise direction. I also tried a point Inside convex hull. It returns “outside”.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s