CGAL users discussion list

[Graviton <>]

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]> 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

---

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.