1 // Copyright (c) 2005  Tel-Aviv University (Israel).
2 // All rights reserved.
3 //
4 // This file is part of CGAL (www.cgal.org).
5 //
6 // $URL: https://github.com/CGAL/cgal/blob/v5.3/Boolean_set_operations_2/include/CGAL/Boolean_set_operations_2/Gps_bfs_xor_visitor.h $
7 // $Id: Gps_bfs_xor_visitor.h 0779373 2020-03-26T13:31:46+01:00 Sébastien Loriot
8 // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial
9 //
10 //
11 // Author(s)     : Baruch Zukerman <baruchzu@post.tau.ac.il>
12 //                 Ophir Setter    <ophir.setter@cs.tau.ac.il>
13 
14 #ifndef CGAL_GPS_BFS_XOR_VISITOR_H
15 #define CGAL_GPS_BFS_XOR_VISITOR_H
16 
17 #include <CGAL/license/Boolean_set_operations_2.h>
18 
19 
20 #include <CGAL/Boolean_set_operations_2/Gps_bfs_base_visitor.h>
21 
22 namespace CGAL {
23 
24 template <class Arrangement_>
25 class Gps_bfs_xor_visitor :
26 public Gps_bfs_base_visitor<Arrangement_, Gps_bfs_xor_visitor<Arrangement_> >
27 {
28   typedef  Arrangement_                                  Arrangement;
29   typedef typename Arrangement::Face_iterator            Face_iterator;
30   typedef typename Arrangement::Halfedge_iterator        Halfedge_iterator;
31   typedef Gps_bfs_xor_visitor<Arrangement>               Self;
32   typedef Gps_bfs_base_visitor<Arrangement, Self>        Base;
33   typedef typename Base::Edges_hash                      Edges_hash;
34   typedef typename Base::Faces_hash                      Faces_hash;
35 
36 public:
37 
Gps_bfs_xor_visitor(Edges_hash * edges_hash,Faces_hash * faces_hash,unsigned int n_pgn)38   Gps_bfs_xor_visitor(Edges_hash* edges_hash, Faces_hash* faces_hash,
39                       unsigned int n_pgn) :
40     Base(edges_hash, faces_hash, n_pgn)
41   {}
42 
43     //! contained_criteria
44 /*! contained_criteria is used to the determine if the face which has
45   inside count should be marked as contained.
46   \param ic the inner count of the talked-about face.
47   \return true if the face of ic, otherwise false.
48 */
contained_criteria(unsigned int ic)49   bool contained_criteria(unsigned int ic)
50   {
51     // xor means odd number of polygons.
52     return (ic % 2) == 1;
53   }
54 
55   //! after_scan post-processing after bfs scan.
56 /*! The function fixes some of the curves, to be in the same direction as the
57     half-edges.
58 
59   \param arr The given arrangment.
60 */
after_scan(Arrangement & arr)61   void after_scan(Arrangement& arr)
62   {
63     typedef typename Arrangement::Geometry_traits_2 Traits;
64     typedef typename Traits::Compare_endpoints_xy_2 Compare_endpoints_xy_2;
65     typedef typename Traits::Construct_opposite_2   Construct_opposite_2;
66     typedef typename Traits::X_monotone_curve_2     X_monotone_curve_2;
67     typedef typename Arrangement::Edge_iterator     Edge_iterator;
68 
69     Traits tr;
70     Compare_endpoints_xy_2 cmp_endpoints =
71       tr.compare_endpoints_xy_2_object();
72     Construct_opposite_2 ctr_opp = tr.construct_opposite_2_object();
73 
74     for(Edge_iterator eit = arr.edges_begin();
75         eit != arr.edges_end();
76         ++eit)
77     {
78       Halfedge_iterator         he = eit;
79       const X_monotone_curve_2& cv = he->curve();
80       const bool                is_cont = he->face()->contained();
81       const Comparison_result   he_res =
82         ((Arr_halfedge_direction)he->direction() == ARR_LEFT_TO_RIGHT) ?
83                                          SMALLER : LARGER;
84       const bool has_same_dir = (cmp_endpoints(cv) == he_res);
85 
86       if ((is_cont && !has_same_dir) || (!is_cont && has_same_dir))
87         arr.modify_edge(he, ctr_opp(cv));
88     }
89   }
90 
91 };
92 
93 } //namespace CGAL
94 
95 #endif
96