Jump to content

Convex hull of a simple polygon

Add links
From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by David Eppstein (talk | contribs) at 17:34, 13 February 2021 (Undid revision 1006578188 by 23.249.37.131 (talk) we use https where available on Wikipedia, to avoid compromising the security of reader access patterns). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

The convex hull of a simple polygon (blue). Its four pockets are shown in yellow; the whole region shaded in either color is the convex hull.

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.

Structure

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]

Algorithms

Finding the convex hull of a simple polygon can be performed in linear time. Several early publications on this problem were discovered to be incorrect, often because they led to intermediate states with crossings that caused them to break. The first correct linear-time algorithm for this problem was given by McCallum & Avis (1979).[3] Even after its publication, other incorrect algorithms continued to be published.[4] Brönnimann & Chan (2006) write that a majority of the published algorithms for the problem are incorrect,[5] although a later history collected by Greg Aloupis lists only seven out of fifteen algorithms as being incorrect.[6]

A particularly simple algorithm for this problem was published by Graham & Yao (1983) and Lee (1983). Like the Graham scan algorithm for convex hulls of point sets, it is based on a stack data structure. The algorithm traverses the polygon in clockwise order, starting from a vertex known to be on the convex hull (for instance, its leftmost point). As it does, it stores a convex sequence of vertices on the stack, the ones that have not yet been identified as being within pockets. The points in this sequence are the vertices of a convex polygon (not necessarily the hull of all vertices seen so far) that may have pockets attached to some of its edges. At each step, the algorithm follows a path along the polygon from the stack top to the next vertex that is not in one of the two pockets adjacent to the stack top. Then, while the top two vertices on the stack together with this new vertex are not in convex position, it pops the stack, before finally pushing the new vertex onto the stack. When the clockwise traversal reaches the starting point, the algorithm is completed and the stack contains the convex hull vertices in clockwise order. Each step of the algorithm either pushes a vertex onto the stack or pops it from the stack, and each vertex is pushed and popped at most once, so the total time for the algorithm is linear.[7][8] If the input vertices are given in clockwise order in an array, then the output can be returned in the same array, using only a constant number of additional variables as intermediate storage.[5]

A similar method can also be used to construct convex hulls of piecewise smooth closed curves in the plane.[9] By using a deque in place of a stack, a similar algorithm can be generalized to the convex hull of any polygonal chain, and the algorithm for simple polygons can be started at any vertex of the polygon rather than requiring an extreme vertex as the starting vertex.[10]

Flipping pockets

Main article: Erdős–Nagy theorem

A flip of a pocket constructs a new polygon from the given one by reflecting the polygonal chain that bounds a pocket across the convex hull edge of the pocket. Each flip produces another simple polygon with equal perimeter and greater area, although multiple simultaneous flips may introduce crossings. Flipping an arbitrarily chosen pocket, and then repeating this process with the pockets of each successively formed polygon, produces a sequence of simple polygons. According to the Erdős–Nagy theorem, this flipping process eventually terminates, by reaching a convex polygon. As with the problem of convex hull construction, this problem has a long history of incorrect proofs.[11]

References

  1. ^ a b Tor, S. B.; Middleditch, A. E. (1984), "Convex decomposition of simple polygons", ACM Transactions on Graphics, 3 (4): 244–265, doi:10.1145/357346.357348
  2. ^ Rappoport, Ari (1992), "An efficient adaptive algorithm for constructing the convex differences tree of a simple polygon", Computer Graphics Forum, 11 (4): 235–240, doi:10.1111/1467-8659.1140235
  3. ^ McCallum, Duncan; Avis, David (1979), "A linear algorithm for finding the convex hull of a simple polygon", Information Processing Letters, 9 (5): 201–206, doi:10.1016/0020-0190(79)90069-3, MR 0552534
  4. ^ Toussaint, Godfried (1991), "A counter-example to a convex hull algorithm for polygons", Pattern Recognition, 24 (2): 183–184, doi:10.1016/0031-3203(91)90087-L, MR 1087740
  5. ^ a b Brönnimann, Hervé; Chan, Timothy M. (2006), "Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear time", Computational Geometry, 34 (2): 75–82, doi:10.1016/j.comgeo.2005.11.005, MR 2222883
  6. ^ Aloupis, Greg, A History of Linear-time Convex Hull Algorithms for Simple Polygons, McGill University, retrieved 2020-01-01
  7. ^ Graham, Ronald L.; Yao, F. Frances (1983), "Finding the convex hull of a simple polygon", Journal of Algorithms, 4 (4): 324–331, doi:10.1016/0196-6774(83)90013-5, MR 0729228
  8. ^ Lee, D. T. (1983), "On finding the convex hull of a simple polygon", International Journal of Computer and Information Sciences, 12 (2): 87–98, doi:10.1007/BF00993195, MR 0724699
  9. ^ Schäffer, Alejandro A.; Van Wyk, Christopher J. (1987), "Convex hulls of piecewise-smooth Jordan curves", Journal of Algorithms, 8 (1): 66–94, doi:10.1016/0196-6774(87)90028-9, MR 0875326
  10. ^ Melkman, Avraham A. (1987), "On-line construction of the convex hull of a simple polyline", Information Processing Letters, 25 (1): 11–12, doi:10.1016/0020-0190(87)90086-X, MR 0896397
  11. ^ Demaine, Erik D.; Gassend, Blaise; O'Rourke, Joseph; Toussaint, Godfried T. (2008), "All polygons flip finitely ... right?", Surveys on discrete and computational geometry, Contemporary Mathematics, vol. 453, Providence, Rhode Island: American Mathematical Society, pp. 231–255, doi:10.1090/conm/453/08801, MR 2405683
Retrieved from "https://en.wikipedia.org/w/index.php?title=Convex_hull_of_a_simple_polygon&oldid=1006581813"