5
$\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

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ You may Triangulate it! $\endgroup$
    – PlatoManiac
    Commented May 28, 2013 at 10:59
  • $\begingroup$ This is not unique. Have you tried dividng it into triangles? $\endgroup$
    – Ali
    Commented May 28, 2013 at 11:00
  • $\begingroup$ As noted, even the triangulation isn't unique... ;) $\endgroup$
    – J. M.'s missing motivation ♦
    Commented May 28, 2013 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
    Commented May 28, 2013 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
    Commented Jun 4, 2013 at 15:07

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

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.