What is a "convex hull" in programming and what are they used for?

Answer 1

A convex hull is a shape. It can exist in any dimension greater than 2, although 2 and 3 dimensional cases are often considered. Given a collection of vertex positions in some dimension (often called a 'cloud' of vertices), the convex hull of those vertices is the shape with the largest volume containing or intersecting every point in the cloud.

Convex Hulls provide a lot of simplifications for intersection queries. Being able to assume that every triangle is convex opens many shortcuts, making this shape ideal for polygonal representations for the purpose of collision detection. The most common use for the convex hull is probably in video games to represent the collision shape for a rigid body.

Answer 2

The convex hull is computed over a set of points (either 2-D or 3-D). The convex hull is the subset of the points that are on the outside of the set. Here are a couple of visualizations:

For a 2-D set of points, imagine the points lying on a board and pounding a nail into each point. Then take a big rubber band, stretch it out so that all the nails are inside of it, and let it go. The nails that the rubber band touches form the convex hull.

For a 3-D set of points, imagine wrapping the points in wrapping paper like a gift. When you stretch the wrapping paper firmly around the points, the points that the paper touches form the convex hull.

There are several efficient algorithms for computing the convex hull of a set of points.

What is it used for? Well, it tells you "outside" points vs. "inside" points, which in itself is not often useful. However, the convex hull is a very common and useful first step in many other computational geometry algorithms.

For example, suppose you want to find which pair of points are furthest apart in your set. Both points will be in the convex hull, so this can dramatically limit the pairs of points you need to consider.

If you are looking for code, I would start at http://qhull.org/.

Good luck!

Answer 3

It would appear to be a mathematical algorithm used in computing.
Follow the link to "Lambert's Java visualization of convex hull algorithms" for more information