1 // Copyright (c) 1997-2000 Max-Planck-Institute Saarbruecken (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/Nef_2/include/CGAL/Nef_2/Segment_overlay_traits.h $ 7 // $Id: Segment_overlay_traits.h f3f6beb 2021-05-12T07:37:49+01:00 Giles Bathgate 8 // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial 9 // 10 // 11 // Author(s) : Michael Seel <seel@mpi-sb.mpg.de> 12 #ifndef CGAL_SEGMENT_OVERLAY_TRAITS_H 13 #define CGAL_SEGMENT_OVERLAY_TRAITS_H 14 15 #include <CGAL/license/Nef_2.h> 16 17 18 #undef CGAL_NEF_DEBUG 19 #define CGAL_NEF_DEBUG 23 20 #include <CGAL/Nef_2/debug.h> 21 22 #if defined(CGAL_USE_LEDA_LIBRARY) 23 #include <CGAL/LEDA_basic.h> 24 25 #include <LEDA/core/tuple.h> 26 #include <LEDA/core/slist.h> 27 #include <LEDA/core/list.h> 28 #include <LEDA/core/map.h> 29 #include <LEDA/core/map2.h> 30 #include <LEDA/core/sortseq.h> 31 #include <LEDA/core/p_queue.h> 32 #include <LEDA/core/impl/ab_tree.h> 33 #include <LEDA/core/impl/bb_tree.h> 34 #include <LEDA/core/impl/rb_tree.h> 35 #include <LEDA/core/impl/rs_tree.h> 36 #include <LEDA/core/impl/skiplist.h> 37 38 #include <utility> 39 #include <sstream> 40 41 namespace CGAL { 42 #ifdef CGAL_USE_TRACE 43 #define PIS(s) (s->first()) 44 #endif 45 46 template <typename IT, typename PMDEC, typename GEOM> 47 class leda_seg_overlay_traits { 48 public: 49 typedef IT ITERATOR; 50 typedef std::pair<IT,IT> INPUT; 51 typedef PMDEC OUTPUT; 52 typedef typename PMDEC::Vertex_handle Vertex_handle; 53 typedef typename PMDEC::Halfedge_handle Halfedge_handle; 54 typedef GEOM GEOMETRY; 55 typedef typename GEOMETRY::Point_2 Point_2; 56 typedef typename GEOMETRY::Segment_2 Segment_2; 57 58 typedef leda_two_tuple<Segment_2,ITERATOR> seg_pair; 59 typedef seg_pair* ISegment; 60 typedef leda_list<seg_pair> IList; 61 typedef typename IList::iterator ilist_iterator; 62 63 64 // types interfacing the generic sweep frame: 65 ITERATOR its, ite; 66 OUTPUT& GO; 67 const GEOMETRY& K; 68 69 class cmp_segs_at_sweepline : public CGAL_LEDA_SCOPE::leda_cmp_base<ISegment> 70 { const Point_2& p; 71 ISegment s_bottom, s_top; // sentinel segments 72 const GEOMETRY& K; 73 public: cmp_segs_at_sweepline(const Point_2 & pi,ISegment s1,ISegment s2,const GEOMETRY & k)74 cmp_segs_at_sweepline(const Point_2& pi, 75 ISegment s1, ISegment s2, const GEOMETRY& k) : 76 p(pi), s_bottom(s1), s_top(s2), K(k) {} 77 operator()78 int operator()(const ISegment& is1, const ISegment& is2) const 79 { // Precondition: p is identical to the left endpoint of s1 or s2. 80 if ( is2 == s_top || is1 == s_bottom ) return -1; 81 if ( is1 == s_top || is2 == s_bottom ) return 1; 82 if ( is1 == is2 ) return 0; 83 const Segment_2& s1 = is1->first(); 84 const Segment_2& s2 = is2->first(); 85 int s = 0; 86 if ( p == K.source(s1) ) s = K.orientation(s2,p); 87 else if ( p == K.source(s2) ) s = - K.orientation(s1,p); 88 else CGAL_error_msg("compare error in sweep."); 89 if ( s || K.is_degenerate(s1) || K.is_degenerate(s2) ) 90 return s; 91 92 s = K.orientation(s2,K.target(s1)); 93 if (s==0) return static_cast<int>( is1 - is2 ); 94 // overlapping segments are not equal 95 return s; 96 } 97 }; 98 99 struct cmp_pnts_xy : public CGAL_LEDA_SCOPE::leda_cmp_base<Point_2> 100 { const GEOMETRY& K; 101 public: cmp_pnts_xycmp_pnts_xy102 cmp_pnts_xy(const GEOMETRY& k) : K(k) {} operatorcmp_pnts_xy103 int operator()(const Point_2& p1, const Point_2& p2) const 104 { return K.compare_xy(p1,p2); } 105 }; 106 107 // typedef CGAL_LEDA_SCOPE::skiplist SearchTree; 108 // typedef typename SearchTree::item ST_item; 109 typedef CGAL_LEDA_SCOPE::seq_item ST_item; 110 typedef leda_sortseq<Point_2, ST_item> EventQueue; 111 typedef leda_sortseq<ISegment, ST_item> SweepStatus; 112 typedef leda_p_queue<Point_2,ISegment> SegQueue; 113 typedef leda_map<ST_item,Halfedge_handle> AssocEdgeMap; 114 typedef leda_slist<ITERATOR> IsoList; 115 typedef typename IsoList::item slist_item; 116 typedef leda_map<ST_item, IsoList* > AssocIsoMap; 117 typedef leda_map2<ISegment,ISegment,ST_item> EventHash; 118 119 120 ST_item event; 121 Point_2 p_sweep; 122 cmp_pnts_xy cmp; 123 EventQueue XS; 124 seg_pair sl,sh; 125 cmp_segs_at_sweepline SLcmp; 126 SweepStatus YS; 127 SegQueue SQ; 128 129 EventHash IEvent; 130 IList Internal; 131 AssocEdgeMap Edge_of; 132 AssocIsoMap Isos_of; 133 leda_seg_overlay_traits(const INPUT & in,OUTPUT & G,const GEOMETRY & k)134 leda_seg_overlay_traits(const INPUT& in, OUTPUT& G, 135 const GEOMETRY& k) : 136 its(in.first), ite(in.second), GO(G), K(k), 137 cmp(K), XS(cmp), SLcmp(p_sweep,&sl,&sh,K), YS(SLcmp), SQ(cmp), 138 IEvent(0), Edge_of(0), Isos_of(0) {} 139 140 dump_structures()141 leda_string dump_structures() const 142 { 143 std::ostringstream out; 144 out << "SQ= "; 145 CGAL_LEDA_SCOPE::pq_item pqit; 146 forall_items(pqit,SQ) { 147 if (SQ.prio(pqit)==XS.key(XS.succ(XS.min_item()))) 148 { out << SQ.inf(pqit)->first(); } 149 pqit = SQ.next_item(pqit); 150 } 151 ST_item sit; 152 out << "\nXS=\n"; 153 forall_items(sit,XS) 154 out << " " << XS.key(sit) << " " << XS.inf(sit) 155 <<std::endl; 156 out << "YS=\n"; 157 for( sit = YS.max_item(); sit; sit=YS.pred(sit) ) 158 out << " "<<YS.key(sit)->first()<<" "<<YS.inf(sit)<<std::endl; 159 leda_string res(out.str().c_str()); 160 return res; 161 } 162 163 source(ISegment is)164 Point_2 source(ISegment is) const 165 { return K.source(is->first()); } target(ISegment is)166 Point_2 target(ISegment is) const 167 { return K.target(is->first()); } original(ISegment s)168 ITERATOR original(ISegment s) const 169 { return s->second(); } 170 orientation(ST_item sit,const Point_2 & p)171 int orientation(ST_item sit, const Point_2& p) const 172 { return K.orientation(YS.key(sit)->first(),p); } 173 collinear(ST_item sit1,ST_item sit2)174 bool collinear(ST_item sit1, 175 ST_item sit2) const 176 { Point_2 ps = source(YS.key(sit2)), pt = target(YS.key(sit2)); 177 return ( orientation(sit1,ps)==0 && 178 orientation(sit1,pt)==0 ); 179 } 180 181 compute_intersection(ST_item sit0)182 void compute_intersection(ST_item sit0) 183 { 184 ST_item sit1 = YS.succ(sit0); 185 if ( sit0 == YS.min_item() || sit1 == YS.max_item() ) return; 186 ISegment s0 = YS.key(sit0); 187 ISegment s1 = YS.key(sit1); 188 int or0 = K.orientation(s0->first(),target(s1)); 189 int or1 = K.orientation(s1->first(),target(s0)); 190 if ( or0 <= 0 && or1 >= 0 ) { 191 ST_item it = IEvent(YS.key(sit0),YS.key(sit1)); 192 if ( it==0 ) { 193 Point_2 q = K.intersection(s0->first(),s1->first()); 194 it = XS.insert(q,sit0); 195 } 196 YS.change_inf(sit0, it); 197 } 198 } 199 initialize_structures()200 void initialize_structures() 201 { 202 CGAL_NEF_TRACEN("initialize_structures"); 203 ITERATOR it_s; 204 for ( it_s=its; it_s != ite; ++it_s ) { 205 Segment_2 s = *it_s; 206 ST_item it1 = 207 XS.insert( K.source(s), ST_item(nil)); 208 ST_item it2 = 209 XS.insert( K.target(s), ST_item(nil)); 210 if (it1 == it2) { 211 if ( Isos_of[it1] == 0 ) Isos_of[it1] = new IsoList; 212 Isos_of[it1]->push(it_s); 213 continue; // ignore zero-length segments in SQ/YS 214 } 215 216 Point_2 p = XS.key(it1); 217 Point_2 q = XS.key(it2); 218 219 Segment_2 s1; 220 if ( K.compare_xy(p,q) < 0 ) 221 s1 = K.construct_segment(p,q); 222 else 223 s1 = K.construct_segment(q,p); 224 225 Internal.append(seg_pair(s1,it_s)); 226 SQ.insert(K.source(s1),&Internal[Internal.last()]); 227 } 228 229 // insert a lower and an upper sentinel segment 230 YS.insert(&sl,ST_item(nil)); 231 YS.insert(&sh,ST_item(nil)); 232 CGAL_NEF_TRACEN("end of initialization\n"<<YS.size()); 233 } 234 event_exists()235 bool event_exists() 236 { 237 if (!XS.empty()) { 238 // event is set at end of loop and in init 239 event = (XS.min)(); 240 p_sweep = XS.key(event); 241 return true; 242 } 243 return false; 244 } 245 procede_to_next_event()246 void procede_to_next_event() 247 { XS.del_item(event); } 248 process_event()249 void process_event() 250 { 251 CGAL_NEF_TRACEN("\n\n >>> process_event: "<<p_sweep<<" "<<XS[event]<<" "<<event); 252 253 Vertex_handle v = GO.new_vertex(p_sweep); 254 ST_item sit = XS.inf(event); 255 256 ST_item sit_succ(0), sit_pred(0), sit_pred_succ(0), sit_first(0); 257 if (sit == nil) 258 { 259 Segment_2 s_sweep = K.construct_segment(p_sweep,p_sweep); 260 seg_pair sp(s_sweep, ite); 261 sit_succ = YS.locate( &sp ); 262 if ( sit_succ != YS.max_item() && 263 orientation(sit_succ,p_sweep) == 0 ) 264 sit = sit_succ; 265 else { 266 sit_pred = YS.pred(sit_succ); 267 sit_pred_succ = sit_succ; 268 } 269 CGAL_NEF_TRACEN("looked up p_sweep "<<PIS(YS.key(sit_succ))); 270 } 271 272 273 274 /* If no segment contains p_sweep then sit_pred and sit_succ are 275 correctly set after the above locate operation, if a segment 276 contains p_sweep sit_pred and sit_succ are set below when 277 determining the bundle.*/ 278 279 if (sit != nil) { // key(sit) is an ending or passing segment 280 CGAL_NEF_TRACEN("ending/passing segs"); 281 while ( YS.inf(sit) == event || 282 YS.inf(sit) == YS.succ(sit) ) // overlapping 283 sit = YS.succ(sit); 284 sit_succ = YS.succ(sit); 285 ST_item sit_last = sit; 286 287 ST_item xit = YS.inf(sit_last); 288 if (xit) { 289 ISegment s1 = YS.key(sit_last); 290 ISegment s2 = YS.key(sit_succ); 291 IEvent(s1,s2) = xit; 292 CGAL_NEF_TRACEN("hashing "<<PIS(s1)<<PIS(s2)<<xit); 293 } 294 295 bool overlapping; 296 do { 297 ISegment s = YS.key(sit); 298 ST_item sit_next = YS.pred(sit); 299 overlapping = (YS.inf(sit_next) == sit); 300 Halfedge_handle e = Edge_of[sit]; 301 if ( !overlapping ) { 302 CGAL_NEF_TRACEN("connecting edge to node "<<PIS(s)<<" "<<sit); 303 GO.link_as_target_and_append(v,e); 304 } 305 GO.supporting_segment(e,original(s)); 306 if ( target(s) == p_sweep ) { // ending segment 307 CGAL_NEF_TRACEN("ending segment "<<PIS(s)); 308 if ( overlapping ) 309 YS.change_inf(sit_next,YS.inf(sit)); 310 YS.del_item(sit); 311 GO.ending_segment(v,original(s)); 312 } else { // passing segment 313 CGAL_NEF_TRACEN("passing segment "<<PIS(s)); 314 if ( YS.inf(sit) != YS.succ(sit) ) 315 YS.change_inf(sit, ST_item(0)); 316 GO.passing_segment(v,original(s)); 317 } 318 sit = sit_next; 319 } 320 while ( YS.inf(sit) == event || overlapping || 321 YS.inf(sit) == YS.succ(sit) ); 322 323 sit_pred = sit; 324 sit_first = sit_pred_succ = YS.succ(sit_pred); // first item of bundle 325 326 CGAL_NEF_TRACE("event bundles between\n "<<PIS(YS.key(sit_succ))); 327 CGAL_NEF_TRACEN("\n "<<PIS(YS.key(sit_pred))); 328 329 while ( sit != sit_succ ) { 330 ST_item sub_first = sit; 331 ST_item sub_last = sub_first; 332 333 while (YS.inf(sub_last) == YS.succ(sub_last)) 334 sub_last = YS.succ(sub_last); 335 336 if (sub_last != sub_first) 337 YS.reverse_items(sub_first, sub_last); 338 339 sit = YS.succ(sub_first); 340 } 341 342 // reverse the entire bundle 343 if (sit_first != sit_succ) 344 YS.reverse_items(YS.succ(sit_pred),YS.pred(sit_succ)); 345 346 347 } // if (sit != nil) 348 349 CGAL_assertion(sit_pred); 350 GO.halfedge_below(v,Edge_of[sit_pred]); 351 if ( Isos_of[event] != 0 ) { 352 const IsoList& IL = *(Isos_of[event]); 353 slist_item iso_it; 354 for (iso_it = IL.first(); iso_it; iso_it=IL.succ(iso_it) ) 355 GO.trivial_segment(v,IL[iso_it] ); 356 delete (Isos_of[event]); // clean up the list 357 } 358 359 360 ISegment next_seg; 361 CGAL_LEDA_SCOPE::pq_item next_it = SQ.find_min(); 362 while ( next_it && 363 (next_seg = SQ.inf(next_it), p_sweep == source(next_seg)) ) { 364 ST_item s_sit = YS.locate_succ(next_seg); 365 ST_item p_sit = YS.pred(s_sit); 366 367 CGAL_NEF_TRACEN("inserting "<<PIS(next_seg)<<" at "<<PIS(YS.key(s_sit))); 368 if ( YS.max_item() != s_sit && 369 orientation(s_sit, source(next_seg) ) == 0 && 370 orientation(s_sit, target(next_seg) ) == 0 ) 371 sit = YS.insert_at(s_sit, next_seg, s_sit); 372 else 373 sit = YS.insert_at(s_sit, next_seg, ST_item(nil)); 374 CGAL_assertion(YS.succ(sit)==s_sit); 375 376 if ( YS.min_item() != p_sit && 377 orientation(p_sit, source(next_seg) ) == 0 && 378 orientation(p_sit, target(next_seg) ) == 0 ) 379 YS.change_inf(p_sit, sit); 380 CGAL_assertion(YS.succ(p_sit)==sit); 381 382 XS.insert(target(next_seg), sit); 383 GO.starting_segment(v,original(next_seg)); 384 385 // delete minimum and assign new minimum to next_seg 386 SQ.del_min(); 387 next_it = SQ.find_min(); 388 } 389 390 for( ST_item sitl = YS.pred(sit_succ); sitl != sit_pred; 391 sitl = YS.pred(sitl) ) { 392 if ( YS.inf(sitl) != YS.succ(sitl) ) { // non-overlapping 393 CGAL_NEF_TRACEN("non-overlapping "<<PIS(YS.key(sitl))<<" "<<sitl); 394 Edge_of[sitl] = GO.new_halfedge_pair_at_source(v); 395 } else { 396 CGAL_NEF_TRACEN("overlapping "<<PIS(YS.key(sitl))); 397 Edge_of[sitl] = Edge_of[ YS.succ(sitl) ]; 398 } 399 } 400 sit_first = YS.succ(sit_pred); 401 402 403 CGAL_assertion(sit_pred); CGAL_assertion(sit_pred_succ); 404 ST_item xit = YS.inf(sit_pred); 405 if ( xit ) { 406 ISegment s1 = YS.key(sit_pred); 407 ISegment s2 = YS.key(sit_pred_succ); 408 IEvent(s1,s2) = xit; 409 CGAL_NEF_TRACEN("hashing "<<PIS(s1)<<PIS(s2)<<xit); 410 YS.change_inf(sit_pred, ST_item(0)); 411 } 412 413 compute_intersection(sit_pred); 414 sit = YS.pred(sit_succ); 415 if (sit != sit_pred) 416 compute_intersection(sit); 417 418 419 } 420 complete_structures()421 void complete_structures() {} check_invariants()422 void check_invariants() {CGAL_NEF_TRACEN("check_invariants\n"<<dump_structures());} check_final()423 void check_final() {} 424 425 }; // leda_seg_overlay_traits 426 427 } // namespace CGAL 428 429 #endif // defined(CGAL_USE_LEDA_LIBRARY) 430 #if !defined(CGAL_USE_LEDA_LIBRARY) 431 #include <list> 432 #include <string> 433 #include <sstream> 434 #include <map> 435 #include <CGAL/Multiset.h> 436 #include <CGAL/Unique_hash_map.h> 437 438 namespace CGAL { 439 440 template <typename IT, typename PMDEC, typename GEOM> 441 class stl_seg_overlay_traits { 442 public: 443 typedef IT ITERATOR; 444 typedef std::pair<IT,IT> INPUT; 445 typedef PMDEC OUTPUT; 446 typedef typename PMDEC::Vertex_handle Vertex_handle; 447 typedef typename PMDEC::Halfedge_handle Halfedge_handle; 448 typedef GEOM GEOMETRY; 449 typedef typename GEOMETRY::Point_2 Point_2; 450 typedef typename GEOMETRY::Segment_2 Segment_2; 451 452 typedef std::pair<Segment_2,ITERATOR> seg_pair; 453 typedef seg_pair* ISegment; 454 typedef std::list<seg_pair> IList; 455 typedef typename IList::const_iterator ilist_iterator; 456 457 458 // types interfacing the generic sweep frame 459 ITERATOR its, ite; 460 OUTPUT& GO; 461 const GEOMETRY& K; 462 463 class compare_segs_at_sweepline 464 { 465 const Point_2& p; 466 ISegment s_bottom, s_top; // sentinel segments 467 const GEOMETRY& K; 468 o2c(int o)469 CGAL::Comparison_result o2c(int o) const { 470 if(o > 0) return CGAL::LARGER; 471 if(o < 0) return CGAL::SMALLER; 472 return CGAL::EQUAL; 473 } 474 475 public: compare_segs_at_sweepline(const Point_2 & pi,ISegment s1,ISegment s2,const GEOMETRY & k)476 compare_segs_at_sweepline(const Point_2& pi, 477 ISegment s1, ISegment s2, 478 const GEOMETRY& k) 479 : p(pi), s_bottom(s1), s_top(s2), K(k) 480 {} 481 compare_segs_at_sweepline(const compare_segs_at_sweepline & lt)482 compare_segs_at_sweepline(const compare_segs_at_sweepline& lt) 483 : p(lt.p), s_bottom(lt.s_bottom), s_top(lt.s_top), K(lt.K) 484 {} 485 486 template <typename ss_pair> 487 bool operator()488 operator()(const ISegment& is1, const ss_pair& ss2) const 489 { 490 return operator()(is1, ss2.first); 491 } 492 493 CGAL::Comparison_result operator()494 operator()(const ISegment& is1, const ISegment& is2) const 495 { 496 if ( is2 == s_top || is1 == s_bottom ) return CGAL::SMALLER; 497 if ( is1 == s_top || is2 == s_bottom ) return CGAL::LARGER; 498 if ( is1 == is2 ) return CGAL::EQUAL; 499 // Precondition: p is contained in s1 or s2. 500 const Segment_2& s1 = is1->first; 501 const Segment_2& s2 = is2->first; 502 503 int s = -K.orientation(s1,p); 504 if ( s == 0 ) 505 s = K.orientation(s2,p); 506 else 507 CGAL_assertion_msg( K.orientation(s2,p) == 0, "compare error in sweep."); 508 509 if( s || K.is_degenerate(s2) || K.is_degenerate(s1)) 510 return o2c(s); 511 512 return o2c(K.orientation(s2,K.target(s1))); 513 } 514 }; 515 516 class compare_pnts_xy { 517 const GEOMETRY& K; 518 519 public: compare_pnts_xy(const GEOMETRY & k)520 compare_pnts_xy(const GEOMETRY& k) 521 : K(k) 522 {} 523 compare_pnts_xy(const compare_pnts_xy & lt)524 compare_pnts_xy(const compare_pnts_xy& lt) 525 : K(lt.K) 526 {} 527 528 CGAL::Comparison_result operator()529 operator()(const Point_2& p1, const Point_2& p2) const 530 { 531 int c = K.compare_xy(p1,p2); 532 if(c < 0) return CGAL::SMALLER; 533 if(c > 0) return CGAL::LARGER; 534 return CGAL::EQUAL; 535 } 536 }; 537 538 struct lt_pnts_xy { 539 const GEOMETRY& K; 540 541 public: lt_pnts_xylt_pnts_xy542 lt_pnts_xy(const GEOMETRY& k) 543 : K(k) 544 {} 545 lt_pnts_xylt_pnts_xy546 lt_pnts_xy(const lt_pnts_xy& lt) 547 : K(lt.K) 548 {} 549 550 bool operatorlt_pnts_xy551 operator()(const Point_2& p1, const Point_2& p2) const 552 { 553 return K.compare_xy(p1,p2) < 0; 554 } 555 }; 556 557 typedef std::list<ITERATOR> IsoList; 558 typedef CGAL::Multiset<Point_2, compare_pnts_xy> EventQueue; 559 typedef typename EventQueue::iterator event_iterator; 560 typedef Unique_hash_map<Point_2*, IsoList*> X2iso; 561 562 typedef CGAL::Multiset<ISegment, compare_segs_at_sweepline> SweepStatus; 563 typedef typename SweepStatus::iterator ss_iterator; 564 typedef typename SweepStatus::const_iterator ss_const_iterator; 565 typedef CGAL::Unique_hash_map<ISegment, event_iterator> Y2X; 566 typedef CGAL::Unique_hash_map<ISegment, ISegment> Y2Y; 567 typedef CGAL::Unique_hash_map<Point_2*, ss_iterator> X2Y; 568 typedef CGAL::Unique_hash_map<ISegment, Halfedge_handle> AssocEdgeMap; 569 570 typedef std::pair<ISegment,ISegment> is_pair; 571 572 struct lt_ssi_pair { 573 574 public: lt_ssi_pairlt_ssi_pair575 lt_ssi_pair() {} operatorlt_ssi_pair576 bool operator()(const is_pair& s0, const is_pair& s1) const { 577 if(s0.second == s1.second) 578 return s0.first < s1.first; 579 return s0.second < s1.second; 580 } 581 }; 582 583 typedef std::map<is_pair, event_iterator, lt_ssi_pair> EventHash; 584 585 typedef std::multimap<Point_2, ISegment, lt_pnts_xy> SegQueue; 586 typedef typename SegQueue::iterator seg_iterator; 587 typedef typename SegQueue::value_type ps_pair; 588 589 event_iterator event; 590 Point_2 p_sweep; 591 EventQueue XS; 592 seg_pair sl,sh; 593 compare_segs_at_sweepline SLcmp; 594 SweepStatus YS; 595 Y2X y2x; 596 X2Y x2y; 597 X2iso x2iso; 598 Y2Y y2y; 599 SegQueue SQ; 600 IList Internal; 601 AssocEdgeMap Edge_of; 602 EventHash IEvent; 603 stl_seg_overlay_traits(const INPUT & in,OUTPUT & G,const GEOMETRY & k)604 stl_seg_overlay_traits(const INPUT& in, OUTPUT& G, const GEOMETRY& k) 605 : its(in.first), ite(in.second), GO(G), K(k), 606 XS(compare_pnts_xy(K)), SLcmp(p_sweep,&sl,&sh,K), YS(SLcmp), 607 y2x(XS.end()), x2y(YS.end()), x2iso(0), y2y(&sl), 608 SQ(lt_pnts_xy(K)), Edge_of(0) 609 {} 610 dump_structures()611 std::string dump_structures() 612 { 613 std::ostringstream out; 614 out << "EventQueue:\n"; 615 typename EventQueue::const_iterator sit1; 616 for(sit1 = XS.begin(); sit1 != XS.end(); ++sit1) 617 out << " " << *sit1 << std::endl; 618 619 out << "SegQueue:\n"; 620 typename SegQueue::const_iterator sit2; 621 for(sit2 = SQ.begin(); sit2 != SQ.end(); ++sit2) 622 out << " " << sit2->first << " " << sit2->second 623 << " " << sit2->first << std::endl; 624 625 out << "SweepStatus:\n"; 626 typename SweepStatus::iterator sit3; 627 for( sit3 = YS.begin(); *sit3 != &sh; ++sit3 ) { 628 int b = orientation(sit3, p_sweep); 629 if(*sit3 == &sl) out << " 1"; 630 else if(*sit3 == &sh) out <<"-1"; 631 else if(b >= 0) out << " " << b; 632 else out << b; 633 out << " " << *sit3 << ": "; 634 // if(y2x[*sit3] != XS.end()) 635 // out << *y2x[*sit3]; 636 // out << " | "; 637 out << (*sit3)->first; 638 if(y2y[*sit3] != &sl) 639 out << " y2y: " << y2y[*sit3]; 640 out << std::endl; 641 } 642 return out.str(); 643 } 644 check_bundle(ss_iterator pred,ss_iterator succ)645 bool check_bundle(ss_iterator pred, 646 ss_iterator succ) { 647 CGAL_NEF_TRACEN("check bundle"); 648 649 check_invariants(); 650 651 CGAL_assertion(*pred == &sl || 652 orientation(pred, p_sweep) > 0); 653 ++pred; 654 while(*pred != *succ) { 655 CGAL_assertion(orientation(pred, p_sweep) == 0); 656 ss_iterator next(pred); 657 ++next; 658 if(*pred != &sl && 659 *next != &sh) { 660 bool b1 = orientation(pred, K.source((*next)->first)) == 0; 661 b1 &= orientation(pred, K.target((*next)->first)) == 0; 662 b1 &= orientation(next, K.source((*pred)->first)) == 0; 663 b1 &= orientation(next, K.target((*pred)->first)) == 0; 664 CGAL_warning(b1 == (y2y[*pred] == *next)); 665 } 666 ++pred; 667 } 668 CGAL_assertion(*succ == &sh || 669 orientation(succ, p_sweep) < 0); 670 671 return true; 672 } 673 source(ISegment is)674 Point_2 source(ISegment is) const 675 { return K.source(is->first); } target(ISegment is)676 Point_2 target(ISegment is) const 677 { return K.target(is->first); } 678 original(ISegment s)679 ITERATOR original(ISegment s) const 680 { return s->second; } 681 orientation(ss_iterator sit,const Point_2 & p)682 int orientation(ss_iterator sit, const Point_2& p) const 683 { return K.orientation((*sit)->first,p); } 684 collinear(ss_iterator sit1,ss_iterator sit2)685 bool collinear(ss_iterator sit1, ss_iterator sit2) const 686 { if( *sit1 == &sl || 687 *sit1 == &sh || 688 *sit2 == &sl || 689 *sit2 == &sh) return false; 690 Point_2 ps = source(*sit2), pt = target(*sit2); 691 return ( orientation(sit1,ps)==0 && 692 orientation(sit1,pt)==0 ); 693 } 694 insertXS(const Point_2 & p)695 event_iterator insertXS(const Point_2& p) { 696 event_iterator upper = XS.upper_bound(p); 697 if(upper == XS.begin()) 698 return XS.insert_before(upper, p); 699 event_iterator pred = upper; --pred; 700 if(K.compare_xy(*pred, p) == CGAL::SMALLER) 701 return XS.insert_before(upper, p); 702 return pred; 703 } 704 compute_intersection(ss_iterator sit0)705 void compute_intersection(ss_iterator sit0) 706 { 707 // Given an item |sit0| in the Y-structure compute the point of 708 // intersection with its successor and (if existing) insert it into 709 // the event queue and do all necessary updates. 710 ss_iterator sit1 = sit0; ++sit1; 711 CGAL_NEF_TRACEN("compute_intersection "<< *sit0 <<" "<< *sit1); 712 if ( *sit0 == &sl || *sit1 == &sh ) return; 713 const Segment_2& s0 = (*sit0)->first; 714 const Segment_2& s1 = (*sit1)->first; 715 int or0 = K.orientation(s0,K.target(s1)); 716 int or1 = K.orientation(s1,K.target(s0)); 717 if ( or0 <= 0 && or1 >= 0 ) { 718 event_iterator it = 719 IEvent[std::make_pair(*sit0, *sit1)]; 720 if(it == event_iterator()) { 721 Point_2 q = K.intersection(s0,s1); 722 event_iterator er = insertXS(q); // only done if none existed!!! 723 x2y[&*er] = sit0; 724 y2x[*sit0] = er; 725 CGAL_assertion(sit0 != YS.end()); 726 } else { 727 CGAL_NEF_TRACEN(" intersection has been found previously"); 728 y2x[*sit0] = it; 729 } 730 } 731 } 732 initialize_structures()733 void initialize_structures() 734 { 735 /* INITIALIZATION 736 - insert all vertices into the x-structure 737 - insert sentinels into y-structure 738 - exploit the fact that insert operations into the x-structure 739 leave previously inserted points unchanged to achieve that 740 any pair of endpoints $p$ and $q$ with |p == q| are identical 741 */ 742 CGAL_NEF_TRACEN("initialize_structures"); 743 744 ITERATOR it_s; 745 for ( it_s=its; it_s != ite; ++it_s ) { 746 const Segment_2& s = *it_s; 747 event_iterator it1, it2, upper; 748 749 if(XS.empty()) 750 it1 = XS.insert(K.source(s)); 751 else 752 it1 = insertXS(K.source(s)); 753 it2 = insertXS(K.target(s)); 754 755 if (it1 == it2) { 756 if ( x2iso[&*it1] == 0 ) x2iso[&*it1] = new IsoList; 757 x2iso[&*it1]->push_front(it_s); 758 continue; // ignore zero-length segments regarding YS 759 } 760 761 Point_2 p = *it1; 762 Point_2 q = *it2; 763 764 Segment_2 s1; 765 if ( K.compare_xy(p,q) < 0 ) 766 s1 = K.construct_segment(p,q); 767 else 768 s1 = K.construct_segment(q,p); 769 770 Internal.push_back(seg_pair(s1,it_s)); 771 SQ.insert(ps_pair(K.source(s1),&Internal.back())); 772 } 773 774 // insert a lower and an upper sentinel segment to avoid special 775 // cases when traversing the Y-structure 776 YS.insert(&sl); 777 YS.insert(&sh); 778 CGAL_NEF_TRACEN("end of initialization\n"); 779 } 780 781 event_exists()782 bool event_exists() 783 { 784 if (!XS.empty()) { 785 // event is set at end of loop and in init 786 event = XS.begin(); 787 p_sweep = *event; 788 return true; 789 } 790 return false; 791 } 792 procede_to_next_event()793 void procede_to_next_event() 794 { XS.erase(event); } 795 process_event()796 void process_event() 797 { 798 CGAL_NEF_TRACEN("\n\n >>> process_event: "<<p_sweep); 799 800 Vertex_handle v = GO.new_vertex(p_sweep); 801 ss_iterator sit = x2y[&*event]; 802 ss_iterator sit_succ, sit_pred, sit_first, sit_pred_succ; 803 804 if(sit == YS.end()) { 805 CGAL_NEF_TRACEN("search for upper bound in YS"); 806 Segment_2 s_sweep = K.construct_segment(p_sweep,p_sweep); 807 seg_pair sp(s_sweep, ite); 808 sit_succ = YS.upper_bound(&sp); 809 sit = sit_succ; 810 --sit; 811 CGAL_NEF_TRACEN("upper bound: " << *sit_succ); 812 if(*sit == &sl || 813 orientation(sit, p_sweep) != 0) { 814 sit_pred_succ = sit_succ; 815 sit_pred = sit; 816 sit = YS.end(); 817 } 818 } 819 820 /* |sit| is determined by upper bounding the search for the 821 segment (p_sweep,p_sweep) and taking its predecessor. 822 if the segment associated to |sit| contains |p_sweep| then 823 there's a bundle of segments containing |p_sweep|. 824 We compute the successor (|sit_succ)|) and 825 predecessor (|sit_pred|) items. */ 826 827 828 /* If no segments contain p_sweep then sit_pred and sit_succ are 829 correctly set after the above locate operation, if a segment 830 contains p_sweep sit_pred and sit_succ are set below when 831 determining the bundle.*/ 832 833 if (sit != YS.end() ) { // sit->first is ending or passing segment 834 CGAL_NEF_TRACEN("ending/passing segs " << *sit); 835 sit_succ = sit; ++sit_succ; 836 837 while ( y2x[*sit] == event || 838 y2y[*sit] == *sit_succ ) { // overlapping 839 sit = sit_succ; 840 ++sit_succ; 841 } 842 CGAL_NEF_TRACEN("ending/passing segs " << *sit); 843 844 ss_iterator sit_last = sit; 845 846 event_iterator xit = y2x[*sit_last]; 847 if (xit != XS.end() && 848 *sit_last != &sl && 849 *sit_succ != &sh) { 850 IEvent[std::make_pair(*sit_last, *sit_succ)] = xit; 851 } 852 853 bool overlapping; 854 do { 855 ISegment s = *sit; 856 ss_iterator sit_next(sit); --sit_next; 857 858 if(*sit_next == &sl) 859 overlapping = false; 860 else 861 overlapping = y2y[*sit_next] == *sit; 862 Halfedge_handle e = Edge_of[*sit]; 863 if ( overlapping ) { 864 CGAL_NEF_TRACEN("overlapping segment "<<s); 865 } else { 866 CGAL_NEF_TRACEN("connecting edge to node "<<s); 867 GO.link_as_target_and_append(v,e); 868 /* in this case we close the output edge |e| associated to 869 |sit| by linking |v| as its target and by appending the 870 twin edge to |v|'s adjacency list. */ 871 } 872 GO.supporting_segment(e,original(s)); 873 if ( target(s) == p_sweep ) { 874 CGAL_NEF_TRACEN("ending segment "<<s); 875 if(overlapping) 876 y2y[*sit_next] = y2y[*sit]; 877 YS.erase(sit); 878 GO.ending_segment(v,original(s)); 879 } else { // passing segment, take care of the node here! 880 CGAL_NEF_TRACEN("passing segment "<<s); 881 ss_iterator sst(sit); ++sst; 882 if(y2y[*sit] != *sst) 883 y2y[*sit] = &sl; 884 y2x[*sit] = XS.end(); 885 GO.passing_segment(v,original(s)); 886 } 887 888 ss_iterator sss(sit_next); ++sss; 889 if(*sit_next != &sl) 890 overlapping |= (y2y[*sit_next] == *sss); 891 892 sit = sit_next; 893 } 894 while (*sit != &sl && 895 (y2x[*sit] == event || overlapping)); 896 897 898 sit_pred = sit; 899 sit_first = sit_pred; 900 ++sit_first; // first item of the bundle 901 sit_pred_succ = sit_first; 902 903 CGAL_NEF_TRACE("event bundles between\n "<< *sit_succ); 904 CGAL_NEF_TRACEN("\n "<< *sit_pred); 905 906 CGAL_assertion(check_bundle(sit_pred, sit_succ)); 907 908 while( *sit != *sit_succ) { 909 ss_iterator sub_first(sit), 910 sub_last(sub_first), 911 succ_sub_last(sub_last); 912 ++succ_sub_last; 913 914 while(y2y[*sub_last] == *succ_sub_last) { 915 ++sub_last; ++succ_sub_last; 916 } 917 918 sit = sub_first; 919 while(*sub_first != *sub_last) { 920 YS.swap(sub_first, sub_last); 921 std::swap(sub_first, sub_last); 922 ++sub_first; 923 if(*sub_first == *sub_last) break; 924 --sub_last; 925 } 926 ++sit; 927 } 928 929 if(*sit_first != *sit_succ) { 930 ss_iterator sfirst(sit_pred); ++sfirst; 931 ss_iterator slast(sit_succ); --slast; 932 while(*sfirst != *slast) { 933 YS.swap(sfirst, slast); 934 std::swap(sfirst, slast); 935 ++sfirst; 936 if(*sfirst == *slast) break; 937 --slast; 938 } 939 } 940 } // if (sit != ss_iterator() ) 941 942 // CGAL_assertion( sit_pred != YS.end() ); 943 GO.halfedge_below(v,Edge_of[*sit_pred]); 944 if ( x2iso[&*event] != 0 ) { 945 IsoList* IL = x2iso[&*event]; 946 typename IsoList::const_iterator iso_it; 947 for (iso_it = IL->begin(); iso_it != IL->end(); ++iso_it) 948 GO.trivial_segment(v,*iso_it); 949 delete IL; 950 x2iso[&*event] = 0; 951 } 952 953 ISegment next_seg = ISegment(); // to avoid /W4 warning 954 seg_iterator next_it = SQ.begin(); 955 while ( next_it != SQ.end() && 956 ( next_seg = next_it->second, p_sweep == source(next_seg)) ) { 957 CGAL_NEF_TRACEN("inserting "<<next_seg); 958 959 ss_iterator s_sit = YS.upper_bound(next_seg); 960 ss_iterator p_sit(s_sit); --p_sit; 961 962 sit = YS.insert_before(s_sit, next_seg); 963 964 ss_iterator ys2_tmp = sit; 965 ++ys2_tmp; 966 CGAL_assertion(*s_sit == *ys2_tmp); 967 968 if(*s_sit != &sh && 969 orientation(s_sit, source(next_seg)) == 0 && 970 orientation(s_sit, target(next_seg)) == 0) { 971 y2y[*sit] = *s_sit; 972 } 973 974 if ( &sl != *p_sit && 975 orientation(p_sit, source(next_seg) ) == 0 && 976 orientation(p_sit, target(next_seg) ) == 0 ) { 977 y2y[*p_sit] = *sit; 978 } 979 980 x2y[&*XS.find(target(next_seg))] = sit; 981 GO.starting_segment(v,original(next_seg)); 982 983 // delete minimum and assign new minimum to next_seg 984 SQ.erase(SQ.begin()); 985 next_it = SQ.begin(); 986 } 987 988 // we insert new edge stubs, non-linked at target 989 ss_iterator sit_curr = sit_succ, sit_prev = sit_succ; 990 for( --sit_curr; *sit_curr != *sit_pred; 991 sit_prev = sit_curr, --sit_curr ) { 992 CGAL_NEF_TRACEN("checking outedge "<< *sit_curr <<"\n "<< *sit_prev); 993 if (y2y[*sit_curr] == *sit_prev) { // overlapping 994 CGAL_assertion(collinear(sit_curr, sit_prev)); 995 Edge_of[*sit_curr] = Edge_of[*sit_prev]; 996 } else { 997 CGAL_NEF_TRACEN("creating new edge "); 998 Edge_of[*sit_curr] = GO.new_halfedge_pair_at_source(v); 999 } 1000 } 1001 sit_first = sit_prev; 1002 1003 event_iterator xxit = y2x[*sit_pred]; 1004 if(xxit != XS.end() && 1005 *sit_pred != &sl && 1006 *sit_pred_succ != &sh) { 1007 IEvent[std::make_pair(*sit_pred, *sit_pred_succ)] = xxit; 1008 y2y[*sit_pred] = &sl; 1009 y2x[*sit_pred] = XS.end(); 1010 } 1011 1012 CGAL_NEF_TRACEN("pred,succ = "<< *sit_pred <<" "<< *sit_succ); 1013 compute_intersection(sit_pred); 1014 sit = sit_succ; --sit; 1015 if (*sit != *sit_pred) 1016 compute_intersection(sit); 1017 } 1018 complete_structures()1019 void complete_structures() {} check_invariants()1020 void check_invariants() {CGAL_NEF_TRACEN("check_invariants\n"<<dump_structures());} check_final()1021 void check_final() {} 1022 1023 1024 }; // stl_seg_overlay_traits 1025 1026 } // namespace CGAL 1027 1028 #endif // !defined(CGAL_USE_LEDA_LIBRARY) 1029 1030 namespace CGAL { 1031 #if defined(CGAL_USE_LEDA_LIBRARY) 1032 #define Segment_overlay_traits leda_seg_overlay_traits 1033 static const char* const sweepversion = "LEDA segment overlay sweep"; 1034 #else 1035 #define Segment_overlay_traits stl_seg_overlay_traits 1036 static const char* const sweepversion = "STL segment overlay sweep"; 1037 #endif 1038 } // namespace CGAL 1039 1040 #include <CGAL/generic_sweep.h> 1041 #endif // CGAL_SEGMENT_OVERLAY_TRAITS_H 1042