← Back to branch summary

~ubuntu-branches/debian/stretch/cgal/stretch

« back to all changes in this revision

Viewing changes to include/CGAL/Boolean_set_operations_2/Gps_on_surface_base_2_impl.h

  • Committer: Package Import Robot
  • Author(s): Joachim Reichel
  • Date: 2014-04-05 10:56:43 UTC
  • mfrom: (1.2.4)
  • Revision ID: package-import@ubuntu.com-20140405105643-jgnrpu2thtx23zfs
Tags: 4.4-1
* New upstream release.
* Remove patches do-not-link-example-with-qt4-support-library.patch and
  fix_jet_fitting_3.patch (applied upstream).

Show diffs side-by-side

added added

removed removed

Lines of Context:
include/CGAL/Boolean_set_operations_2/Gps_on_surface_base_2_impl.h
13
13
// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
14
14
//
15
15
// $URL$
16
 
// $Id$ 
17
 
// 
 
16
// $Id$
 
17
//
18
18
//
19
19
// Author(s)     : Baruch Zukerman <baruchzu@post.tau.ac.il>
20
20
//                 Efi Fogel <efif@post.tau.ac.il>
21
21
//                 Ophir Setter    <ophir.setter@cs.tau.ac.il>
22
 
//                 Guy Zucker <guyzucke@post.tau.ac.il> 
 
22
//                 Guy Zucker <guyzucke@post.tau.ac.il>
23
23
 
24
24
#ifndef CGAL_GPS_ON_SURFACE_BASE_2_IMPL_H
25
25
#define CGAL_GPS_ON_SURFACE_BASE_2_IMPL_H
26
26
 
27
27
#include <CGAL/iterator.h>
28
28
#include <CGAL/function_objects.h>
29
 
#include <CGAL/circulator.h> 
 
29
#include <CGAL/circulator.h>
30
30
#include <CGAL/Boolean_set_operations_2/Gps_bfs_scanner.h>
31
31
#include <CGAL/Arr_accessor.h>
32
32
 
38
38
construct_polygon(Ccb_halfedge_const_circulator ccb, Polygon_2 & pgn,
39
39
                  Traits_ * tr)
40
40
{
41
 
  typedef CGAL::Ccb_curve_iterator<Arrangement_on_surface_2>    
 
41
  typedef CGAL::Ccb_curve_iterator<Arrangement_on_surface_2>
42
42
    Ccb_curve_iterator;
43
43
  Ccb_curve_iterator begin(ccb, false);
44
44
  Ccb_curve_iterator end(ccb, true);
52
52
// arrangement.
53
53
// This scanner is not the same as the Gps_bfs_scanner. In this file, the
54
54
// Gps_bfs_scanner is used with Init_faces_visitor to init the faces of the
55
 
// representing arrangement. 
 
55
// representing arrangement.
56
56
// It seems that Gps_bfs_scanner is used for a regular bfs scan on the faces
57
57
// of the arrangements, with comparison to Arr_bfs_scanner that cares about
58
58
// inner ccbs and outer ccbs (it treats them differently).
66
66
  typedef typename Arrangement::Topology_traits         Gps_top_traits;
67
67
  typedef typename Gps_traits::Polygon_2                Polygon_2;
68
68
  typedef typename Gps_traits::Polygon_with_holes_2     Polygon_with_holes_2;
69
 
  typedef typename Arrangement::Ccb_halfedge_const_circulator 
 
69
  typedef typename Arrangement::Ccb_halfedge_const_circulator
70
70
    Ccb_halfedge_const_circulator;
71
71
  typedef typename Arrangement::Face_const_iterator     Face_const_iterator;
72
72
  typedef typename Arrangement::Halfedge_const_iterator Halfedge_const_iterator;
73
 
  typedef typename Arrangement::Outer_ccb_const_iterator     
 
73
  typedef typename Arrangement::Outer_ccb_const_iterator
74
74
    Outer_ccb_const_iterator;
75
 
  typedef typename Arrangement::Inner_ccb_const_iterator     
 
75
  typedef typename Arrangement::Inner_ccb_const_iterator
76
76
    Inner_ccb_const_iterator;
77
77
 
78
78
 
88
88
  /*! Constructor */
89
89
  Arr_bfs_scanner(Gps_traits* tr, OutputIterator oi) : m_traits(tr), m_oi(oi)
90
90
  {}
91
 
                             
 
91
 
92
92
 
93
93
  void scan(Arrangement& arr)
94
94
  {
99
99
        continue;
100
100
      if (ubf->visited())
101
101
        continue;
102
 
      
 
102
 
103
103
      Inner_ccb_const_iterator  holes_it;
104
104
      if (!ubf->contained())
105
105
      {
114
114
      {
115
115
        // ubf is contained -> unbounded polygon !!
116
116
        scan_contained_ubf(ubf);
117
 
        
 
117
 
118
118
      }
119
 
      
 
119
 
120
120
      while(!m_holes_q.empty())
121
121
      {
122
122
        Face_const_iterator top_f = m_holes_q.front();
127
127
        {
128
128
          scan_ccb(*holes_it);
129
129
        }
130
 
        
 
130
 
131
131
        //scan_uncontained_face(top_f->outer_ccb());
132
132
      }
133
133
    }
146
146
 
147
147
  void scan_ccb(Ccb_halfedge_const_circulator ccb)
148
148
  {
149
 
         
 
149
 
150
150
    Polygon_2 pgn_boundary;
151
151
    Gps_on_surface_base_2<Gps_traits, Gps_top_traits>::
152
152
      construct_polygon(ccb, pgn_boundary, m_traits);
160
160
      ++ccb;
161
161
    }
162
162
    while(ccb != ccb_end);
163
 
    Polygon_with_holes_2 pgn = 
 
163
    Polygon_with_holes_2 pgn =
164
164
      m_traits->construct_polygon_with_holes_2_object()(pgn_boundary,
165
165
                                                        m_pgn_holes.begin(),
166
166
                                                        m_pgn_holes.end());
178
178
    // ubf is contained -> unbounded polygon !!
179
179
    all_incident_faces(ubf);
180
180
    Polygon_2 boundary;
181
 
    Polygon_with_holes_2 pgn = 
 
181
    Polygon_with_holes_2 pgn =
182
182
      m_traits->construct_polygon_with_holes_2_object()(boundary,
183
183
                                                        m_pgn_holes.begin(),
184
184
                                                        m_pgn_holes.end());
206
206
          Gps_on_surface_base_2<Gps_traits, Gps_top_traits>::
207
207
            construct_polygon(*oci, m_pgn_holes.back(), m_traits);
208
208
        }
209
 
        
 
209
 
210
210
        m_holes_q.push(f);
211
211
      }
212
212
 
213
 
    
 
213
 
214
214
      for (Outer_ccb_const_iterator oci = f->outer_ccbs_begin();
215
215
           oci != f->outer_ccbs_end(); ++oci)
216
216
      {
217
217
        Ccb_halfedge_const_circulator ccb_end = *oci;
218
218
        Ccb_halfedge_const_circulator ccb_circ = ccb_end;
219
219
        do
220
 
        { 
 
220
        {
221
221
          //get the current halfedge on the face boundary
222
222
          Halfedge_const_iterator he  = ccb_circ;
223
223
          Face_const_iterator new_f = he->twin()->face();
241
241
        if (is_single_face(ccb_of_hole))
242
242
        {
243
243
          CGAL_assertion(!he->twin()->face()->contained());
244
 
         
 
244
 
245
245
          m_pgn_holes.push_back(Polygon_2());
246
246
          Gps_on_surface_base_2<Gps_traits, Gps_top_traits>::
247
247
            construct_polygon(he->twin()->face()->outer_ccb(),
271
271
    Halfedge_const_iterator he = ccb;
272
272
    Face_const_iterator curr_f = he->twin()->face();
273
273
    do
274
 
    { 
 
274
    {
275
275
      //get the current halfedge on the face boundary
276
276
      Halfedge_const_iterator he  = ccb_circ;
277
277
      if (he->twin()->face() != curr_f)
291
291
{
292
292
  typedef typename Arrangement::Face_iterator             Face_iterator;
293
293
  typedef typename Arrangement::Halfedge_iterator         Halfedge_iterator;
294
 
 
 
294
 
295
295
public:
296
296
 
297
297
  //! discovered_face
298
 
/*! discovered_face is called by Gps_bfs_scanner when it reveals a new face 
 
298
/*! discovered_face is called by Gps_bfs_scanner when it reveals a new face
299
299
    during a BFS scan. It is important to say that I have a strong suspition
300
 
    that this place is the reason why discovered_face was once called 
 
300
    that this place is the reason why discovered_face was once called
301
301
    "flip_face" (WTF?)
302
302
  \param old_f The face that was already revealed
303
303
  \param new_f The face that we have just now revealed
304
304
*/
305
 
  void discovered_face(Face_iterator old_f, 
306
 
                       Face_iterator new_f, 
 
305
  void discovered_face(Face_iterator old_f,
 
306
                       Face_iterator new_f,
307
307
                       Halfedge_iterator /*he*/)
308
308
  {
309
309
    new_f->set_contained(!old_f->contained());
311
311
};
312
312
 
313
313
//! _insert
314
 
/*! The function inserts a polygon into an arrangement, assuming that the 
 
314
/*! The function inserts a polygon into an arrangement, assuming that the
315
315
    polygon is contained in one face of the arrangement.
316
 
  \param pgn The polygon to be inserted to the arrangement. pgn must be 
 
316
  \param pgn The polygon to be inserted to the arrangement. pgn must be
317
317
             completely disjoint from the arrangement
318
318
  \param arr The arrangement to insert the polygon to.
319
319
*/
339
339
    m_traits_adaptor.parameter_space_in_x_2_object()(*curr, ARR_MIN_END);
340
340
  const Arr_parameter_space  ps_y =
341
341
    m_traits_adaptor.parameter_space_in_y_2_object()(*curr, ARR_MIN_END);
342
 
  
 
342
 
343
343
  Object obj_f;
344
344
  if ((ps_x == ARR_INTERIOR) && (ps_y == ARR_INTERIOR))
345
345
  {
357
357
  CGAL_assertion(CGAL::assign(const_f, obj_f) && !const_f->contained());
358
358
  CGAL::assign(const_f, obj_f);
359
359
  Face_iterator f = arr.non_const_handle(const_f);
360
 
  
361
 
  Halfedge_handle first_he = 
 
360
 
 
361
  Halfedge_handle first_he =
362
362
    arr.insert_in_face_interior(*curr, f);
363
363
  //first_he is directed from left to right (see insert_in_face_interior)
364
 
  
 
364
 
365
365
  Halfedge_handle curr_he;
366
366
  if (cmp_ends(*curr) == CGAL::SMALLER)
367
367
  {
381
381
  if (temp == end) // a polygon with circular arcs may have only
382
382
                  // two edges (full circle for example)
383
383
  {
384
 
    /*Halfedge_handle he = 
 
384
    /*Halfedge_handle he =
385
385
      arr.insert_at_vertices(*temp, curr_he, first_he);*/
386
386
    bool new_face_created = false;
387
387
    bool dummy_swapped_predecessors = false;
392
392
                                                         dummy_swapped_predecessors);
393
393
    // TODO EBEB 2012-08-06 do we have to care if order has been swapped,
394
394
    // or do we have to disallow swapping?
395
 
    
396
 
    CGAL_assertion(new_face_created); 
 
395
 
 
396
    CGAL_assertion(new_face_created);
397
397
    CGAL_assertion((he->face() != he->twin()->face()));
398
 
    
 
398
 
399
399
    he->face()->set_contained(true);
400
400
    return;
401
401
  }
420
420
    arr.insert_at_vertices(last_cv, curr_he, first_he); */
421
421
  bool new_face_created = false;
422
422
  bool dummy_swapped_predecessors = false;
423
 
  Halfedge_handle last_he = 
 
423
  Halfedge_handle last_he =
424
424
    accessor.insert_at_vertices_ex (curr_he,
425
425
                                    last_cv, ( cmp_ends(last_cv) == CGAL::SMALLER ? ARR_LEFT_TO_RIGHT : ARR_RIGHT_TO_LEFT),
426
426
                                    first_he->next(),
429
429
  // TODO EBEB 2012-08-06 do we have to care if order has been swapped,
430
430
  // or do we have to disallow swapping?
431
431
 
432
 
  CGAL_assertion(new_face_created); 
 
432
  CGAL_assertion(new_face_created);
433
433
  CGAL_assertion((last_he->face() != last_he->twin()->face()));
434
 
  
 
434
 
435
435
  last_he->face()->set_contained(true);
436
436
}
437
437
 
442
442
  insert(PolygonIter p_begin, PolygonIter p_end)
443
443
{
444
444
  typename std::iterator_traits<PolygonIter>::value_type pgn;
445
 
  //check validity of all polygons    
 
445
  //check validity of all polygons
446
446
  for( ; p_begin != p_end; ++p_begin)
447
447
  {
448
448
    ValidationPolicy::is_valid(*p_begin, *m_traits);
462
462
  typedef Gps_bfs_scanner<Arrangement_on_surface_2, My_visitor>     Arr_bfs_scanner;
463
463
 
464
464
  XCurveList xcurve_list;
465
 
  
 
465
 
466
466
  for( ; p_begin != p_end; ++p_begin)
467
467
  {
468
468
    ValidationPolicy::is_valid(*p_begin, *m_traits);
500
500
  template<class PolygonIter>
501
501
  void Gps_on_surface_base_2<Traits_, TopTraits_, ValidationPolicy>::
502
502
  _insert(PolygonIter p_begin, PolygonIter p_end, Polygon_2 & /*pgn*/)
503
 
{  
 
503
{
504
504
  for(PolygonIter pitr = p_begin; pitr != p_end; ++pitr)
505
505
  {
506
506
    this->_insert(*pitr, *m_arr);
511
511
  template<class PolygonIter>
512
512
  void Gps_on_surface_base_2<Traits_, TopTraits_, ValidationPolicy>::
513
513
  _insert(PolygonIter p_begin, PolygonIter p_end, Polygon_with_holes_2 & /*pgn*/)
514
 
{  
 
514
{
515
515
  typedef std::list<X_monotone_curve_2>                  XCurveList;
516
516
  typedef Init_faces_visitor<Arrangement_on_surface_2>              My_visitor;
517
517
  typedef Gps_bfs_scanner<Arrangement_on_surface_2, My_visitor>     Arr_bfs_scanner;
521
521
  for( ; p_begin != p_end; ++p_begin)
522
522
  {
523
523
    // is_unbounded = (is_unbounded || p_begin->is_unbounded());
524
 
    is_unbounded = (is_unbounded || m_traits->construct_is_unbounded_object()(*p_begin));  
 
524
    is_unbounded = (is_unbounded || m_traits->construct_is_unbounded_object()(*p_begin));
525
525
    _construct_curves(*p_begin, std::back_inserter(xcurve_list));
526
526
 
527
527
  }
549
549
  void Gps_on_surface_base_2<Traits_, TopTraits_, ValidationPolicy>::
550
550
  _insert(const Polygon_with_holes_2 & pgn, Arrangement_on_surface_2 & arr)
551
551
{
552
 
 // inner function not exposed to user - no validation 
 
552
 // inner function not exposed to user - no validation
553
553
 // ValidationPolicy::is_valid(pgn, *m_traits);
554
554
 
555
555
  typedef std::list<X_monotone_curve_2>                  XCurveList;
561
561
  insert_non_intersecting_curves(arr, xcurve_list.begin(), xcurve_list.end());
562
562
 
563
563
  //if (pgn.is_unbounded())
564
 
  if (m_traits->construct_is_unbounded_object()(pgn))     
 
564
  if (m_traits->construct_is_unbounded_object()(pgn))
565
565
  {
566
 
    for (Face_iterator fit = arr.faces_begin(); 
 
566
    for (Face_iterator fit = arr.faces_begin();
567
567
         fit != arr.faces_end(); ++fit)
568
568
    {
569
569
      if (fit->number_of_outer_ccbs() == 0)
579
579
 
580
580
template <class Traits_, class TopTraits_, class ValidationPolicy>
581
581
  template <class OutputIterator>
582
 
  void 
 
582
  void
583
583
  Gps_on_surface_base_2<Traits_, TopTraits_, ValidationPolicy>::
584
584
  _construct_curves(const Polygon_2 & pgn, OutputIterator oi)
585
585
{
599
599
  {
600
600
    const Polygon_2& pgn_boundary = m_traits->construct_outer_boundary_object ()(pgn);
601
601
    std::pair<Curve_const_iterator,
602
 
      Curve_const_iterator> itr_pair = 
 
602
      Curve_const_iterator> itr_pair =
603
603
      m_traits->construct_curves_2_object()(pgn_boundary);
604
604
    std::copy (itr_pair.first, itr_pair.second, oi);
605
605
  }
606
 
  std::pair<GP_Holes_const_iterator, GP_Holes_const_iterator> hpair = 
 
606
  std::pair<GP_Holes_const_iterator, GP_Holes_const_iterator> hpair =
607
607
    m_traits->construct_holes_object()(pgn);
608
608
  GP_Holes_const_iterator hit;
609
609
  for (hit = hpair.first; hit != hpair.second; ++hit)
630
630
 
631
631
 
632
632
template <class Traits_, class TopTraits_, class ValidationPolicy>
633
 
  typename Gps_on_surface_base_2<Traits_, TopTraits_, ValidationPolicy>::Size 
 
633
  typename Gps_on_surface_base_2<Traits_, TopTraits_, ValidationPolicy>::Size
634
634
  Gps_on_surface_base_2<Traits_, TopTraits_, ValidationPolicy>::
635
635
  number_of_polygons_with_holes() const
636
636
{
637
 
 
 
637
 
638
638
  typedef Arr_bfs_scanner<Arrangement_on_surface_2, Counting_output_iterator>
639
639
    Arr_bfs_scanner;
640
 
  //counting_output_operator CTOR reqires a parameter  
641
 
  std::size_t *cc = new size_t();  
642
 
  Arr_bfs_scanner scanner(this->m_traits, Counting_output_iterator(cc));
 
640
  //counting_output_operator CTOR reqires a parameter
 
641
  std::size_t cc = 0;
 
642
  Arr_bfs_scanner scanner(this->m_traits, Counting_output_iterator(&cc));
643
643
  scanner.scan(*(this->m_arr));
644
644
  return (scanner.output_iterator().current_counter());
645
645
}
693
693
 
694
694
  OutputItr oi (pgn);
695
695
  Arr_bfs_scanner scanner(this->m_traits, oi);
696
 
  
697
 
  
 
696
 
 
697
 
698
698
  Ccb_halfedge_const_circulator ccb_of_pgn = get_boundary_of_polygon(f);
699
699
  this->_reset_faces();
700
 
  if (ccb_of_pgn == Ccb_halfedge_const_circulator()) 
 
700
  if (ccb_of_pgn == Ccb_halfedge_const_circulator())
701
701
  {
702
702
    // the polygon has no boundary
703
703
 
704
 
    // f is unbounded 
 
704
    // f is unbounded
705
705
    for (Face_iterator fit = m_arr->faces_begin(); fit != m_arr->faces_end();
706
706
         ++fit)
707
707
    {
728
728
{
729
729
  CGAL_assertion(!f->visited());
730
730
  f->set_visited(true);
731
 
  
 
731
 
732
732
  if (f->number_of_outer_ccbs() == 0) // (f->is_unbounded())
733
733
  {
734
734
    return Ccb_halfedge_const_circulator();
736
736
 
737
737
  // We assume that a polygon has only one outer_ccb. This code does not handle
738
738
  // the case where there are more than 1 outer ccbs. If this is the case, we
739
 
  // need to devise a method to convert the outer ccbs to inner ccbs so we 
 
739
  // need to devise a method to convert the outer ccbs to inner ccbs so we
740
740
  // will have only one outer ccb.
741
741
  if (f->number_of_outer_ccbs() > 1)
742
742
    CGAL_error_msg("Not implemented yet.");
743
743
 
744
 
        // Some compilers (VC 9) do not like that we directly access the ccb_circ. So we have 
745
 
        // to pass through the iterator.  
 
744
        // Some compilers (VC 9) do not like that we directly access the ccb_circ. So we have
 
745
        // to pass through the iterator.
746
746
  Outer_ccb_const_iterator oci_temp = f->outer_ccbs_begin();
747
747
  Ccb_halfedge_const_circulator ccb_end = *oci_temp;
748
748
  Ccb_halfedge_const_circulator ccb_circ = ccb_end;
749
749
  do
750
 
  { 
 
750
  {
751
751
    //get the current halfedge on the face boundary
752
752
    Halfedge_const_iterator he  = ccb_circ;
753
753
    Face_const_iterator new_f = he->twin()->face();
762
762
  while(ccb_circ != ccb_end);
763
763
  CGAL_error();
764
764
  return Ccb_halfedge_const_circulator();
765
 
  
 
765
 
766
766
}
767
767
 
768
768
template <class Traits_, class TopTraits_, class ValidationPolicy>
770
770
  is_hole_of_face(Face_const_handle f, Halfedge_const_handle he) const
771
771
{
772
772
  Inner_ccb_const_iterator   holes_it;
773
 
  for (holes_it = f->inner_ccbs_begin(); 
 
773
  for (holes_it = f->inner_ccbs_begin();
774
774
       holes_it != f->inner_ccbs_end(); ++holes_it)
775
775
  {
776
776
    Ccb_halfedge_const_circulator ccb = *holes_it;