CGAL users discussion list

[Thomas Recouvreux <>]

Hi,

Thanks for the answer.

If I have well understand the delaunay triangulation there are a big problem : some edges will be constructed inside the holes.

Secondly the decomposition is not optimal. I saw on this link http://forums.create.msdn.com/forums/t/50204.aspx someone speaks about CGAL, he merges polygons to have complex polygon with holes (binary difference operation I think) then he uses mp5 algorithm to make an optimal partition, the result is exactly what I would like to get (a navigation graph). Do you know what mp5 algorithm refers to ?

2012/1/18 Sebastien Loriot (GeometryFactory) <>

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

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss