1 // Copyright (c) 2013 Technical University Braunschweig (Germany). 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/Visibility_2/include/CGAL/Triangular_expansion_visibility_2.h $ 7 // $Id: Triangular_expansion_visibility_2.h 1faa0e2 2021-04-28T10:55:26+02:00 Sébastien Loriot 8 // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial 9 // 10 // 11 // Author(s): Michael Hemmer <michael.hemmer@cgal.org> 12 // 13 14 #ifndef CGAL_TRIANGULAR_EXPANSION_VISIBILITY_2_H 15 #define CGAL_TRIANGULAR_EXPANSION_VISIBILITY_2_H 16 17 #include <CGAL/license/Visibility_2.h> 18 19 20 #include <CGAL/Arrangement_2.h> 21 #include <memory> 22 #include <CGAL/boost/iterator/transform_iterator.hpp> 23 #include <CGAL/Constrained_Delaunay_triangulation_2.h> 24 #include <CGAL/Arr_observer.h> 25 #include <CGAL/assertions.h> 26 #include <CGAL/use.h> 27 28 namespace CGAL { 29 30 template<class Arrangement_2_ , class RegularizationCategory = CGAL::Tag_true > 31 class Triangular_expansion_visibility_2 { 32 typedef typename Arrangement_2_::Geometry_traits_2 Geometry_traits_2; 33 typedef typename Geometry_traits_2::Kernel K; 34 35 typedef Triangular_expansion_visibility_2< 36 Arrangement_2_, RegularizationCategory> Self; 37 38 public: 39 typedef Arrangement_2_ Arrangement_2; 40 typedef typename Arrangement_2::Traits_2 Traits_2; 41 typedef typename Arrangement_2::Halfedge Halfedge; 42 typedef typename Arrangement_2::Halfedge_const_handle Halfedge_const_handle; 43 typedef typename Arrangement_2::Halfedge_handle Halfedge_handle; 44 typedef typename Arrangement_2::Edge_const_iterator Edge_const_iterator; 45 typedef typename Arrangement_2::Ccb_halfedge_const_circulator 46 Ccb_halfedge_const_circulator; 47 typedef typename Arrangement_2::Ccb_halfedge_circulator 48 Ccb_halfedge_circulator; 49 typedef typename Arrangement_2::Face_const_handle Face_const_handle; 50 typedef typename Arrangement_2::Face_handle Face_handle; 51 typedef typename Arrangement_2::Vertex_const_handle Vertex_const_handle; 52 typedef typename Arrangement_2::Vertex_handle Vertex_handle; 53 54 typedef typename K::Point_2 Point_2; 55 typedef typename Geometry_traits_2::Ray_2 Ray_2; 56 typedef typename Geometry_traits_2::Segment_2 Segment_2; 57 typedef typename Geometry_traits_2::Line_2 Line_2; 58 typedef typename Geometry_traits_2::Vector_2 Vector_2; 59 typedef typename Geometry_traits_2::Direction_2 Direction_2; 60 typedef typename Geometry_traits_2::FT Number_type; 61 typedef typename Geometry_traits_2::Object_2 Object_2; 62 63 typedef RegularizationCategory Regularization_category; 64 65 typedef CGAL::Tag_true Supports_general_polygon_category; 66 typedef CGAL::Tag_true Supports_simple_polygon_category; 67 68 private: 69 typedef CGAL::Triangulation_vertex_base_2<K> Vb; 70 typedef CGAL::Constrained_triangulation_face_base_2<K> Fb; 71 typedef CGAL::Triangulation_data_structure_2<Vb, Fb> TDS; 72 typedef CGAL::No_constraint_intersection_requiring_constructions_tag Itag; 73 typedef CGAL::Constrained_Delaunay_triangulation_2<K, TDS, Itag> CDT; 74 75 typedef std::pair<Point_2, Point_2> Constraint; 76 77 // Functor to create edge constraints for the CDT out of Halfedges 78 struct Make_constraint 79 { 80 typedef Constraint result_type; 81 operatorMake_constraint82 Constraint operator()(const Halfedge& edge) const { 83 return std::make_pair(edge.source()->point(), 84 edge.target()->point()); 85 } 86 }; 87 88 // Observer to track any changes of the attached arrangement. 89 class Observer : public Arr_observer<Arrangement_2> 90 { 91 92 typedef Arr_observer<Arrangement_2> Base; 93 typedef Observer Self; 94 95 96 public: 97 bool has_changed; 98 Observer()99 Observer() : Base(), has_changed(false) 100 {} 101 Observer(const Arrangement_2 & arr)102 Observer(const Arrangement_2& arr) 103 : Base(const_cast<Arrangement_2&>(arr)), has_changed(false) 104 {} 105 106 // Arr_observer interface 107 after_attach()108 void after_attach() { has_changed = false; } 109 110 after_global_change()111 void after_global_change() { has_changed = true; } after_create_vertex(Vertex_handle)112 void after_create_vertex(Vertex_handle) { has_changed = true; } after_create_boundary_vertex(Vertex_handle)113 void after_create_boundary_vertex(Vertex_handle) { has_changed = true; } after_create_edge(Halfedge_handle)114 void after_create_edge(Halfedge_handle) { has_changed = true; } after_modify_vertex(Vertex_handle)115 void after_modify_vertex(Vertex_handle) { has_changed = true; } after_modify_edge(Halfedge_handle)116 void after_modify_edge(Halfedge_handle) { has_changed = true; } after_split_edge(Halfedge_handle,Halfedge_handle)117 void after_split_edge(Halfedge_handle, Halfedge_handle) { 118 has_changed = true; } after_split_fictitious_edge(Halfedge_handle,Halfedge_handle)119 void after_split_fictitious_edge(Halfedge_handle, Halfedge_handle) { 120 has_changed = true; } after_split_face(Face_handle,Face_handle,bool)121 void after_split_face(Face_handle, Face_handle, bool) { 122 has_changed = true; } after_split_outer_ccb(Face_handle,Ccb_halfedge_circulator,Ccb_halfedge_circulator)123 void after_split_outer_ccb(Face_handle, Ccb_halfedge_circulator, 124 Ccb_halfedge_circulator) { 125 has_changed = true; } after_split_inner_ccb(Face_handle,Ccb_halfedge_circulator,Ccb_halfedge_circulator)126 void after_split_inner_ccb(Face_handle, Ccb_halfedge_circulator, 127 Ccb_halfedge_circulator) { 128 has_changed = true; } after_add_outer_ccb(Ccb_halfedge_circulator)129 void after_add_outer_ccb(Ccb_halfedge_circulator) { has_changed = true; } after_add_inner_ccb(Ccb_halfedge_circulator)130 void after_add_inner_ccb(Ccb_halfedge_circulator) { has_changed = true; } after_add_isolated_vertex(Vertex_handle)131 void after_add_isolated_vertex(Vertex_handle) { has_changed = true; } after_merge_edge(Halfedge_handle)132 void after_merge_edge(Halfedge_handle) { has_changed = true; } after_merge_fictitious_edge(Halfedge_handle)133 void after_merge_fictitious_edge(Halfedge_handle) { has_changed = true; } after_merge_face(Face_handle)134 void after_merge_face(Face_handle) { has_changed = true; } after_merge_outer_ccb(Face_handle,Ccb_halfedge_circulator)135 void after_merge_outer_ccb(Face_handle, Ccb_halfedge_circulator) { 136 has_changed = true; } after_merge_inner_ccb(Face_handle,Ccb_halfedge_circulator)137 void after_merge_inner_ccb(Face_handle, Ccb_halfedge_circulator) { 138 has_changed = true; } after_move_outer_ccb(Ccb_halfedge_circulator)139 void after_move_outer_ccb(Ccb_halfedge_circulator) { has_changed = true; } after_move_inner_ccb(Ccb_halfedge_circulator)140 void after_move_inner_ccb(Ccb_halfedge_circulator) { has_changed = true; } after_move_isolated_vertex(Vertex_handle)141 void after_move_isolated_vertex(Vertex_handle) { has_changed = true; } after_remove_vertex()142 void after_remove_vertex() { has_changed = true; } after_remove_edge()143 void after_remove_edge() { has_changed = true; } after_remove_outer_ccb(Face_handle)144 void after_remove_outer_ccb(Face_handle) { has_changed = true; } after_remove_inner_ccb(Face_handle)145 void after_remove_inner_ccb(Face_handle) { has_changed = true; } 146 }; 147 148 149 private: 150 const Arrangement_2* p_arr; 151 152 // May change during visibility computation 153 mutable Observer observer; 154 mutable std::shared_ptr<CDT> p_cdt; 155 mutable std::vector<Segment_2> needles; 156 157 // Copy constructor and assignment not supported 158 Triangular_expansion_visibility_2(const Self&); 159 Self& operator= (const Self& ); 160 161 162 public: Triangular_expansion_visibility_2()163 Triangular_expansion_visibility_2() : p_arr(nullptr){} 164 165 /*! Constructor given an arrangement. */ Triangular_expansion_visibility_2(const Arrangement_2 & arr)166 Triangular_expansion_visibility_2 (const Arrangement_2& arr) 167 : p_arr(&arr), observer(arr) 168 { 169 init_cdt(); 170 } 171 name()172 const std::string name() const { return std::string("T_visibility_2"); } 173 174 is_attached()175 bool is_attached() const { 176 //std::cout << "is_attached" << std::endl; 177 return (p_arr != nullptr); 178 } 179 attach(const Arrangement_2 & arr)180 void attach(const Arrangement_2& arr) { 181 if(p_arr != &arr){ 182 p_arr = &arr; 183 observer.detach(); 184 observer.attach(const_cast<Arrangement_2&>(arr)); 185 init_cdt(); 186 } 187 //std::cout << "attach done" << std::endl; 188 } 189 detach()190 void detach() { 191 //std::cout << "detach" << std::endl; 192 observer.detach(); 193 p_arr = nullptr; 194 p_cdt.reset(); 195 } 196 arrangement_2()197 const Arrangement_2& arrangement_2() const { 198 return *p_arr; 199 } 200 201 202 template <typename VARR> 203 typename VARR::Face_handle compute_visibility(const Point_2 & q,const Face_const_handle face,VARR & out_arr)204 compute_visibility(const Point_2& q, 205 const Face_const_handle face, 206 VARR& out_arr ) 207 const { 208 //std::cout << "query in face interior" << std::endl; 209 210 if(observer.has_changed) { 211 init_cdt(); 212 } 213 214 out_arr.clear(); 215 needles.clear(); 216 CGAL_USE(face); 217 CGAL_assertion(!face->is_unbounded()); 218 219 220 std::vector<Point_2> raw_output; 221 typename CDT::Face_handle fh = p_cdt->locate(q); 222 223 raw_output.push_back(fh->vertex(1)->point()); 224 if(!p_cdt->is_constrained(get_edge(fh,0))){ 225 //std::cout<< "edge 0 is not constrained" << std::endl; 226 expand_edge( 227 q, 228 fh->vertex(2)->point(), 229 fh->vertex(1)->point(), 230 fh,0,std::back_inserter(raw_output)); 231 } 232 233 raw_output.push_back(fh->vertex(2)->point()); 234 if(!p_cdt->is_constrained(get_edge(fh,1))){ 235 //std::cout << "edge 1 is not constrained" << std::endl; 236 expand_edge( 237 q, 238 fh->vertex(0)->point(), 239 fh->vertex(2)->point(), 240 fh,1,std::back_inserter(raw_output)); 241 } 242 243 raw_output.push_back(fh->vertex(0)->point()); 244 if(!p_cdt->is_constrained(get_edge(fh,2))){ 245 //std::cout << "edge 2 is not constrained" << std::endl; 246 expand_edge( 247 q, 248 fh->vertex(1)->point(), 249 fh->vertex(0)->point(), 250 fh,2,std::back_inserter(raw_output)); 251 } 252 253 254 return output(raw_output,out_arr); 255 } 256 257 template <typename VARR> 258 typename VARR::Face_handle compute_visibility(const Point_2 & q,const Halfedge_const_handle he,VARR & out_arr)259 compute_visibility(const Point_2& q, 260 const Halfedge_const_handle he, 261 VARR& out_arr) 262 const { 263 //std::cout << "visibility_region he" << std::endl; 264 265 if(observer.has_changed) { 266 init_cdt(); 267 } 268 269 CGAL_assertion(!he->face()->is_unbounded()); 270 out_arr.clear(); 271 needles.clear(); 272 273 std::vector<Point_2> raw_output; 274 typename CDT::Locate_type location; 275 int index; 276 typename CDT::Face_handle fh = p_cdt->locate(q,location,index); 277 CGAL_assertion(location == CDT::EDGE || location == CDT::VERTEX); 278 //the following code tries to figure out which triangle one should start in. 279 280 281 if(location == CDT::EDGE){ 282 //std::cout << "query on edge" << std::endl; 283 // this is the easy part, there are only two possible faces 284 // index indicates the edge = vertex on the other side of the edge 285 // the next vertex in cw order should be the target of given edge 286 if(fh->vertex(p_cdt->cw(index))->point() != he->target()->point()){ 287 //std::cout << "need to swap face" << std::endl; 288 // take face on the other side if this is not the case 289 typename CDT::Face_handle nfh = fh->neighbor(index); 290 index = nfh->index(fh); 291 fh = nfh; 292 } 293 CGAL_assertion(fh->vertex(p_cdt->cw(index))->point() == he->target()->point()); 294 CGAL_assertion(!p_cdt->is_infinite(fh->vertex(index))); 295 296 297 // output the edge the query lies on 298 raw_output.push_back(he->source()->point()); 299 raw_output.push_back(he->target()->point()); 300 301 if(!p_cdt->is_constrained(get_edge(fh,p_cdt->ccw(index)))){ 302 expand_edge( 303 q, 304 fh->vertex(index)->point(), //left 305 he->target()->point() , //right 306 fh, 307 p_cdt->ccw(index), 308 std::back_inserter(raw_output)); 309 } 310 raw_output.push_back(fh->vertex(index)->point()); 311 312 if(!p_cdt->is_constrained(get_edge(fh,p_cdt->cw(index)))){ 313 expand_edge( 314 q, 315 he->source()->point() , //left 316 fh->vertex(index)->point(), //right 317 fh, 318 p_cdt->cw(index), 319 std::back_inserter(raw_output)); 320 } 321 } 322 323 if(location == CDT::VERTEX){ 324 //std::cout << "query on vertex" << std::endl; 325 326 //bool query_point_on_vertex_is_not_working_yet = false; 327 //CGAL_assertion(query_point_on_vertex_is_not_working_yet); 328 329 CGAL_assertion(q == he->target()->point()); 330 CGAL_assertion(fh->vertex(index)->point() == he->target()->point()); 331 332 // push points that are seen anyway 333 // raw_output.push_back(he->source()->point()); inserted last 334 raw_output.push_back(he->target()->point()); 335 raw_output.push_back(he->next()->target()->point()); 336 337 // now start in the triangle that contains he->next() 338 while( 339 p_cdt->is_infinite(fh->vertex(p_cdt->ccw(index))) || 340 he->next()->target()->point() != 341 fh->vertex(p_cdt->ccw(index))->point() 342 ) 343 { 344 typename CDT::Face_handle nfh = fh->neighbor(p_cdt->ccw(index)); 345 int nindex = nfh->index(fh); 346 index = p_cdt->ccw(nindex); 347 fh = nfh; 348 CGAL_assertion(he->target()->point() == fh->vertex(index)->point()); 349 } 350 351 352 CGAL_assertion(he->next()->source()->point() == fh->vertex(index)->point()); 353 CGAL_assertion(he->next()->target()->point() == 354 fh->vertex(p_cdt->ccw(index))->point()); 355 CGAL_assertion(!p_cdt->is_infinite(fh)); 356 CGAL_assertion(p_cdt->is_constrained(get_edge(fh,p_cdt->cw(index)))); 357 358 while(he->source()->point() != fh->vertex(p_cdt->ccw(index))->point()){ 359 360 if(!p_cdt->is_constrained(get_edge(fh,index))){ 361 expand_edge( 362 q, 363 fh->vertex(p_cdt-> cw(index))->point(), //left 364 fh->vertex(p_cdt->ccw(index))->point(), //right 365 fh, 366 index, 367 std::back_inserter(raw_output)); 368 } 369 // push left end point of edge into output 370 raw_output.push_back(fh->vertex(p_cdt-> cw(index))->point()); 371 372 // take the next triangle around q in ccw order 373 typename CDT::Face_handle nfh = fh->neighbor(p_cdt->ccw(index)); 374 int nindex = nfh->index(fh); 375 index = p_cdt->ccw(nindex); 376 fh = nfh; 377 CGAL_assertion(fh->vertex(index)->point() == he->target()->point()); 378 } 379 } 380 return output(raw_output,out_arr); 381 } 382 383 384 385 private: 386 get_edge(typename CDT::Face_handle fh,int i)387 typename CDT::Edge get_edge(typename CDT::Face_handle fh, int i) const { 388 return std::make_pair(fh,i); 389 } 390 ray_seg_intersection(const Point_2 & q,const Point_2 & b,const Point_2 & s,const Point_2 & t)391 Point_2 ray_seg_intersection( 392 const Point_2& q, const Point_2& b, // the ray 393 const Point_2& s, const Point_2& t // the segment 394 ) const { 395 396 Ray_2 ray(q,b); 397 Segment_2 seg(s,t); 398 CGAL_assertion(typename K::Do_intersect_2()(ray,seg)); 399 CGAL::Object obj = typename K::Intersect_2()(ray,seg); 400 Point_2 result = object_cast<Point_2>(obj); 401 return result; 402 } 403 collect_needle(const Point_2 & q,const typename CDT::Vertex_handle vh,const typename CDT::Face_handle fh,int index)404 void collect_needle( 405 const Point_2& q, 406 const typename CDT::Vertex_handle vh, 407 const typename CDT::Face_handle fh, 408 int index) 409 const { 410 411 // the expanded edge should not be constrained 412 CGAL_assertion(!p_cdt->is_constrained(get_edge(fh,index))); 413 CGAL_assertion(!p_cdt->is_infinite(fh)); 414 // go into the new face 415 const typename CDT::Face_handle nfh(fh->neighbor(index)); 416 CGAL_assertion(!p_cdt->is_infinite(nfh)); 417 418 // get indices of neighbors 419 int nindex = nfh->index(fh); // index of new vertex and old face 420 int rindex = p_cdt->ccw(nindex); // index of face behind right edge 421 int lindex = p_cdt-> cw(nindex); // index of face behind left edge 422 423 // get vertices seen from entering edge 424 const typename CDT::Vertex_handle nvh(nfh->vertex(nindex)); 425 const typename CDT::Vertex_handle rvh(nfh->vertex(p_cdt->cw (nindex))); 426 const typename CDT::Vertex_handle lvh(nfh->vertex(p_cdt->ccw(nindex))); 427 CGAL_assertion(!p_cdt->is_infinite(nvh)); 428 CGAL_assertion(!p_cdt->is_infinite(lvh)); 429 CGAL_assertion(!p_cdt->is_infinite(rvh)); 430 431 // get edges seen from entering edge 432 typename CDT::Edge re = get_edge(nfh,p_cdt->ccw(nindex)); 433 typename CDT::Edge le = get_edge(nfh,p_cdt-> cw(nindex)); 434 435 // do orientation computation once for new vertex 436 typename K::Orientation_2 orientation = 437 p_cdt->geom_traits().orientation_2_object(); 438 CGAL::Orientation orient = orientation(q,vh->point(),nvh->point()); 439 440 441 //std::cout << "\n collect_needle" <<std::endl; 442 //std::cout << "q "<< q << std::endl ; 443 //std::cout << "vh->point() "<< vh->point() << std::endl; 444 //std::cout << "lvh->point() "<< lvh->point() << std::endl ; 445 //std::cout << "nvh->point() "<< nvh->point() << std::endl ; 446 //std::cout << "rvh->point() "<< rvh->point() << std::endl<< std::endl; 447 448 449 switch ( orient ) { 450 case CGAL::COUNTERCLOCKWISE: 451 // looking on to the right edge 452 if(p_cdt->is_constrained(re)) { 453 if(vh != rvh) { 454 Point_2 p = ray_seg_intersection(q, vh->point(), 455 nvh->point(), rvh->point()); 456 //std::cout << vh->point() <<" -1- "<< p <<std::endl; 457 needles.push_back(Segment_2(vh->point(),p)); 458 } 459 } else { 460 collect_needle(q,vh,nfh,rindex); 461 } 462 break; 463 case CGAL::CLOCKWISE: 464 // looking on to the left edge 465 if(p_cdt->is_constrained(le)){ 466 if(vh != lvh){ 467 Point_2 p = ray_seg_intersection(q, vh->point(), 468 nvh->point(), lvh->point()); 469 //std::cout << vh->point() <<" -2- "<< p <<std::endl; 470 needles.push_back(Segment_2(vh->point(),p)); 471 } 472 } else { 473 collect_needle(q,vh,nfh,lindex); 474 } 475 break; 476 default: 477 CGAL_assertion(orient == CGAL::COLLINEAR); 478 // looking on nvh, so it must be reported 479 // if it wasn't already (triangles rotate around vh) 480 if(vh != nvh){ 481 //std::cout << vh->point() <<" -3- "<< nvh->point() <<std::endl; 482 needles.push_back(Segment_2(vh->point(),nvh->point())); 483 } 484 // but we may also contiue looking along the vertex 485 if(!p_cdt->is_constrained(re)) { 486 collect_needle(q,nvh,nfh,rindex); 487 } 488 if(!p_cdt->is_constrained(le)) { 489 collect_needle(q,nvh,nfh,lindex); 490 } 491 break; 492 } 493 } 494 495 template<class OIT> expand_edge(const Point_2 & q,const Point_2 & left,const Point_2 & right,typename CDT::Face_handle fh,int index,OIT oit)496 OIT expand_edge( 497 const Point_2& q, 498 const Point_2& left, 499 const Point_2& right, 500 typename CDT::Face_handle fh, 501 int index, 502 OIT oit) 503 const { 504 505 // the expanded edge should not be constrained 506 CGAL_assertion(!p_cdt->is_constrained(get_edge(fh,index))); 507 CGAL_assertion(!p_cdt->is_infinite(fh)); 508 509 // go into the new face 510 const typename CDT::Face_handle nfh(fh->neighbor(index)); 511 CGAL_assertion(!p_cdt->is_infinite(nfh)); 512 513 // get indices of neighbors 514 int nindex = nfh->index(fh); // index of new vertex and old face 515 int rindex = p_cdt->ccw(nindex); // index of face behind right edge 516 int lindex = p_cdt-> cw(nindex); // index of face behind left edge 517 518 // get vertices seen from entering edge 519 const typename CDT::Vertex_handle nvh(nfh->vertex(nindex)); 520 const typename CDT::Vertex_handle rvh(nfh->vertex(p_cdt->cw (nindex))); 521 const typename CDT::Vertex_handle lvh(nfh->vertex(p_cdt->ccw(nindex))); 522 CGAL_assertion(!p_cdt->is_infinite(nvh)); 523 CGAL_assertion(!p_cdt->is_infinite(lvh)); 524 CGAL_assertion(!p_cdt->is_infinite(rvh)); 525 526 // get edges seen from entering edge 527 typename CDT::Edge re = get_edge(nfh,p_cdt->ccw(nindex)); 528 typename CDT::Edge le = get_edge(nfh,p_cdt-> cw(nindex)); 529 530 // do orientation computation once for new vertex 531 typename K::Orientation_2 orientation = 532 p_cdt->geom_traits().orientation_2_object(); 533 CGAL::Orientation ro = orientation(q,right,nvh->point()); 534 CGAL::Orientation lo = orientation(q,left ,nvh->point()); 535 536 CGAL_assertion(typename K::Orientation_2()(q,left ,lvh->point()) 537 != CGAL::CLOCKWISE); 538 CGAL_assertion(typename K::Orientation_2()(q,right,rvh->point()) 539 != CGAL::COUNTERCLOCKWISE); 540 541 //std::cout << (ro == CGAL::COUNTERCLOCKWISE) << " " << 542 //(lo == CGAL::CLOCKWISE) << std::endl; 543 544 //right edge is seen if new vertex is counter clockwise of right boarder 545 if(ro == CGAL::COUNTERCLOCKWISE){ 546 if(p_cdt->is_constrained(re)){ 547 // the edge is constrained 548 // report intersection with right boarder ray 549 // if it is not already the right vertex (already reported) 550 if(right != rvh->point()){ 551 *oit++ = ray_seg_intersection(q,right,nvh->point(),rvh->point()); 552 } 553 554 // then report intersection with left boarder if it exists 555 if(lo == CGAL::COUNTERCLOCKWISE){ 556 *oit++ = ray_seg_intersection(q,left,nvh->point(),rvh->point()); 557 } 558 }else{ 559 // the edge is not a constrained 560 if(lo == CGAL::COUNTERCLOCKWISE){ 561 // no split needed and return 562 //std::cout<< "h1"<< std::endl; 563 oit = expand_edge(q,left,right,nfh,rindex,oit); 564 //std::cout<< "h1 done"<< std::endl; 565 return oit; 566 }else{ 567 // spliting at new vertex 568 //std::cout<< "h2"<< std::endl; 569 *oit++ = expand_edge(q,nvh->point(),right,nfh,rindex,oit); 570 //std::cout<< "h2 done"<< std::endl; 571 } 572 } 573 } 574 575 576 //std::cout << "q "<< q << std::endl ; 577 //std::cout << "lvh->point() "<< lvh->point() << std::endl; 578 //std::cout << "left "<< left << std::endl ; 579 //std::cout << "nvh->point() "<< nvh->point() << std::endl ; 580 //std::cout << "right "<< right << std::endl ; 581 //std::cout << "rvh->point() "<< rvh->point() << std::endl<< std::endl; 582 583 584 // determin whether new vertex needs to be reported 585 if(ro != CGAL::CLOCKWISE && lo != CGAL::COUNTERCLOCKWISE){ 586 *oit++ = nvh->point(); 587 } 588 if(!Regularization_category::value){ 589 CGAL_assertion(!(ro == CGAL::COLLINEAR && lo == CGAL::COLLINEAR)); 590 // we have to check whether a needle starts here. 591 if(p_cdt->is_constrained(le) && !p_cdt->is_constrained(re) 592 && ro == CGAL::COLLINEAR) 593 collect_needle(q,nvh,nfh,rindex); 594 595 if(p_cdt->is_constrained(re) && !p_cdt->is_constrained(le) 596 && lo == CGAL::COLLINEAR) 597 collect_needle(q,nvh,nfh,lindex); 598 } 599 600 //left edge is seen if new vertex is clockwise of left boarder 601 if(lo == CGAL::CLOCKWISE){ 602 if(p_cdt->is_constrained(le)){ 603 // the edge is constrained 604 // report interesection with right boarder if exists 605 if(ro == CGAL::CLOCKWISE){ 606 *oit++ = ray_seg_intersection(q,right,nvh->point(),lvh->point()); 607 } 608 // then report intersection with left boarder ray 609 // if it is not already the left vertex (already reported) 610 if(left != lvh->point()){ 611 *oit++ = ray_seg_intersection(q,left,nvh->point(),lvh->point()); 612 } 613 return oit; 614 }else{ 615 // the edge is not a constrained 616 if(ro == CGAL::CLOCKWISE){ 617 // no split needed and return 618 //std::cout<< "h3"<< std::endl; 619 oit = expand_edge(q,left,right,nfh,lindex,oit); 620 //std::cout<< "h3 done"<< std::endl; 621 return oit; 622 }else{ 623 // spliting at new vertex 624 //std::cout<< "h4"<< std::endl; 625 oit = expand_edge(q,left,nvh->point(),nfh,lindex,oit); 626 //std::cout<< "h4 done"<< std::endl; 627 return oit; 628 } 629 } 630 } 631 632 return oit; 633 } 634 635 636 template <typename VARR> 637 typename VARR::Face_handle output(std::vector<Point_2> & raw_output,VARR & out_arr)638 output(std::vector<Point_2>& raw_output, VARR& out_arr) const { 639 640 if(!needles.empty()){ 641 std::vector<Segment_2> segments(needles.begin(),needles.end()); 642 for(unsigned int i = 0; i < raw_output.size(); i++){ 643 // //std::cout << raw_output[i] << " -- " 644 // << raw_output[(i+1)%raw_output.size()] << std::endl; 645 segments.push_back(Segment_2(raw_output[i], 646 raw_output[(i+1) % raw_output.size()])); 647 } 648 649 CGAL::insert_non_intersecting_curves(out_arr, 650 segments.begin(), 651 segments.end()); 652 653 } else { 654 typename VARR::Vertex_handle v_last, v_first; 655 v_last = v_first = 656 out_arr.insert_in_face_interior(raw_output[0],out_arr.unbounded_face()); 657 658 for(unsigned int i = 0; i < raw_output.size()-1; i++){ 659 // std::cout << raw_output[i] << " -- " 660 // << raw_output[(i+1)%raw_output.size()] << std::endl; 661 if(raw_output[i] < raw_output[(i+1)]){ 662 v_last = out_arr.insert_from_left_vertex ( 663 Segment_2(raw_output[i], raw_output[i+1]), v_last 664 )->target(); 665 } else { 666 v_last = out_arr.insert_from_right_vertex( 667 Segment_2(raw_output[i], raw_output[i+1]), v_last 668 )->target(); 669 } 670 } 671 out_arr.insert_at_vertices( 672 Segment_2(raw_output.front(), raw_output.back()), 673 v_last, v_first 674 ); 675 } 676 677 CGAL_assertion(out_arr.number_of_faces() == 2); 678 679 if(out_arr.faces_begin()->is_unbounded()) 680 return ++out_arr.faces_begin(); 681 else 682 return out_arr.faces_begin(); 683 } 684 init_cdt()685 void init_cdt() const { 686 //std::cout<< "==============" <<std::endl; 687 //std::cout<< "Input Polygon:" <<std::endl; 688 689 typedef typename boost::transform_iterator<Make_constraint, 690 Edge_const_iterator> Iter; 691 692 Iter begin = boost::make_transform_iterator(p_arr->edges_begin(), 693 Make_constraint()); 694 695 Iter end = boost::make_transform_iterator(p_arr->edges_end(), 696 Make_constraint()); 697 698 //std::cout << "init_cdt new CDT" << std::endl; 699 p_cdt = std::shared_ptr<CDT>(new CDT(begin, end)); 700 observer.has_changed = false; 701 //std::cout << "init_cdt done" << std::endl; 702 //std::cout << std::endl; 703 } 704 }; 705 706 } // namespace CGAL 707 708 #endif // CGAL_TRIANGULAR_EXPANSION_VISIBILITY_2_H 709