CGAL users discussion list

[Mariette Yvinec <>]

Starting from the constrained triangulation of your polygons
you can appraoch a minimal convex subdivision
(I think at most twice the number of parts of the optimal)
by pulling out as much as you can
of non constrained triangulation edges
without forming angles greater than 90 degrees.

Le 18/01/12 09:27, Sebastien Loriot (GeometryFactory) a écrit :

The input polygon should be simple and without holes.
In you case you might want to try to use a constrained (Delaunay)
triangulation (edges of your polygon are constraints).
The decomposition would be minimal at all but it will be convex.


See:
http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Triangulation_2/Chapter_main.html#Section_36.7

Sebastien.

Thomas Recouvreux wrote:

Hi,

I've have found some examples about partitionning a Polygon_2, but I didn't see functions for partitionning a Poly_2 with holes. Is there any function to do so or shall I decompose first my polygon with holes in polygons without holes and apply the partitionning function ?

An other question, I tried to use partition function on a polygon with tangente edges (see below), and the function return the whole polygon without partionning it, did I miss something ?

+---------------------------------------+
|                                       / |
|                                     /   |
|                        +----------+   |
|                         |           |    |
|                        +----------+   |
|                                         |
|                                         |
+---------------------------------------+
polygon.push_back(Point_2(0, 0));
polygon.push_back(Point_2(10, 0));
polygon.push_back(Point_2(6, 2));
polygon.push_back(Point_2(2, 2));
polygon.push_back(Point_2(2, 6));
polygon.push_back(Point_2(6, 6));
polygon.push_back(Point_2(6, 2));
polygon.push_back(Point_2(10, 0));
polygon.push_back(Point_2(10, 10));
polygon.push_back(Point_2(0,10));


Best
Thomas

-- 
Mariette Yvinec
Geometrica project team
INRIA  Sophia-Antipolis