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. The whole code shown below is available here.

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 random
from dataclasses import dataclass

import matplotlib.pyplot as plt

POINTS_N = 15  # number of points

GRID_WIDTH = 10
GRID_HEIGHT = 10


@dataclass(frozen=True, order=True)
class Point:
    x: int = 0
    y: int = 0


Points = list[Point]


def generate_point() -> Point:
    return Point(random.randint(0, GRID_WIDTH), random.randint(0, GRID_HEIGHT))

# generate input points
points = [generate_point() for _ in range(POINTS_N)]

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(point_o: Point, point_a: Point, point_b: Point) -> int:
    """ 2D cross product of OA and OB vectors,
    i.e. z-component of their 3D cross product
    :param point_o: point O
    :param point_a: point A
    :param point_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 collinear
    """
    return (point_a.x - point_o.x) * (point_b.y - point_o.y) - (
            point_a.y - point_o.y) * (point_b.x - point_o.x)

Now we are ready to build the convex hull:

# find a convex hull
convex_hull = compute_convex_hull(points)

where

def compute_convex_hull(points: Points) -> Points:
    """ Computation of a convex hull for a set of 2D points.
    :param points: sequence of points
    :return a list of vertices of the convex hull in counter-clockwise order,
    starting from the vertex with the lexicographically smallest coordinates
    """
    # remove duplicates and sort points lexicographically
    # to detect the case we have just one unique point
    points = sorted(list(set(points)))

    # boring case: no points or a single point,
    # possibly repeated multiple times
    if len(points) <= 1:
        return points

    # build lower and upper hulls
    lower_hull = compute_hull_side(points)
    upper_hull = compute_hull_side(list(reversed(points)))

    # 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 = lower_hull + upper_hull
    draw_convex_hull(points, lower_hull, upper_hull)

    return convex_hull


def compute_hull_side(points: Points) -> Points:
    hull: Points = []
    for p in points:
        while len(hull) >= 2 and cross(hull[-2], hull[-1], p) <= 0:
            hull.pop()
        hull.append(p)

    return hull

Here we plot input points (black) with the corresponding upper (red) and lower (blue) convex hulls:

def draw_grid() -> None:
    plt.axis([-1, GRID_WIDTH + 1, -1, GRID_HEIGHT + 1])
    plt.grid(visible=True, which='major', color='0.75', linestyle='--')
    plt.xticks(range(-5, GRID_WIDTH + 1, 1))
    plt.yticks(range(-1, GRID_HEIGHT + 5, 1))


def draw_convex_hull(
        points: Points, lower_hull: Points, upper_hull: Points) -> None:
    plt.figure('Convex hull computation')
    draw_grid()
    plt.plot([p.x for p in points], [p.y for p in points], 'ko')
    plt.plot([p.x for p in lower_hull], [p.y for p in lower_hull],
             linestyle='-', color='blue', label='lower hull')
    plt.plot([p.x for p in upper_hull], [p.y for p in upper_hull],
             linestyle='-', color='red', label='upper hull')
    plt.legend(['Points', 'Lower Hull', 'Upper Hull'], loc='upper left')
    plt.show()
    plt.close()

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
point = generate_point()

# check the point
check_point(convex_hull, point)

where

def check_point(convex_hull: Points, point: Point) -> None:
    def _is_inside() -> bool:
        for idx in range(1, len(convex_hull)):
            if cross(convex_hull[idx - 1], convex_hull[idx], point) < 0:
                return False
        return True

    # visualize results
    draw_results(convex_hull, point, _is_inside())


def draw_results(convex_hull: Points, point: Point, is_inside: bool) -> None:
    fig = plt.figure('Checking a point')
    ax = fig.add_subplot()
    draw_grid()
    ax.text(
        0.95, 0.01, 'Inside' if is_inside else 'Outside',
        verticalalignment='bottom', horizontalalignment='right',
        transform=ax.transAxes, color='green', fontsize=15)

    plt.plot([p.x for p in convex_hull], [p.y for p in convex_hull],
             linestyle='-', color='blue')
    plt.plot(point.x, point.y, 'go')
    plt.legend(['Convex Hull', 'Input Point'], loc='upper left')
    plt.show()
    plt.close()

The final plot is shown below. In our run the target point was located inside the convex hull: