1 /************************************************************** 2 * 3 * Licensed to the Apache Software Foundation (ASF) under one 4 * or more contributor license agreements. See the NOTICE file 5 * distributed with this work for additional information 6 * regarding copyright ownership. The ASF licenses this file 7 * to you under the Apache License, Version 2.0 (the 8 * "License"); you may not use this file except in compliance 9 * with the License. You may obtain a copy of the License at 10 * 11 * http://www.apache.org/licenses/LICENSE-2.0 12 * 13 * Unless required by applicable law or agreed to in writing, 14 * software distributed under the License is distributed on an 15 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 16 * KIND, either express or implied. See the License for the 17 * specific language governing permissions and limitations 18 * under the License. 19 * 20 *************************************************************/ 21 22 23 24 // MARKER(update_precomp.py): autogen include statement, do not remove 25 #include "precompiled_basegfx.hxx" 26 27 #include <rtl/math.hxx> 28 29 #include <basegfx/tuple/b2dtuple.hxx> 30 #include <basegfx/range/b2drange.hxx> 31 #include <basegfx/range/b2dpolyrange.hxx> 32 #include <basegfx/polygon/b2dpolypolygon.hxx> 33 #include <basegfx/polygon/b2dpolygontools.hxx> 34 #include <basegfx/polygon/b2dpolypolygontools.hxx> 35 36 #include <o3tl/vector_pool.hxx> 37 #include <boost/bind.hpp> 38 #include <boost/utility.hpp> 39 40 #include <algorithm> 41 #include <deque> 42 #include <list> 43 44 45 namespace basegfx 46 { 47 namespace 48 { 49 // Generating a poly-polygon from a bunch of rectangles 50 // 51 // Helper functionality for sweep-line algorithm 52 // ==================================================== 53 54 typedef std::vector<B2DRange> VectorOfRanges; 55 56 class ImplPolygon; 57 typedef o3tl::vector_pool<ImplPolygon> VectorOfPolygons; 58 59 60 /** This class represents an active edge 61 62 As the sweep line traverses across the overall area, 63 rectangle edges parallel to it generate events, and 64 rectangle edges orthogonal to it generate active 65 edges. This class represents the latter. 66 */ 67 class ActiveEdge 68 { 69 public: 70 /** The two possible active rectangle edges differ by one 71 coordinate value - the upper edge has the lower, the 72 lower edge the higher value. 73 */ 74 enum EdgeType { 75 /// edge with lower coordinate value 76 UPPER=0, 77 /// edge with higher coordinate value 78 LOWER=1 79 }; 80 81 enum EdgeDirection { 82 /// edge proceeds to the left 83 PROCEED_LEFT=0, 84 /// edge proceeds to the right 85 PROCEED_RIGHT=1 86 }; 87 88 /** Create active edge 89 90 @param rRect 91 Rectangle this edge is part of 92 93 @param fInvariantCoord 94 The invariant ccordinate value of this edge 95 96 @param eEdgeType 97 Is fInvariantCoord the lower or the higher value, for 98 this rect? 99 */ 100 ActiveEdge( const B2DRectangle& rRect, 101 const double& fInvariantCoord, 102 std::ptrdiff_t nPolyIdx, 103 EdgeType eEdgeType, 104 EdgeDirection eEdgeDirection ) : 105 mfInvariantCoord(fInvariantCoord), 106 mpAssociatedRect( &rRect ), 107 mnPolygonIdx( nPolyIdx ), 108 meEdgeType( eEdgeType ), 109 meEdgeDirection( eEdgeDirection ) 110 {} 111 112 double getInvariantCoord() const { return mfInvariantCoord; } 113 const B2DRectangle& getRect() const { return *mpAssociatedRect; } 114 std::ptrdiff_t getTargetPolygonIndex() const { return mnPolygonIdx; } 115 void setTargetPolygonIndex( std::ptrdiff_t nIdx ) { mnPolygonIdx = nIdx; } 116 EdgeType getEdgeType() const { return meEdgeType; } 117 EdgeDirection getEdgeDirection() const { return meEdgeDirection; } 118 119 /// For STL sort 120 bool operator<( const ActiveEdge& rRHS ) const { return mfInvariantCoord < rRHS.mfInvariantCoord; } 121 122 private: 123 /** The invariant coordinate value of this edge (e.g. the 124 common y value, for a horizontal edge) 125 */ 126 double mfInvariantCoord; 127 128 /** Associated rectangle 129 130 This on the one hand saves some storage space (the 131 vector of rectangles is persistent, anyway), and on 132 the other hand provides an identifier to match active 133 edges and x events (see below) 134 135 Ptr because class needs to be assignable 136 */ 137 const B2DRectangle* mpAssociatedRect; 138 139 /** Index of the polygon this edge is currently involved 140 with. 141 142 Note that this can change for some kinds of edge 143 intersection, as the algorithm tends to swap 144 associated polygons there. 145 146 -1 denotes no assigned polygon 147 */ 148 std::ptrdiff_t mnPolygonIdx; 149 150 /// 'upper' or 'lower' edge of original rectangle. 151 EdgeType meEdgeType; 152 153 /// 'left' or 'right' 154 EdgeDirection meEdgeDirection; 155 }; 156 157 // Needs to be list - various places hold ptrs to elements 158 typedef std::list< ActiveEdge > ListOfEdges; 159 160 161 /** Element of the sweep line event list 162 163 As the sweep line traverses across the overall area, 164 rectangle edges parallel to it generate events, and 165 rectangle edges orthogonal to it generate active 166 edges. This class represents the former. 167 168 The class defines an element of the sweep line list. The 169 sweep line's position jumps in steps defined by the 170 coordinates of the sorted SweepLineEvent entries. 171 */ 172 class SweepLineEvent 173 { 174 public: 175 /** The two possible sweep line rectangle edges differ by 176 one coordinate value - the starting edge has the 177 lower, the finishing edge the higher value. 178 */ 179 enum EdgeType { 180 /// edge with lower coordinate value 181 STARTING_EDGE=0, 182 /// edge with higher coordinate value 183 FINISHING_EDGE=1 184 }; 185 186 /** The two possible sweep line directions 187 */ 188 enum EdgeDirection { 189 PROCEED_UP=0, 190 PROCEED_DOWN=1 191 }; 192 193 /** Create sweep line event 194 195 @param fPos 196 Coordinate position of the event 197 198 @param rRect 199 Rectangle this event is generated for. 200 201 @param eEdgeType 202 Is fPos the lower or the higher value, for the 203 rectangle this event is generated for? 204 */ 205 SweepLineEvent( double fPos, 206 const B2DRectangle& rRect, 207 EdgeType eEdgeType, 208 EdgeDirection eDirection) : 209 mfPos( fPos ), 210 mpAssociatedRect( &rRect ), 211 meEdgeType( eEdgeType ), 212 meEdgeDirection( eDirection ) 213 {} 214 215 double getPos() const { return mfPos; } 216 const B2DRectangle& getRect() const { return *mpAssociatedRect; } 217 EdgeType getEdgeType() const { return meEdgeType; } 218 EdgeDirection getEdgeDirection() const { return meEdgeDirection; } 219 220 /// For STL sort 221 bool operator<( const SweepLineEvent& rRHS ) const { return mfPos < rRHS.mfPos; } 222 223 private: 224 /// position of the event, in the direction of the line sweep 225 double mfPos; 226 227 /** Rectangle this event is generated for 228 229 This on the one hand saves some storage space (the 230 vector of rectangles is persistent, anyway), and on 231 the other hand provides an identifier to match active 232 edges and events (see below) 233 234 Ptr because class needs to be assignable 235 */ 236 const B2DRectangle* mpAssociatedRect; 237 238 /// 'upper' or 'lower' edge of original rectangle. 239 EdgeType meEdgeType; 240 241 /// 'up' or 'down' 242 EdgeDirection meEdgeDirection; 243 }; 244 245 typedef std::vector< SweepLineEvent > VectorOfEvents; 246 247 248 /** Smart point container for B2DMultiRange::getPolyPolygon() 249 250 This class provides methods needed only here, and is used 251 as a place to store some additional information per 252 polygon. Also, most of the intersection logic is 253 implemented here. 254 */ 255 class ImplPolygon 256 { 257 public: 258 /** Create polygon 259 */ 260 ImplPolygon() : 261 mpLeadingRightEdge(NULL), 262 mnIdx(-1), 263 maPoints(), 264 mbIsFinished(false) 265 { 266 // completely ad-hoc. but what the hell. 267 maPoints.reserve(11); 268 } 269 270 void setPolygonPoolIndex( std::ptrdiff_t nIdx ) { mnIdx = nIdx; } 271 bool isFinished() const { return mbIsFinished; } 272 273 /// Add point to the end of the existing points 274 void append( const B2DPoint& rPoint ) 275 { 276 OSL_PRECOND( maPoints.empty() || 277 maPoints.back().getX() == rPoint.getX() || 278 maPoints.back().getY() == rPoint.getY(), 279 "ImplPolygon::append(): added point violates 90 degree line angle constraint!" ); 280 281 if( maPoints.empty() || 282 maPoints.back() != rPoint ) 283 { 284 // avoid duplicate points 285 maPoints.push_back( rPoint ); 286 } 287 } 288 289 /** Perform the intersection of this polygon with an 290 active edge. 291 292 @param rEvent 293 The vertical line event that generated the 294 intersection 295 296 @param rActiveEdge 297 The active edge that generated the intersection 298 299 @param rPolygonPool 300 Polygon pool, we sometimes need to allocate a new one 301 302 @param bIsFinishingEdge 303 True, when this is hitting the last edge of the 304 vertical sweep - every vertical sweep starts and ends 305 with upper and lower edge of the _same_ rectangle. 306 307 @return the new current polygon (that's the one 308 processing must proceed with, when going through the 309 list of upcoming active edges). 310 */ 311 std::ptrdiff_t intersect( SweepLineEvent& rEvent, 312 ActiveEdge& rActiveEdge, 313 VectorOfPolygons& rPolygonPool, 314 B2DPolyPolygon& rRes, 315 bool isFinishingEdge ) 316 { 317 OSL_PRECOND( !isFinished(), 318 "ImplPolygon::intersect(): called on already finished polygon!" ); 319 OSL_PRECOND( !isFinishingEdge 320 || (isFinishingEdge && &rEvent.getRect() == &rActiveEdge.getRect()), 321 "ImplPolygon::intersect(): inconsistent ending!" ); 322 323 const B2DPoint aIntersectionPoint( rEvent.getPos(), 324 rActiveEdge.getInvariantCoord() ); 325 326 // intersection point, goes to our polygon 327 // unconditionally 328 append(aIntersectionPoint); 329 330 const bool isSweepLineEnteringRect( 331 rEvent.getEdgeType() == SweepLineEvent::STARTING_EDGE); 332 if( isFinishingEdge ) 333 { 334 if( isSweepLineEnteringRect ) 335 handleFinalOwnRightEdge(rActiveEdge); 336 else 337 handleFinalOwnLeftEdge(rActiveEdge, 338 rPolygonPool, 339 rRes); 340 341 // we're done with this rect & sweep line 342 return -1; 343 } 344 else if( metOwnEdge(rEvent,rActiveEdge) ) 345 { 346 handleInitialOwnEdge(rEvent, rActiveEdge); 347 348 // point already added, all init done, continue 349 // with same poly 350 return mnIdx; 351 } 352 else 353 { 354 OSL_ENSURE( rActiveEdge.getTargetPolygonIndex() != -1, 355 "ImplPolygon::intersect(): non-trivial intersection hit empty polygon!" ); 356 357 const bool isHittingLeftEdge( 358 rActiveEdge.getEdgeDirection() == ActiveEdge::PROCEED_LEFT); 359 360 if( isHittingLeftEdge ) 361 return handleComplexLeftEdge(rActiveEdge, 362 aIntersectionPoint, 363 rPolygonPool, 364 rRes); 365 else 366 return handleComplexRightEdge(rActiveEdge, 367 aIntersectionPoint, 368 rPolygonPool); 369 } 370 } 371 372 private: 373 std::ptrdiff_t getPolygonPoolIndex() const { return mnIdx; } 374 375 void handleInitialOwnEdge(SweepLineEvent& rEvent, 376 ActiveEdge& rActiveEdge) 377 { 378 const bool isActiveEdgeProceedLeft( 379 rActiveEdge.getEdgeDirection() == ActiveEdge::PROCEED_LEFT); 380 const bool isSweepLineEnteringRect( 381 rEvent.getEdgeType() == SweepLineEvent::STARTING_EDGE); 382 (void)isActiveEdgeProceedLeft; 383 (void)isSweepLineEnteringRect; 384 385 OSL_ENSURE( isSweepLineEnteringRect == isActiveEdgeProceedLeft, 386 "ImplPolygon::intersect(): sweep initial own edge hit: wrong polygon order" ); 387 388 OSL_ENSURE( isSweepLineEnteringRect || 389 mpLeadingRightEdge == &rActiveEdge, 390 "ImplPolygon::intersect(): sweep initial own edge hit: wrong leading edge" ); 391 } 392 393 void handleFinalOwnRightEdge(ActiveEdge& rActiveEdge) 394 { 395 OSL_ENSURE( rActiveEdge.getEdgeDirection() == ActiveEdge::PROCEED_RIGHT, 396 "ImplPolygon::handleInitialOwnRightEdge(): start edge wrong polygon order" ); 397 398 rActiveEdge.setTargetPolygonIndex(mnIdx); 399 mpLeadingRightEdge = &rActiveEdge; 400 } 401 402 void handleFinalOwnLeftEdge(ActiveEdge& rActiveEdge, 403 VectorOfPolygons& rPolygonPool, 404 B2DPolyPolygon& rRes) 405 { 406 OSL_ENSURE( rActiveEdge.getEdgeDirection() == ActiveEdge::PROCEED_LEFT, 407 "ImplPolygon::handleFinalOwnLeftEdge(): end edge wrong polygon order" ); 408 409 const bool isHittingOurTail( 410 rActiveEdge.getTargetPolygonIndex() == mnIdx); 411 412 if( isHittingOurTail ) 413 finish(rRes); // just finish. no fuss. 414 else 415 { 416 // temp poly hits final left edge 417 const std::ptrdiff_t nTmpIdx=rActiveEdge.getTargetPolygonIndex(); 418 ImplPolygon& rTmp=rPolygonPool.get(nTmpIdx); 419 420 // active edge's polygon has points 421 // already. ours need to go in front of them. 422 maPoints.insert(maPoints.end(), 423 rTmp.maPoints.begin(), 424 rTmp.maPoints.end()); 425 426 // adjust leading edges, we're switching the polygon 427 ActiveEdge* const pFarEdge=rTmp.mpLeadingRightEdge; 428 429 mpLeadingRightEdge = pFarEdge; 430 pFarEdge->setTargetPolygonIndex(mnIdx); 431 432 // nTmpIdx is an empty shell, get rid of it 433 rPolygonPool.free(nTmpIdx); 434 } 435 } 436 437 std::ptrdiff_t handleComplexLeftEdge(ActiveEdge& rActiveEdge, 438 const B2DPoint& rIntersectionPoint, 439 VectorOfPolygons& rPolygonPool, 440 B2DPolyPolygon& rRes) 441 { 442 const bool isHittingOurTail( 443 rActiveEdge.getTargetPolygonIndex() == mnIdx); 444 if( isHittingOurTail ) 445 { 446 finish(rRes); 447 448 // so "this" is done - need new polygon to collect 449 // further points 450 const std::ptrdiff_t nIdxNewPolygon=rPolygonPool.alloc(); 451 rPolygonPool.get(nIdxNewPolygon).setPolygonPoolIndex(nIdxNewPolygon); 452 rPolygonPool.get(nIdxNewPolygon).append(rIntersectionPoint); 453 454 rActiveEdge.setTargetPolygonIndex(nIdxNewPolygon); 455 456 return nIdxNewPolygon; 457 } 458 else 459 { 460 const std::ptrdiff_t nTmpIdx=rActiveEdge.getTargetPolygonIndex(); 461 ImplPolygon& rTmp=rPolygonPool.get(nTmpIdx); 462 463 // active edge's polygon has points 464 // already. ours need to go in front of them. 465 maPoints.insert(maPoints.end(), 466 rTmp.maPoints.begin(), 467 rTmp.maPoints.end()); 468 469 rTmp.maPoints.clear(); 470 rTmp.append(rIntersectionPoint); 471 472 // adjust leading edges, we're switching the polygon 473 ActiveEdge* const pFarEdge=rTmp.mpLeadingRightEdge; 474 ActiveEdge* const pNearEdge=&rActiveEdge; 475 476 rTmp.mpLeadingRightEdge = NULL; 477 pNearEdge->setTargetPolygonIndex(nTmpIdx); 478 479 mpLeadingRightEdge = pFarEdge; 480 pFarEdge->setTargetPolygonIndex(mnIdx); 481 482 return nTmpIdx; 483 } 484 } 485 486 std::ptrdiff_t handleComplexRightEdge(ActiveEdge& rActiveEdge, 487 const B2DPoint& rIntersectionPoint, 488 VectorOfPolygons& rPolygonPool) 489 { 490 const std::ptrdiff_t nTmpIdx=rActiveEdge.getTargetPolygonIndex(); 491 ImplPolygon& rTmp=rPolygonPool.get(nTmpIdx); 492 493 rTmp.append(rIntersectionPoint); 494 495 rActiveEdge.setTargetPolygonIndex(mnIdx); 496 mpLeadingRightEdge = &rActiveEdge; 497 498 rTmp.mpLeadingRightEdge = NULL; 499 500 return nTmpIdx; 501 } 502 503 /// True when sweep line hits our own active edge 504 bool metOwnEdge(const SweepLineEvent& rEvent, 505 ActiveEdge& rActiveEdge) 506 { 507 const bool bHitOwnEdge=&rEvent.getRect() == &rActiveEdge.getRect(); 508 return bHitOwnEdge; 509 } 510 511 /// Retrieve B2DPolygon from this object 512 B2DPolygon getPolygon() const 513 { 514 B2DPolygon aRes; 515 std::for_each( maPoints.begin(), 516 maPoints.end(), 517 boost::bind( 518 &B2DPolygon::append, 519 boost::ref(aRes), 520 _1, 521 1 ) ); 522 aRes.setClosed( true ); 523 return aRes; 524 } 525 526 /** Finish this polygon, push to result set. 527 */ 528 void finish(B2DPolyPolygon& rRes) 529 { 530 OSL_PRECOND( maPoints.empty() || 531 maPoints.front().getX() == maPoints.back().getX() || 532 maPoints.front().getY() == maPoints.back().getY(), 533 "ImplPolygon::finish(): first and last point violate 90 degree line angle constraint!" ); 534 535 mbIsFinished = true; 536 mpLeadingRightEdge = NULL; 537 538 rRes.append(getPolygon()); 539 } 540 541 /** Refers to the current leading edge element of this 542 polygon, or NULL. The leading edge denotes the 'front' 543 of the polygon vertex sequence, i.e. the coordinates 544 at the polygon's leading edge are returned from 545 maPoints.front() 546 */ 547 ActiveEdge* mpLeadingRightEdge; 548 549 /// current index into vector pool 550 std::ptrdiff_t mnIdx; 551 552 /// Container for the actual polygon points 553 std::vector<B2DPoint> maPoints; 554 555 /// When true, this polygon is 'done', i.e. nothing must be added anymore. 556 bool mbIsFinished; 557 }; 558 559 /** Init sweep line event list 560 561 This method fills the event list with the sweep line 562 events generated from the input rectangles, and sorts them 563 with increasing x. 564 */ 565 void setupSweepLineEventListFromRanges( VectorOfEvents& o_rEventVector, 566 const std::vector<B2DRange>& rRanges, 567 const std::vector<B2VectorOrientation>& rOrientations ) 568 { 569 // we need exactly 2*rectVec.size() events: one for the 570 // left, and one for the right edge of each rectangle 571 o_rEventVector.clear(); 572 o_rEventVector.reserve( 2*rRanges.size() ); 573 574 // generate events 575 // =============== 576 577 // first pass: add all left edges in increasing order 578 std::vector<B2DRange>::const_iterator aCurrRect=rRanges.begin(); 579 std::vector<B2VectorOrientation>::const_iterator aCurrOrientation=rOrientations.begin(); 580 const std::vector<B2DRange>::const_iterator aEnd=rRanges.end(); 581 const std::vector<B2VectorOrientation>::const_iterator aEndOrientation=rOrientations.end(); 582 while( aCurrRect != aEnd && aCurrOrientation != aEndOrientation ) 583 { 584 const B2DRectangle& rCurrRect( *aCurrRect++ ); 585 586 o_rEventVector.push_back( 587 SweepLineEvent( rCurrRect.getMinX(), 588 rCurrRect, 589 SweepLineEvent::STARTING_EDGE, 590 (*aCurrOrientation++) == ORIENTATION_POSITIVE ? 591 SweepLineEvent::PROCEED_UP : SweepLineEvent::PROCEED_DOWN) ); 592 } 593 594 // second pass: add all right edges in reversed order 595 std::vector<B2DRange>::const_reverse_iterator aCurrRectR=rRanges.rbegin(); 596 std::vector<B2VectorOrientation>::const_reverse_iterator aCurrOrientationR=rOrientations.rbegin(); 597 const std::vector<B2DRange>::const_reverse_iterator aEndR=rRanges.rend(); 598 const std::vector<B2VectorOrientation>::const_reverse_iterator aEndOrientationR=rOrientations.rend(); 599 while( aCurrRectR != aEndR ) 600 { 601 const B2DRectangle& rCurrRect( *aCurrRectR++ ); 602 603 o_rEventVector.push_back( 604 SweepLineEvent( rCurrRect.getMaxX(), 605 rCurrRect, 606 SweepLineEvent::FINISHING_EDGE, 607 (*aCurrOrientationR++) == ORIENTATION_POSITIVE ? 608 SweepLineEvent::PROCEED_DOWN : SweepLineEvent::PROCEED_UP ) ); 609 } 610 611 // sort events 612 // =========== 613 614 // since we use stable_sort, the order of events with the 615 // same x value will not change. The elaborate two-pass 616 // add above thus ensures, that for each two rectangles 617 // with similar left and right x coordinates, the 618 // rectangle whose left event comes first will have its 619 // right event come last. This is advantageous for the 620 // clip algorithm below, see handleRightEdgeCrossing(). 621 622 // TODO(P3): Use radix sort (from 623 // b2dpolypolygonrasterconverter, or have your own 624 // templatized version). 625 std::stable_sort( o_rEventVector.begin(), 626 o_rEventVector.end() ); 627 } 628 629 /** Insert two active edge segments for the given rectangle. 630 631 This method creates two active edge segments from the 632 given rect, and inserts them into the active edge list, 633 such that this stays sorted (if it was before). 634 635 @param io_rEdgeList 636 Active edge list to insert into 637 638 @param io_rPolygons 639 Vector of polygons. Each rectangle added creates one 640 tentative result polygon in this vector, and the edge list 641 entries holds a reference to that polygon (this _requires_ 642 that the polygon vector does not reallocate, i.e. it must 643 have at least the maximal number of rectangles reserved) 644 645 @param o_CurrentPolygon 646 The then-current polygon when processing this sweep line 647 event 648 649 @param rCurrEvent 650 The actual event that caused this call 651 */ 652 void createActiveEdgesFromStartEvent( ListOfEdges& io_rEdgeList, 653 VectorOfPolygons& io_rPolygonPool, 654 SweepLineEvent& rCurrEvent ) 655 { 656 ListOfEdges aNewEdges; 657 const B2DRectangle& rRect=rCurrEvent.getRect(); 658 const bool bGoesDown=rCurrEvent.getEdgeDirection() == SweepLineEvent::PROCEED_DOWN; 659 660 // start event - new rect starts here, needs polygon to 661 // collect points into 662 const std::ptrdiff_t nIdxPolygon=io_rPolygonPool.alloc(); 663 io_rPolygonPool.get(nIdxPolygon).setPolygonPoolIndex(nIdxPolygon); 664 665 // upper edge 666 aNewEdges.push_back( 667 ActiveEdge( 668 rRect, 669 rRect.getMinY(), 670 bGoesDown ? nIdxPolygon : -1, 671 ActiveEdge::UPPER, 672 bGoesDown ? ActiveEdge::PROCEED_LEFT : ActiveEdge::PROCEED_RIGHT) ); 673 // lower edge 674 aNewEdges.push_back( 675 ActiveEdge( 676 rRect, 677 rRect.getMaxY(), 678 bGoesDown ? -1 : nIdxPolygon, 679 ActiveEdge::LOWER, 680 bGoesDown ? ActiveEdge::PROCEED_RIGHT : ActiveEdge::PROCEED_LEFT ) ); 681 682 // furthermore, have to respect a special tie-breaking 683 // rule here, for edges which share the same y value: 684 // newly added upper edges must be inserted _before_ any 685 // other edge with the same y value, and newly added lower 686 // edges must be _after_ all other edges with the same 687 // y. This ensures that the left vertical edge processing 688 // below encounters the upper edge of the current rect 689 // first, and the lower edge last, which automatically 690 // starts and finishes this rect correctly (as only then, 691 // the polygon will have their associated active edges 692 // set). 693 const double nMinY( rRect.getMinY() ); 694 const double nMaxY( rRect.getMaxY() ); 695 ListOfEdges::iterator aCurr( io_rEdgeList.begin() ); 696 const ListOfEdges::iterator aEnd ( io_rEdgeList.end() ); 697 while( aCurr != aEnd ) 698 { 699 const double nCurrY( aCurr->getInvariantCoord() ); 700 701 if( nCurrY >= nMinY && 702 aNewEdges.size() == 2 ) // only add, if not yet done. 703 { 704 // insert upper edge _before_ aCurr. Thus, it will 705 // be the first entry for a range of equal y 706 // values. Using splice here, since we hold 707 // references to the moved list element! 708 io_rEdgeList.splice( aCurr, 709 aNewEdges, 710 aNewEdges.begin() ); 711 } 712 713 if( nCurrY > nMaxY ) 714 { 715 // insert lower edge _before_ aCurr. Thus, it will 716 // be the last entry for a range of equal y values 717 // (aCurr is the first entry strictly larger than 718 // nMaxY). Using splice here, since we hold 719 // references to the moved list element! 720 io_rEdgeList.splice( aCurr, 721 aNewEdges, 722 aNewEdges.begin() ); 723 // done with insertion, can early-exit here. 724 return; 725 } 726 727 ++aCurr; 728 } 729 730 // append remainder of aNewList (might still contain 2 or 731 // 1 elements, depending of the contents of io_rEdgeList). 732 io_rEdgeList.splice( aCurr, 733 aNewEdges ); 734 } 735 736 inline bool isSameRect(ActiveEdge& rEdge, 737 const basegfx::B2DRange& rRect) 738 { 739 return &rEdge.getRect() == &rRect; 740 } 741 742 // wow what a hack. necessary because stl's list::erase does 743 // not eat reverse_iterator 744 template<typename Cont, typename Iter> Iter eraseFromList(Cont&, Iter); 745 template<> inline ListOfEdges::iterator eraseFromList( 746 ListOfEdges& rList, ListOfEdges::iterator aIter) 747 { 748 return rList.erase(aIter); 749 } 750 template<> inline ListOfEdges::reverse_iterator eraseFromList( 751 ListOfEdges& rList, ListOfEdges::reverse_iterator aIter) 752 { 753 return ListOfEdges::reverse_iterator( 754 rList.erase(boost::prior(aIter.base()))); 755 } 756 757 template<int bPerformErase, 758 typename Iterator> inline void processActiveEdges( 759 Iterator first, 760 Iterator last, 761 ListOfEdges& rActiveEdgeList, 762 SweepLineEvent& rCurrEvent, 763 VectorOfPolygons& rPolygonPool, 764 B2DPolyPolygon& rRes ) 765 { 766 const basegfx::B2DRange& rCurrRect=rCurrEvent.getRect(); 767 768 // fast-forward to rCurrEvent's first active edge (holds 769 // for both starting and finishing sweep line events, a 770 // rect is regarded _outside_ any rects whose events have 771 // started earlier 772 first = std::find_if(first, last, 773 boost::bind( 774 &isSameRect, 775 _1, 776 boost::cref(rCurrRect))); 777 778 if(first == last) 779 return; 780 781 int nCount=0; 782 std::ptrdiff_t nCurrPolyIdx=-1; 783 while(first != last) 784 { 785 if( nCurrPolyIdx == -1 ) 786 nCurrPolyIdx=first->getTargetPolygonIndex(); 787 788 OSL_ASSERT(nCurrPolyIdx != -1); 789 790 // second encounter of my rect -> second edge 791 // encountered, done 792 const bool bExit= 793 nCount && 794 isSameRect(*first, 795 rCurrRect); 796 797 // deal with current active edge 798 nCurrPolyIdx = 799 rPolygonPool.get(nCurrPolyIdx).intersect( 800 rCurrEvent, 801 *first, 802 rPolygonPool, 803 rRes, 804 bExit); 805 806 // prune upper & lower active edges, if requested 807 if( bPerformErase && (bExit || !nCount) ) 808 first = eraseFromList(rActiveEdgeList,first); 809 else 810 ++first; 811 812 // delayed exit, had to prune first 813 if( bExit ) 814 return; 815 816 ++nCount; 817 } 818 } 819 820 template<int bPerformErase> inline void processActiveEdgesTopDown( 821 SweepLineEvent& rCurrEvent, 822 ListOfEdges& rActiveEdgeList, 823 VectorOfPolygons& rPolygonPool, 824 B2DPolyPolygon& rRes ) 825 { 826 processActiveEdges<bPerformErase>( 827 rActiveEdgeList. begin(), 828 rActiveEdgeList. end(), 829 rActiveEdgeList, 830 rCurrEvent, 831 rPolygonPool, 832 rRes); 833 } 834 835 template<int bPerformErase> inline void processActiveEdgesBottomUp( 836 SweepLineEvent& rCurrEvent, 837 ListOfEdges& rActiveEdgeList, 838 VectorOfPolygons& rPolygonPool, 839 B2DPolyPolygon& rRes ) 840 { 841 processActiveEdges<bPerformErase>( 842 rActiveEdgeList. rbegin(), 843 rActiveEdgeList. rend(), 844 rActiveEdgeList, 845 rCurrEvent, 846 rPolygonPool, 847 rRes); 848 } 849 850 enum{ NoErase=0, PerformErase=1 }; 851 852 void handleStartingEdge( SweepLineEvent& rCurrEvent, 853 ListOfEdges& rActiveEdgeList, 854 VectorOfPolygons& rPolygonPool, 855 B2DPolyPolygon& rRes) 856 { 857 // inject two new active edges for rect 858 createActiveEdgesFromStartEvent( rActiveEdgeList, 859 rPolygonPool, 860 rCurrEvent ); 861 862 if( SweepLineEvent::PROCEED_DOWN == rCurrEvent.getEdgeDirection() ) 863 processActiveEdgesTopDown<NoErase>( 864 rCurrEvent, rActiveEdgeList, rPolygonPool, rRes); 865 else 866 processActiveEdgesBottomUp<NoErase>( 867 rCurrEvent, rActiveEdgeList, rPolygonPool, rRes); 868 } 869 870 void handleFinishingEdge( SweepLineEvent& rCurrEvent, 871 ListOfEdges& rActiveEdgeList, 872 VectorOfPolygons& rPolygonPool, 873 B2DPolyPolygon& rRes) 874 { 875 if( SweepLineEvent::PROCEED_DOWN == rCurrEvent.getEdgeDirection() ) 876 processActiveEdgesTopDown<PerformErase>( 877 rCurrEvent, rActiveEdgeList, rPolygonPool, rRes); 878 else 879 processActiveEdgesBottomUp<PerformErase>( 880 rCurrEvent, rActiveEdgeList, rPolygonPool, rRes); 881 } 882 883 inline void handleSweepLineEvent( SweepLineEvent& rCurrEvent, 884 ListOfEdges& rActiveEdgeList, 885 VectorOfPolygons& rPolygonPool, 886 B2DPolyPolygon& rRes) 887 { 888 if( SweepLineEvent::STARTING_EDGE == rCurrEvent.getEdgeType() ) 889 handleStartingEdge(rCurrEvent,rActiveEdgeList,rPolygonPool,rRes); 890 else 891 handleFinishingEdge(rCurrEvent,rActiveEdgeList,rPolygonPool,rRes); 892 } 893 } 894 895 namespace tools 896 { 897 B2DPolyPolygon solveCrossovers(const std::vector<B2DRange>& rRanges, 898 const std::vector<B2VectorOrientation>& rOrientations) 899 { 900 // sweep-line algorithm to generate a poly-polygon 901 // from a bunch of rectangles 902 // =============================================== 903 // 904 // This algorithm uses the well-known sweep line 905 // concept, explained in every good text book about 906 // computational geometry. 907 // 908 // We start with creating two structures for every 909 // rectangle, one representing the left x coordinate, 910 // one representing the right x coordinate (and both 911 // referencing the original rect). These structs are 912 // sorted with increasing x coordinates. 913 // 914 // Then, we start processing the resulting list from 915 // the beginning. Every entry in the list defines a 916 // point in time of the line sweeping from left to 917 // right across all rectangles. 918 VectorOfEvents aSweepLineEvents; 919 setupSweepLineEventListFromRanges( aSweepLineEvents, 920 rRanges, 921 rOrientations ); 922 923 B2DPolyPolygon aRes; 924 VectorOfPolygons aPolygonPool; 925 ListOfEdges aActiveEdgeList; 926 927 // sometimes not enough, but a usable compromise 928 aPolygonPool.reserve( rRanges.size() ); 929 930 std::for_each( aSweepLineEvents.begin(), 931 aSweepLineEvents.end(), 932 boost::bind( 933 &handleSweepLineEvent, 934 _1, 935 boost::ref(aActiveEdgeList), 936 boost::ref(aPolygonPool), 937 boost::ref(aRes)) ); 938 939 return aRes; 940 } 941 } 942 } 943 944