# How to split compound polygons into convex polygons?

Is it possible to split non-convex polygons into convex plygons with Mathematica 9?

For example:

pts={{-5, 29.6537}, {-4, 16.3031}, {-3, 13.8614}, {-2, 9.22332}, {-1,
6.89646}, {0, 6.76047}, {1, 9.20436}, {2, 6.65919}, {3,
18.2084}, {4, 18.9102}, {5, 31.6521}}


-
You may Triangulate it! – PlatoManiac May 28 '13 at 10:59
This is not unique. Have you tried dividng it into triangles? – Ali May 28 '13 at 11:00
As noted, even the triangulation isn't unique... ;) – J. M. May 28 '13 at 11:01
See my answer to the MO question, "Partitioning a polygon into convex parts." There is a relatively easy algorithm (Hertel-Mehlhorn) superior to triangulation for most shapes. – Joseph O'Rourke May 28 '13 at 12:23
dma.fi.upm.es/docencia/trabajosfindecarrera/programas/… is a very nice exposition of both a triangulation algorithm and the Hertel-Mehlhorn algorithm. – David Speyer Jun 4 '13 at 15:07

In V9, hidden in GraphicsMesh is the PolygonTriangulate function...

pts = {{-5, 29.6537}, {-4, 16.3031}, {-3, 13.8614}, {-2, 9.22332}, {-1, 6.89646},
{0, 6.76047}, {1, 9.20436}, {2, 6.65919}, {3, 18.2084}, {4, 18.9102}, {5, 31.6521}};

Graphics[
GraphicsComplex[
pts,
{EdgeForm[{Thick, Gray}],
LightRed,
Polygon@GraphicsMeshPolygonTriangulate[pts]}
], Axes -> True, AspectRatio -> 1/GoldenRatio]


V10 update

While the OP specifically asks about V9, it is worth pointing out a more current solution, DiscretizeRegion. It has a tendency to add points, which are not strictly necessary. MaxCellMeasure can control the size of the triangles to some extent.

Show[
DiscretizeRegion[
Polygon[pts], MaxCellMeasure -> {"Area" -> Infinity}],
Axes -> True, AspectRatio -> 1/GoldenRatio]


One can get the same result using TriangulateMesh and BoundaryDiscretizeRegion.

-