CGAL users discussion list

["Sebastien Loriot (GeometryFactory)" <>]

On 01/18/2012 11:09 AM, Thomas Recouvreux wrote:
> 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.
Which is not a problem as you can simply do not consider these 
triangles. See this thread for example (the code works for non 
intersecting polygons but can simply be extended).
https://lists-sop.inria.fr/sympa/arc/cgal-discuss/2011-11/msg00150.html

> 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 ?
No idea but a link is provided to a paper on the page you refer to.
I guess it's a union of adjacent triangles to form maximal convex set.

Sebastien.

> 2012/1/18 Sebastien Loriot (GeometryFactory) 
> <
> <mailto:>>
>
>     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
>     
> <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
>     <https://lists-sop.inria.fr/wws/info/cgal-discuss>