Convex Hulls vs. Nonconvex Polygons

The convex hull of a set of points in N-D space is the smallest convex region enclosing all points in the set. If you think of a 2-D set of points as pegs in a peg board, the convex hull of that set would be formed by taking an elastic band and using it to enclose all the pegs.

rng("default")
x = rand(20,1);
y = rand(20,1);
plot(x,y,"r.",MarkerSize=10)
hold on
k = convhull(x,y);
plot(x(k),y(k))
title("The Convex Hull of a Set of Points")
hold off

A convex polygon is a polygon that does not have concave vertices, for example:

x = rand(20,1);
y = rand(20,1);
plot(x,y,"r.",MarkerSize=10)
hold on
k = convhull(x,y);
plot(x(k),y(k))
title("Convex Polygon")
hold off

You also can create a boundary of a point set that is nonconvex. If you shrink and tighten the convex hull from above, you can enclose all of the points in a nonconvex polygon with concave vertices:

plot(x,y,"r.",MarkerSize=10)
hold on
k = boundary(x,y,0.9);
plot(x(k),y(k))
title("Nonconvex Polygon")
hold off

The convex hull has numerous applications. You can compute the upper bound on the area bounded by a discrete point set in the plane from the convex hull of the set. The convex hull simplifies the representation of more complex polygons or polyhedra. For instance, to determine whether two nonconvex bodies intersect, you could apply a series of fast rejection steps to avoid the penalty of a full intersection analysis:

• Check if the axis-aligned bounding boxes around each body intersect.

• If the bounding boxes intersect, you can compute the convex hull of each body and check intersection of the hulls.

If the convex hulls did not intersect, this would avoid the expense of a more comprehensive intersection test.

While convex hulls and nonconvex polygons are convenient ways to represent relatively simple boundaries, they are in fact specific instances of a more general geometric construct called the alpha shape.