20
$\begingroup$

I'm looking for an algorithm to partition any simple closed polygon into convex sub-polygons--preferably as few as possible.

I know almost nothing about this subject, so I've been searching on Google Scholar and various computational geometry books, and I see a variety of different methods, some of which are extremely complicated (and meant to apply to non-simple polygons). I'm hoping there's a standard algorithm for this, with a clear explanation, but I don't know where to find it.

Can anyone point me to a source with a clear explanation of how to do this?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Triangulation is well-researched topic. For introduction see book by de Berg, Cheong, Kreveld Overmars. $\endgroup$
    – Boris Bukh
    Mar 31, 2011 at 17:30

2 Answers 2

Reset to default
40
$\begingroup$

Chapter 2, Section 2.5 of Computational Geometry in C (1998), accessible via Google books, is on this topic: "Convex Partitioning." There are several choices here: (1) Triangulation, which always results in $n-2$ pieces for a polygon of $n$ vertices; (2) the Hertel-Mehlhorn algorithm, which is never worse than $2r+1$ pieces, where $r$ is the number of reflex vertices (which means it is never worse than four times the minimum); or (3) Chazelle's complex cubic algorithm that finds the minimum partition. The H-M algorithm is a happy medium in terms of both implementation difficulty (easy) and quality of result (not bad).

Convex partition

There is a 4th choice if you insist that the corners of all your convex pieces are subsets of the polygon's vertices (unlike the example above). Then Greene's (now) cubic dynamic programming algorithm achieves the minimum number of pieces.

Both Greene's algorithm and the Hertel-Mehlhorn algorithm are implemented in CGAL; see the "2D Polygon Partitioning" section of the CGAL manual.

Improve this answer
$\endgroup$
6
  • $\begingroup$ What is the minimum number of pieces needed for partitioning/covering an n-gon to convex pieces? $\endgroup$
    – domotorp
    Aug 22, 2020 at 19:50
  • 1
    $\begingroup$ Keil, Mark, and Jack Snoeyink. "On the time bound for convex decomposition of simple polygons." International Journal of Computational Geometry & Applications 12, no. 03 (2002): 181-192. Abstract: "We show that a decomposition of a simple polygon having $n$ vertices, $r$of which are reflex, into a minimum number of convex regions without the addition of Steiner vertices can be computed in $O(n + r^2\min{r^2, n})$ time and space." $\endgroup$
    – Joseph O'Rourke
    Aug 22, 2020 at 21:12
  • $\begingroup$ I've looked at many of these papers, but all of them seems to be about the computational complexity of the optimum value for a given input. I'm just looking for a simple expression, like n/3 for the art gallery problem. $\endgroup$
    – domotorp
    Aug 22, 2020 at 21:43
  • 1
    $\begingroup$ @domotorp: Sorry for the delay. The best possible is $\lceil r/2 \rceil + 1$, where $r$ is the number of reflex vertices, because each reflex vertex must be resolved, and at most two reflex vertices can be resolved by a single partition segment. The min might be as high as $r+1$ depending on alignment of the reflexivities. $\endgroup$
    – Joseph O'Rourke
    Aug 23, 2020 at 17:34
  • 1
    $\begingroup$ Oh, I see, so the answer to my question is n-2! On one hand, this is an upper bound given by any triangulation. On the other, if an n-gon has a concave arc of n-2 consecutive segments, i.e., with n-3 reflex vertices, then obviously n-2 pieces are needed. Thanks! $\endgroup$
    – domotorp
    Aug 23, 2020 at 18:39
3
$\begingroup$

I don't know, whether this is an already known algorithm and I also don't know how optimal the resulting partitioning will be, but its description and implementation are simple:

  • identify the set of inflex points, i.e. where a right-turn is made when going around the polygon counter clockwise

  • calculate the nested convex hull of the inflex point set

  • cut the polygon along the edges of the nested convex hull, that are inside the polygon

Improve this answer
$\endgroup$
4
  • $\begingroup$ What is the nested convex hull? Does your algorithm handle correctly a polygon made of three concave parts (with only three non-inflex points)? $\endgroup$
    – Benoît Kloeckner
    Dec 14, 2014 at 16:54
  • $\begingroup$ @BenoîtKloeckner the nested convex hull is constructed by iteratively calculating the convex hull, then removing the points of the convex hull and then to calculate the convex hull of the remaining point set. So this is a set of nested convex polygons. The nested convex hull is also known as the iterated convex hull. $\endgroup$
    – Manfred Weis
    Dec 14, 2014 at 18:16
  • $\begingroup$ If I understand well, at each step you remove from the finite set of the previous step some of the points (those that are extremal in the convex hull, I guess). $\endgroup$
    – Benoît Kloeckner
    Dec 14, 2014 at 19:16
  • 4
    $\begingroup$ This is called convex hull onion peeling. Too bad I cannot include an image in a comment, but: image. $\endgroup$
    – Joseph O'Rourke
    Dec 14, 2014 at 22:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.