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