Convex hull of a simple polygon
From Wikipedia, the free encyclopedia
In discrete geometry and computational geometry, the convex hull of a simple polygon is the polygon of minimum perimeter that contains a given simple polygon. It is a special case of the more general concept of a convex hull. It can be computed in linear time, faster than algorithms for convex hulls of point sets.
The convex hull of a simple polygon can be subdivided into the given polygon itself and into polygonal pockets bounded by a polygonal chain of the polygon together with a single convex hull edge. Repeatedly reflecting an arbitrarily chosen pocket across this convex hull edge produces a sequence of larger simple polygons; according to the Erdős–Nagy theorem, this process eventually terminates with a convex polygon.
The convex hull of a simple polygon is itself a convex polygon. Overlaying the original simple polygon onto its convex hull partitions this convex polygon into regions, one of which is the original polygon. The remaining regions are called pockets. Each pocket is itself a simple polygon, bounded by a polygonal chain on the boundary of the given simple polygon and by a single edge of the convex hull. A polygon that is already convex has no pockets.[1]
One can form a hierarchical description of any given polygon by constructing its hull and its pockets in this way and then recursively forming a hierarchy of the same type for each pocket.[1] This structure, called a convex differences tree, can be constructed efficiently.[2]