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