What is the convex hull?
The convex hull of a set of points is defined as the smallest convex polygon, that encloses all of the points in the set. Convex means that the polygon has no corner that is bent inwards.
The red edges on the right polygon enclose the corner where the shape is concave, the opposite of convex.
A useful way to think about the convex hull is the rubber band analogy. Suppose the points in the set were nails, sticking out of a flat surface. Imagine now, what would happen if you took a rubber band and stretched it around the nails. Trying to contract back to its original length, the rubber band would enclose the nails, touching the ones that stick out the furthest from the centre.
Comments
Post a Comment