Skip to Content.
Sympa Menu

cgal-discuss - [cgal-discuss] Re: Constraint Delaunay Triangulation: How to triangulate a set of polygons

Subject: CGAL users discussion list

List archive

[cgal-discuss] Re: Constraint Delaunay Triangulation: How to triangulate a set of polygons


Chronological Thread 
  • From: Graviton <>
  • To:
  • Subject: [cgal-discuss] Re: Constraint Delaunay Triangulation: How to triangulate a set of polygons
  • Date: Wed, 7 Dec 2011 00:06:53 -0800 (PST)
Thanks! Sebastien, I got your point. 

On Wed, Dec 7, 2011 at 3:50 PM, Sebastien Loriot (GeometryFactory) [via cgal-discuss] <[hidden email]> wrote:
If an edge is shared by two polygons, the endpoints are vertices of both
polygons.

Upon insertion of a point in the CDT, you can get the corresponding
vertex handle, and for an edge a pair of vertex handle. If you sort
the pair, then you have a unique id per edge. You can use a std::set for
example or a std::map to track shared edges.

Sebastien.


Graviton wrote:

> * then you need to modify a little bit the code  and increase the
> nesting level only if the constrained edge is not  shared by two polygons. *
>
> This is something I don't quite understand, when we are doing the
> mark_domains, we don't yet know whether a constrained edge is shared by
> two mesh elements (AKA face) or not ( this is the whole purpose of
> mark_domains). If this were the case how can we know a constrained edge
> is shared by one or two polygons?  
>
> Do I miss something?
>
> On Tue, Dec 6, 2011 at 5:45 PM, Sebastien Loriot (GeometryFactory) [via
> cgal-discuss] <[hidden email]
> </user/SendEmail.jtp?type=node&node=4164287&i=0>> wrote:

>
>     oops! I thought this was the mesh thread.
>     The code given is working if polygons are not intersecting.
>     If they can share an edge, then you need to modify a little bit the
>     code
>     and increase the nesting level only if the constrained edge is not
>     shared by two polygons.
>
>     here:
>     mark_domains(cdt, n, e.first->info().nesting_level+1, border);
>
>     do +1 only if e is not shared by two polygons.
>
>     Sebastien.
>
>
>     Graviton wrote:
>
>      > Hi Sebastien, thanks for your pointer.
>      >
>      > But I still don't quite understand the phase  "you don't need the
>      > nesting level which is invalid
>      > since polygons can share edges in your setting", does that mean
>     that now
>      > I don't need the nesting level ( i.e, a face is considered "in
>     domain"
>      > if nesting level>=1)? Any idea how to modify the above code to
>     make sure
>      > it works for the above case and the case when there is a hole
>     inside the
>      > polygon set?
>      >
>      > On Tue, Dec 6, 2011 at 4:43 PM, Sebastien Loriot
>     (GeometryFactory) [via
>      > cgal-discuss] <[hidden email]
>      > </user/SendEmail.jtp?type=node&node=4164051&i=0>> wrote:
>
>      >
>      >     I did not mean to use the code directly. I meant to use only the
>      >     connected component exploration part which is the same in the
>     example
>      >     and in your case (you don't need the nesting level which is
>     invalid
>      >     since polygons can share edges in your setting).
>      >
>      >
>      >     Sebastien.
>      >
>      >     Graviton wrote:
>      >
>      >      > Hi Sebastian, I tried your algorithm, and it works for a
>     lot of
>      >     cases, but
>      >      > there are cases that it couldn't work. You can try the
>     following
>      >     code:
>      >      >
>      >      >
>      >      >
>      >      > #include
>     <CGAL/Exact_predicates_inexact_constructions_kernel.h>
>      >      > #include <CGAL/Constrained_Delaunay_triangulation_2.h>
>      >      > #include <CGAL/Triangulation_face_base_with_info_2.h>
>      >      > #include <CGAL/Polygon_2.h>
>      >      > #include <boost/next_prior.hpp>
>      >      > #include <iostream>
>      >      >
>      >      > struct FaceInfo2
>      >      > {
>      >      >   FaceInfo2(){}
>      >      >   int nesting_level;
>      >      >
>      >      >   bool in_domain(){
>      >      >     return nesting_level%2 == 1;
>      >      >   }
>      >      > };
>      >      >
>      >      >
>      >      > typedef
>     CGAL::Exact_predicates_inexact_constructions_kernel       K;
>      >      > typedef CGAL::Triangulation_vertex_base_2<K>              
>          
>      >      Vb;
>      >      > typedef
>     CGAL::Triangulation_face_base_with_info_2<FaceInfo2,K>  
>      >      Fbb;
>      >      > typedef CGAL::Constrained_triangulation_face_base_2<K,Fbb>
>          
>      >      Fb;
>      >      > typedef CGAL::Triangulation_data_structure_2<Vb,Fb>      
>            
>      >     TDS;
>      >      > typedef CGAL::Exact_predicates_tag                        
>          
>      >      Itag;
>      >      > typedef CGAL::Constrained_Delaunay_triangulation_2<K, TDS,
>     Itag>
>      >      CDT;
>      >      > typedef CDT::Point                                        
>          
>      >      Point;
>      >      > typedef CGAL::Polygon_2<K>                                
>          
>      >        Polygon;
>      >      >
>      >      > void
>      >      > mark_domains(CDT& ct,
>      >      >              CDT::Face_handle start,
>      >      >              int index,
>      >      >              std::list<CDT::Edge>& border )
>      >      > {
>      >      >   if(start->info().nesting_level != -1){
>      >      >     return;
>      >      >   }
>      >      >   std::list<CDT::Face_handle> queue;
>      >      >   queue.push_back(start);
>      >      >
>      >      >   while(! queue.empty()){
>      >      >     CDT::Face_handle fh = queue.front();
>      >      >     queue.pop_front();
>      >      >     if(fh->info().nesting_level == -1){
>      >      >       fh->info().nesting_level = index;
>      >      >       for(int i = 0; i < 3; i++){
>      >      >         CDT::Edge e(fh,i);
>      >      >         CDT::Face_handle n = fh->neighbor(i);
>      >      >         if(n->info().nesting_level == -1){
>      >      >           if(ct.is_constrained(e)) border.push_back(e);
>      >      >           else queue.push_back(n);
>      >      >         }
>      >      >       }
>      >      >     }
>      >      >   }
>      >      > }
>      >      >
>      >      > //explore set of facets connected with non constrained edges,
>      >      > //and attribute to each such set a nesting level.
>      >      > //We start from facets incident to the infinite vertex,
>     with a
>      >     nesting
>      >      > //level of 0. Then we recursively consider the non-explored
>      >     facets incident
>      >      > //to constrained edges bounding the former set and
>     increase the
>      >     nesting
>      >      > level by 1.
>      >      > //Facets in the domain are those with an odd nesting level.
>      >      > void
>      >      > mark_domains(CDT& cdt)
>      >      > {
>      >      >   for(CDT::All_faces_iterator it = cdt.all_faces_begin();
>     it !=
>      >      > cdt.all_faces_end(); ++it){
>      >      >     it->info().nesting_level = -1;
>      >      >   }
>      >      >
>      >      >   int index = 0;
>      >      >   std::list<CDT::Edge> border;
>      >      >   mark_domains(cdt, cdt.infinite_face(), index++, border);
>      >      >   while(! border.empty()){
>      >      >     CDT::Edge e = border.front();
>      >      >     border.pop_front();
>      >      >     CDT::Face_handle n = e.first->neighbor(e.second);
>      >      >     if(n->info().nesting_level == -1){
>      >      >       mark_domains(cdt, n,
>     e.first->info().nesting_level+1, border);
>      >      >     }
>      >      >   }
>      >      > }
>      >      >
>      >      > void insert_polygon(CDT& cdt,const Polygon& polygon){
>      >      >   if ( polygon.is_empty() ) return;
>      >      >   CDT::Vertex_handle
>      >      > v_prev=cdt.insert(*boost::prior(polygon.vertices_end()));
>      >      >   for (Polygon::Vertex_iterator vit=polygon.vertices_begin();
>      >      >                                
>     vit!=polygon.vertices_end();++vit)
>      >      >   {
>      >      >     CDT::Vertex_handle vh=cdt.insert(*vit);
>      >      >     cdt.insert_constraint(vh,v_prev);
>      >      >     v_prev=vh;
>      >      >   }  
>      >      > }
>      >      >
>      >      > int main( )
>      >      > {
>      >      >   //construct two non-intersecting nested polygons  
>      >      >   Polygon polygon1;
>      >      >   polygon1.push_back(Point(254250, 173750));
>      >      >   polygon1.push_back(Point(257250, 139250));
>      >      >   polygon1.push_back(Point(259750, 133750));
>      >      >   polygon1.push_back(Point(261250, 136250));
>      >      >   polygon1.push_back(Point(257750, 176250));
>      >      >
>      >      >   Polygon polygon2;
>      >      >   polygon2.push_back(Point(254750, 122750));
>      >      >   polygon2.push_back(Point(312750, 93750));
>      >      >   polygon2.push_back(Point(317750, 104750));
>      >      >   polygon2.push_back(Point(303750, 111750));
>      >      >   polygon2.push_back(Point(259750, 133750));
>      >      >
>      >      >
>      >      >     Polygon polygon3;
>      >      >   polygon3.push_back(Point(261250, 136250));
>      >      >   polygon3.push_back(Point(259750, 133750));
>      >      >   polygon3.push_back(Point(303750, 111750));
>      >      >   polygon3.push_back(Point(315750, 145750));
>      >      >   polygon3.push_back(Point(257750, 176250));
>      >      >
>      >      >
>      >      >   Polygon polygon4;
>      >      >   polygon4.push_back(Point(303750, 111750));
>      >      >   polygon4.push_back(Point(317750, 104750));
>      >      >   polygon4.push_back(Point(321250, 102750));
>      >      >   polygon4.push_back(Point(327250, 105250));
>      >      >   polygon4.push_back(Point(338750, 137250));
>      >      > polygon4.push_back(Point(315750, 145750));
>      >      >
>      >      >   Polygon polygon5;
>      >      >   polygon5.push_back(Point(251250, 179750));
>      >      >   polygon5.push_back(Point(257750, 176250));
>      >      >   polygon5.push_back(Point(315750, 145750));
>      >      >   polygon5.push_back(Point(329750, 183750));
>      >      >   polygon5.push_back(Point(272250, 223750));
>      >      >
>      >      >
>      >      >
>      >      >   //Insert the polyons into a constrained triangulation
>      >      >   CDT cdt;
>      >      >   insert_polygon(cdt,polygon1);
>      >      >  insert_polygon(cdt,polygon2);
>      >      >    insert_polygon(cdt,polygon3);
>      >      >  insert_polygon(cdt,polygon4);
>      >      >    insert_polygon(cdt,polygon5);
>      >      >  //insert_polygon(cdt,polygon2);
>      >      >  
>      >      >   //Mark facets that are inside the domain bounded by the
>     polygon
>      >      >   mark_domains(cdt);
>      >      >  
>      >      >   int count=0;
>      >      >   for (CDT::Finite_faces_iterator
>     fit=cdt.finite_faces_begin();
>      >      >                                  
>     fit!=cdt.finite_faces_end();++fit)
>      >      >   {
>      >      >     if ( fit->info().in_domain() ) ++count;
>      >      >   }
>      >      >  
>      >      >   std::cout << "There are " << count << " facets in the
>     domain." <<
>      >      > std::endl;   // should be 16, but instead it is 13 only
>      >      >
>      >      >   return 0;
>      >      > }
>      >      >
>      >      >
>      >      >
>      >      > I also attach a screenshot of the polygon set for easier
>     visual
>      >     checking.
>      >      >
>     http://cgal-discuss.949826.n4.nabble.com/file/n4163918/image001.png 
>      >      >
>      >      > --
>      >      > View this message in context:
>      >    
>     http://cgal-discuss.949826.n4.nabble.com/Constraint-Delaunay-Triangulation-How-to-triangulate-a-set-of-polygons-tp4122741p4163918.html
>      >

>
>      >      > Sent from the cgal-discuss mailing list archive at
>     Nabble.com.
>      >      >
>      >
>      >
>      >     --
>      >     You are currently subscribed to cgal-discuss.
>      >     To unsubscribe or access the archives, go to
>      >     https://lists-sop.inria.fr/wws/info/cgal-discuss
>      >
>      >
>      >
>      >    
>     ------------------------------------------------------------------------
>
>      >     If you reply to this email, your message will be added to the
>      >     discussion below:
>      >    
>     http://cgal-discuss.949826.n4.nabble.com/Constraint-Delaunay-Triangulation-How-to-triangulate-a-set-of-polygons-tp4122741p4163927.html
>      >
>      >     To unsubscribe from Constraint Delaunay Triangulation: How to
>      >     triangulate a set of polygons, click here.
>      >     NAML
>      >    
>     <http://cgal-discuss.949826.n4.nabble.com/template/NamlServlet.jtp?macro=macro_viewer&id=instant_html%21nabble%3Aemail.naml&base=nabble.naml.namespaces.BasicNamespace-nabble.view.web.template.NabbleNamespace-nabble.view.web.template.InstantMailNamespace&breadcrumbs=instant+emails%21nabble%3Aemail.naml-instant_emails%21nabble%3Aemail.naml-send_instant_email%21nabble%3Aemail.naml
>     <http://cgal-discuss.949826.n4.nabble.com/template/NamlServlet.jtp?macro=macro_viewer&id=instant_html%21nabble%3Aemail.naml&base=nabble.naml.namespaces.BasicNamespace-nabble.view.web.template.NabbleNamespace-nabble.view.web.template.InstantMailNamespace&breadcrumbs=instant+emails%21nabble%3Aemail.naml-instant_emails%21nabble%3Aemail.naml-send_instant_email%21nabble%3Aemail.naml>>

>
>      >
>      >
>      >
>      >
>      >
>     ------------------------------------------------------------------------
>
>      > View this message in context: Re: Constraint Delaunay
>     Triangulation: How
>      > to triangulate a set of polygons
>      >
>     <http://cgal-discuss.949826.n4.nabble.com/Constraint-Delaunay-Triangulation-How-to-triangulate-a-set-of-polygons-tp4122741p4164051.html>
>
>      > Sent from the cgal-discuss mailing list archive
>      > <http://cgal-discuss.949826.n4.nabble.com/> at Nabble.com.
>
>
>     --
>     You are currently subscribed to cgal-discuss.
>     To unsubscribe or access the archives, go to
>     https://lists-sop.inria.fr/wws/info/cgal-discuss
>
>
>
>     ------------------------------------------------------------------------
>     If you reply to this email, your message will be added to the
>     discussion below:
>     http://cgal-discuss.949826.n4.nabble.com/Constraint-Delaunay-Triangulation-How-to-triangulate-a-set-of-polygons-tp4122741p4164067.html
>
>     To unsubscribe from Constraint Delaunay Triangulation: How to
>     triangulate a set of polygons, click here.
>     NAML
>     <http://cgal-discuss.949826.n4.nabble.com/template/NamlServlet.jtp?macro=macro_viewer&id=instant_html%21nabble%3Aemail.naml&base=nabble.naml.namespaces.BasicNamespace-nabble.view.web.template.NabbleNamespace-nabble.view.web.template.InstantMailNamespace&breadcrumbs=instant+emails%21nabble%3Aemail.naml-instant_emails%21nabble%3Aemail.naml-send_instant_email%21nabble%3Aemail.naml>
>
>
>
>
> ------------------------------------------------------------------------
> View this message in context: Re: Constraint Delaunay Triangulation: How
> to triangulate a set of polygons
> <http://cgal-discuss.949826.n4.nabble.com/Constraint-Delaunay-Triangulation-How-to-triangulate-a-set-of-polygons-tp4122741p4164287.html>
> Sent from the cgal-discuss mailing list archive
> <http://cgal-discuss.949826.n4.nabble.com/> at Nabble.com.


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



To unsubscribe from Constraint Delaunay Triangulation: How to triangulate a set of polygons, click here.
NAML


View this message in context: Re: Constraint Delaunay Triangulation: How to triangulate a set of polygons
Sent from the cgal-discuss mailing list archive at Nabble.com.

Archive powered by MHonArc 2.6.16.

Top of Page