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_base_visitor.h $ 7 // $Id: Gps_bfs_base_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_BPS_BASE_VISITOR_H 15 #define CGAL_GPS_BPS_BASE_VISITOR_H 16 17 #include <CGAL/license/Boolean_set_operations_2.h> 18 19 20 #include <CGAL/Unique_hash_map.h> 21 22 namespace CGAL { 23 24 //! Gps_bfs_base_visitor 25 /*! This is a base class for all visitors that are responsible for merging 26 polygon sets. 27 We use DerivedVisitor for static polymorphism for using contained_criteria 28 which determines if we should mark the face as contained given the inside 29 count of the face. 30 */ 31 template <class Arrangement_, class DerivedVisitor> 32 class Gps_bfs_base_visitor 33 { 34 typedef Arrangement_ Arrangement; 35 typedef typename Arrangement::Face_iterator Face_iterator; 36 typedef typename Arrangement::Halfedge_iterator Halfedge_iterator; 37 public: 38 typedef Unique_hash_map<Halfedge_iterator, unsigned int> Edges_hash; 39 typedef Unique_hash_map<Face_iterator, unsigned int> Faces_hash; 40 41 protected: 42 Edges_hash* m_edges_hash; 43 Faces_hash* m_faces_hash; 44 unsigned int m_num_of_polygons; // number of polygons 45 46 public: 47 Gps_bfs_base_visitor(Edges_hash * edges_hash,Faces_hash * faces_hash,unsigned int n_pgn)48 Gps_bfs_base_visitor(Edges_hash* edges_hash, 49 Faces_hash* faces_hash, 50 unsigned int n_pgn): 51 m_edges_hash(edges_hash), 52 m_faces_hash(faces_hash), 53 m_num_of_polygons(n_pgn) 54 {} 55 56 57 //! discovered_face 58 /*! discovered_face is called by Gps_bfs_scanner when it reveals a new face 59 during a BFS scan. In the BFS traversal we are going from old_face to 60 new_face throught the half-edge he. 61 \param old_face The face that was already revealed 62 \param new_face The face that we have just now revealed 63 \param he The half-edge that is used to traverse between them. 64 */ discovered_face(Face_iterator old_face,Face_iterator new_face,Halfedge_iterator he)65 void discovered_face(Face_iterator old_face, 66 Face_iterator new_face, 67 Halfedge_iterator he) 68 { 69 unsigned int ic = compute_ic(old_face, new_face, he); 70 71 if (static_cast<DerivedVisitor*>(this)->contained_criteria(ic)) 72 new_face->set_contained(true); 73 } 74 75 // mark the unbounded_face (true iff contained) visit_ubf(Face_iterator ubf,unsigned int ubf_ic)76 void visit_ubf(Face_iterator ubf, unsigned int ubf_ic) 77 { 78 CGAL_assertion(ubf->is_unbounded()); 79 if(static_cast<DerivedVisitor*>(this)->contained_criteria(ubf_ic)) 80 ubf->set_contained(true); 81 } 82 83 protected: 84 85 // compute the inside count of a face compute_ic(Face_iterator f1,Face_iterator f2,Halfedge_iterator he)86 unsigned int compute_ic(Face_iterator f1, 87 Face_iterator f2, 88 Halfedge_iterator he) 89 { 90 CGAL_assertion(m_edges_hash->is_defined(he) && 91 m_edges_hash->is_defined(he->twin()) && 92 m_faces_hash->is_defined(f1) && 93 !m_faces_hash->is_defined(f2)); 94 unsigned int ic_f2 = 95 (*m_faces_hash)[f1] - (*m_edges_hash)[he] + (*m_edges_hash)[he->twin()]; 96 (*m_faces_hash)[f2] = ic_f2; 97 98 return (ic_f2); 99 } 100 }; 101 102 } //namespace CGAL 103 104 #endif 105