4
$\begingroup$

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}}

enter image description here

$\endgroup$
  • 2
    $\begingroup$ You may Triangulate it! $\endgroup$ – PlatoManiac May 28 '13 at 10:59
  • $\begingroup$ This is not unique. Have you tried dividng it into triangles? $\endgroup$ – Ali May 28 '13 at 11:00
  • $\begingroup$ As noted, even the triangulation isn't unique... ;) $\endgroup$ – J. M.'s technical difficulties May 28 '13 at 11:01
  • 4
    $\begingroup$ 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. $\endgroup$ – Joseph O'Rourke May 28 '13 at 12:23
  • 1
    $\begingroup$ dma.fi.upm.es/docencia/trabajosfindecarrera/programas/… is a very nice exposition of both a triangulation algorithm and the Hertel-Mehlhorn algorithm. $\endgroup$ – David E Speyer Jun 4 '13 at 15:07
6
$\begingroup$

In V9, hidden in Graphics`Mesh` 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@Graphics`Mesh`PolygonTriangulate[pts]}
  ], Axes -> True, AspectRatio -> 1/GoldenRatio]

enter image description here


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]

Mathematica graphics

One can get the same result using TriangulateMesh and BoundaryDiscretizeRegion.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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