1 // Copyright (c) 2002-2004 INRIA Sophia-Antipolis (France).
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/Triangulation_2/include/CGAL/apply_to_range.h $
7 // $Id: apply_to_range.h 0779373 2020-03-26T13:31:46+01:00 Sébastien Loriot
8 // SPDX-License-Identifier: LGPL-3.0-or-later OR LicenseRef-Commercial
9 //
10 //
11 // Author(s) : Radu Ursu
12
13 #ifndef CGAL_apply_to_range_h
14 #define CGAL_apply_to_range_h
15
16 #include <CGAL/Point_2.h>
17 #include <CGAL/Unique_hash_map.h>
18 #include <stack>
19
20 namespace CGAL{
21
22
23 template <class Tr, class Fct, class R>
apply_to_range(const Tr & t,const Point_2<R> & p1,const Point_2<R> & p2,Fct & fct)24 void apply_to_range(const Tr &t,
25 const Point_2<R> &p1, const Point_2<R> &p2,
26 Fct& fct)
27 {
28 if (t.dimension()<2) return;
29 typedef typename Tr::Point POINT;
30 typedef typename Tr::Face_handle hFACE;
31 typedef typename Tr::Vertex_handle hVERTEX;
32 typedef typename Tr::Line_face_circulator LFC;
33 typedef typename Tr::Finite_vertices_iterator FVI;
34 typedef typename Tr::Finite_faces_iterator FFI;
35 typedef typename Kernel_traits<POINT>::Kernel K;
36 typedef typename K::FT FT;
37
38 LFC l1, l2, l3, l4; //the faces that intersect the pixmap RECTANGLE
39 hFACE hface1, hface2,
40 hface3, hface4; //the faces where we start to search
41 FT xr_left, yr_top,
42 xr_right, yr_bottom;//the coordinates of the screen boundaries
43 CGAL::Unique_hash_map<hFACE, bool> visited(false);//used for DFS
44 std::stack<hFACE> face_stack; //used for DFS
45
46 xr_left = p1.x(); xr_right = p2.x();
47 yr_top = p1.y(); yr_bottom = p2.y();
48
49 hface1 = t.locate(POINT(xr_left, yr_top));
50 hface2 = t.locate(POINT(xr_right, yr_top));
51 hface3 = t.locate(POINT(xr_right, yr_bottom));
52 hface4 = t.locate(POINT(xr_left, yr_bottom));
53
54 l1 = t.line_walk(POINT(xr_left, yr_top), POINT(xr_right, yr_top), hface1);
55 l2 = t.line_walk(POINT(xr_right, yr_top), POINT(xr_right, yr_bottom), hface2);
56 l3 = t.line_walk(POINT(xr_right, yr_bottom), POINT(xr_left, yr_bottom), hface3);
57 l4 = t.line_walk(POINT(xr_left, yr_bottom), POINT(xr_left, yr_top), hface4);
58
59 //test if everything is inside or outside
60 if( (l1 == nullptr) && (l2 == nullptr) &&
61 (l3 == nullptr) && (l4 == nullptr))
62 {
63 FVI v = t.finite_vertices_begin();
64 if((*v).point().x() < xr_left || (*v).point().x() > xr_right ||
65 (*v).point().y() < yr_bottom || (*v).point().y() > yr_top) //true if everything is outside
66 return;
67 else{ //everything is inside
68 FFI it = t.finite_faces_begin();
69 while(it != t.finite_faces_end())
70 {
71 fct(it);
72 it++;
73 }
74 }
75 return;
76 }
77
78 //if we are here, then a part of the triangulation is inside, the other is outside
79
80 //put all the faces on the boundaries in the stack and the map
81 if(l1 != nullptr) //found at least one face that intersect the TOP segment
82 {
83 while (t.is_infinite(l1)) l1++; //we should start with a finite face
84 do{ //put all of them in the stack;
85 face_stack.push(l1);
86 visited[l1] = true;
87 l1++;
88 }while(!t.is_infinite(l1) &&
89 t.triangle(l1).has_on_unbounded_side(POINT(xr_right, yr_top)));
90 }
91 if(l2 != nullptr) //found at least one face that intersect the RIGHT segment
92 {
93 while (t.is_infinite(l2)) l2++; //we should start with a finite face
94 do{ //put all of them in the stack;
95 if(!visited[l2]){
96 face_stack.push(l2);
97 visited[l2] = true;
98 }
99 l2++;
100 }while(!t.is_infinite(l2) &&
101 t.triangle(l2).has_on_unbounded_side(POINT(xr_right, yr_bottom)));
102 }
103 if(l3 != nullptr) //found at least one face that intersect the BOTTOM segment
104 {
105 while (t.is_infinite(l3)) l3++; //we should start with a finite face
106 do{ //put all of them in the stack;
107 if(!visited[l3]){
108 face_stack.push(l3);
109 visited[l3] = true;
110 }
111 l3++;
112 }while(!t.is_infinite(l3) &&
113 t.triangle(l3).has_on_unbounded_side(POINT(xr_left, yr_bottom)));
114 }
115 if(l4 != nullptr) //found at least one face that intersect the LEFT segment
116 {
117 while (t.is_infinite(l4)) l4++; //we should start with a finite face
118 do{ //put all of them in the stack;
119 if(!visited[l4]){
120 face_stack.push(l4);
121 visited[l4] = true;
122 }
123 l4++;
124 }while(!t.is_infinite(l4) &&
125 t.triangle(l4).has_on_unbounded_side(POINT(xr_left, yr_top)));
126 }
127
128 //HERE we begin to walk through the faces DFS
129 hFACE hf;
130 typename CGAL::Unique_hash_map<hFACE,bool>::Data&
131 data_ref_start(visited[hf]);
132 data_ref_start = true;
133 while(!face_stack.empty()){
134 hf = face_stack.top();
135 face_stack.pop(); //done with this face
136 for (int i=0; i<3; i++){ //visit all the neighbors
137 if(!visited[(*hf).neighbor(i)] )
138 if(!t.is_infinite((*hf).neighbor(i))){ //true if it is not an infinite face
139 hVERTEX hv = (*(*hf).neighbor(i)).vertex((*(*hf).neighbor(i)).index(hf));
140 if(!((*hv).point().x() < xr_left || (*hv).point().x() > xr_right ||
141 (*hv).point().y() < yr_bottom || (*hv).point().y() > yr_top)) //true if the vertex is outside
142 face_stack.push((*hf).neighbor(i));
143 typename CGAL::Unique_hash_map<hFACE,bool>::Data&
144 data_ref(visited[(*hf).neighbor(i)]);
145 data_ref = true;
146 }
147 }
148 fct(hf);
149 }
150 }
151
152 }//end namespace
153
154 #endif
155