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: b2dpolygontriangulator.cxx,v $ 10 * $Revision: 1.7 $ 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 #include <basegfx/polygon/b2dtrapezoid.hxx> 34 #include <basegfx/range/b1drange.hxx> 35 #include <basegfx/polygon/b2dpolygontools.hxx> 36 #include <list> 37 38 ////////////////////////////////////////////////////////////////////////////// 39 40 namespace basegfx 41 { 42 namespace trapezoidhelper 43 { 44 ////////////////////////////////////////////////////////////////////////////// 45 // helper class to hold a simple ege. This is only used for horizontal edges 46 // currently, thus the YPositions will be equal. I did not create a special 47 // class for this since holdingthe pointers is more effective and also can be 48 // used as baseclass for the traversing edges 49 50 class TrDeSimpleEdge 51 { 52 protected: 53 // pointers to start and end point 54 const B2DPoint* mpStart; 55 const B2DPoint* mpEnd; 56 57 public: 58 // constructor 59 TrDeSimpleEdge( 60 const B2DPoint* pStart, 61 const B2DPoint* pEnd) 62 : mpStart(pStart), 63 mpEnd(pEnd) 64 { 65 } 66 67 // data read access 68 const B2DPoint& getStart() const { return *mpStart; } 69 const B2DPoint& getEnd() const { return *mpEnd; } 70 }; 71 72 ////////////////////////////////////////////////////////////////////////////// 73 // define vector of simple edges 74 75 typedef ::std::vector< TrDeSimpleEdge > TrDeSimpleEdges; 76 77 ////////////////////////////////////////////////////////////////////////////// 78 // helper class for holding a traversing edge. It will always have some 79 // distance in YPos. The slope (in a numerically useful form, see comments) is 80 // hold and used in SortValue to allow sorting traversing edges by Y, X and slope 81 // (in that order) 82 83 class TrDeEdgeEntry : public TrDeSimpleEdge 84 { 85 private: 86 // the slope in a numerical useful form for sorting 87 sal_uInt32 mnSortValue; 88 89 public: 90 // convenience data read access 91 double getDeltaX() const { return mpEnd->getX() - mpStart->getX(); } 92 double getDeltaY() const { return mpEnd->getY() - mpStart->getY(); } 93 94 // convenience data read access. SortValue is created on demand since 95 // it is not always used 96 sal_uInt32 getSortValue() const 97 { 98 if(0 != mnSortValue) 99 return mnSortValue; 100 101 // get radiant; has to be in the range ]0.0 .. pi[, thus scale to full 102 // sal_uInt32 range for maximum precision 103 const double fRadiant(atan2(getDeltaY(), getDeltaX()) * (SAL_MAX_UINT32 / F_PI)); 104 105 // convert to sal_uInt32 value 106 const_cast< TrDeEdgeEntry* >(this)->mnSortValue = sal_uInt32(fRadiant); 107 108 return mnSortValue; 109 } 110 111 // constructor. SortValue can be given when known, use zero otherwise 112 TrDeEdgeEntry( 113 const B2DPoint* pStart, 114 const B2DPoint* pEnd, 115 sal_uInt32 nSortValue = 0) 116 : TrDeSimpleEdge(pStart, pEnd), 117 mnSortValue(nSortValue) 118 { 119 // force traversal of deltaY downward 120 if(mpEnd->getY() < mpStart->getY()) 121 { 122 std::swap(mpStart, mpEnd); 123 } 124 125 // no horizontal edges allowed, all neeed to traverse vertically 126 OSL_ENSURE(mpEnd->getY() > mpStart->getY(), "Illegal TrDeEdgeEntry constructed (!)"); 127 } 128 129 // data write access to StartPoint 130 void setStart( const B2DPoint* pNewStart) 131 { 132 OSL_ENSURE(0 != pNewStart, "No null pointer allowed here (!)"); 133 134 if(mpStart != pNewStart) 135 { 136 mpStart = pNewStart; 137 138 // no horizontal edges allowed, all neeed to traverse vertivally 139 OSL_ENSURE(mpEnd->getY() > mpStart->getY(), "Illegal TrDeEdgeEntry constructed (!)"); 140 } 141 } 142 143 // data write access to EndPoint 144 void setEnd( const B2DPoint* pNewEnd) 145 { 146 OSL_ENSURE(0 != pNewEnd, "No null pointer allowed here (!)"); 147 148 if(mpEnd != pNewEnd) 149 { 150 mpEnd = pNewEnd; 151 152 // no horizontal edges allowed, all neeed to traverse vertivally 153 OSL_ENSURE(mpEnd->getY() > mpStart->getY(), "Illegal TrDeEdgeEntry constructed (!)"); 154 } 155 } 156 157 // operator for sort support. Sort by Y, X and slope (in that order) 158 bool operator<(const TrDeEdgeEntry& rComp) const 159 { 160 if(fTools::equal(getStart().getY(), rComp.getStart().getY(), fTools::getSmallValue())) 161 { 162 if(fTools::equal(getStart().getX(), rComp.getStart().getX(), fTools::getSmallValue())) 163 { 164 // when start points are equal, use the direction the edge is pointing 165 // to. That value is created on demand and derived from atan2 in the 166 // range ]0.0 .. pi[ (without extremas, we always have a deltaY in this 167 // class) and scaled to sal_uInt32 range for best precision. 0 means no angle, 168 // while SAL_MAX_UINT32 means pi. Thus, the higher the value, the more left 169 // the edge traverses. 170 return (getSortValue() > rComp.getSortValue()); 171 } 172 else 173 { 174 return fTools::less(getStart().getX(), rComp.getStart().getX()); 175 } 176 } 177 else 178 { 179 return fTools::less(getStart().getY(), rComp.getStart().getY()); 180 } 181 } 182 183 // method for cut support 184 B2DPoint getCutPointForGivenY(double fGivenY) 185 { 186 // Calculate cut point locally (do not use interpolate) since it is numerically 187 // necessary to guarantee the new, equal Y-coordinate 188 const double fFactor((fGivenY - getStart().getY()) / getDeltaY()); 189 const double fDeltaXNew(fFactor * getDeltaX()); 190 191 return B2DPoint(getStart().getX() + fDeltaXNew, fGivenY); 192 } 193 }; 194 195 ////////////////////////////////////////////////////////////////////////////// 196 // define double linked list of edges (for fast random insert) 197 198 typedef ::std::list< TrDeEdgeEntry > TrDeEdgeEntries; 199 200 } // end of anonymous namespace 201 } // end of namespace basegfx 202 203 ////////////////////////////////////////////////////////////////////////////// 204 205 namespace basegfx 206 { 207 namespace trapezoidhelper 208 { 209 // helper class to handle the complete trapezoid subdivision of a PolyPolygon 210 class TrapezoidSubdivider 211 { 212 private: 213 // local data 214 sal_uInt32 mnInitialEdgeEntryCount; 215 TrDeEdgeEntries maTrDeEdgeEntries; 216 ::std::vector< B2DPoint > maPoints; 217 ::std::vector< B2DPoint* > maNewPoints; 218 219 void addEdgeSorted( 220 TrDeEdgeEntries::iterator aCurrent, 221 const TrDeEdgeEntry& rNewEdge) 222 { 223 // Loop while new entry is bigger, use operator< 224 while(aCurrent != maTrDeEdgeEntries.end() && (*aCurrent) < rNewEdge) 225 { 226 aCurrent++; 227 } 228 229 // Insert before first which is smaller or equal or at end 230 maTrDeEdgeEntries.insert(aCurrent, rNewEdge); 231 } 232 233 bool splitEdgeAtGivenPoint( 234 TrDeEdgeEntries::reference aEdge, 235 const B2DPoint& rCutPoint, 236 TrDeEdgeEntries::iterator aCurrent) 237 { 238 // do not create edges without deltaY: do not split when start is identical 239 if(aEdge.getStart().equal(rCutPoint, fTools::getSmallValue())) 240 { 241 return false; 242 } 243 244 // do not create edges without deltaY: do not split when end is identical 245 if(aEdge.getEnd().equal(rCutPoint, fTools::getSmallValue())) 246 { 247 return false; 248 } 249 250 const double fOldDeltaYStart(rCutPoint.getY() - aEdge.getStart().getY()); 251 252 if(fTools::lessOrEqual(fOldDeltaYStart, 0.0)) 253 { 254 // do not split: the resulting edge would be horizontal 255 // correct it to new start point 256 aEdge.setStart(&rCutPoint); 257 return false; 258 } 259 260 const double fNewDeltaYStart(aEdge.getEnd().getY() - rCutPoint.getY()); 261 262 if(fTools::lessOrEqual(fNewDeltaYStart, 0.0)) 263 { 264 // do not split: the resulting edge would be horizontal 265 // correct it to new end point 266 aEdge.setEnd(&rCutPoint); 267 return false; 268 } 269 270 // Create new entry 271 const TrDeEdgeEntry aNewEdge( 272 &rCutPoint, 273 &aEdge.getEnd(), 274 aEdge.getSortValue()); 275 276 // Correct old entry 277 aEdge.setEnd(&rCutPoint); 278 279 // Insert sorted (to avoid new sort) 280 addEdgeSorted(aCurrent, aNewEdge); 281 282 return true; 283 } 284 285 bool testAndCorrectEdgeIntersection( 286 TrDeEdgeEntries::reference aEdgeA, 287 TrDeEdgeEntries::reference aEdgeB, 288 TrDeEdgeEntries::iterator aCurrent) 289 { 290 // Exclude simple cases: same start or end point 291 if(aEdgeA.getStart().equal(aEdgeB.getStart(), fTools::getSmallValue())) 292 { 293 return false; 294 } 295 296 if(aEdgeA.getStart().equal(aEdgeB.getEnd(), fTools::getSmallValue())) 297 { 298 return false; 299 } 300 301 if(aEdgeA.getEnd().equal(aEdgeB.getStart(), fTools::getSmallValue())) 302 { 303 return false; 304 } 305 306 if(aEdgeA.getEnd().equal(aEdgeB.getEnd(), fTools::getSmallValue())) 307 { 308 return false; 309 } 310 311 // Exclude simple cases: one of the edges has no length anymore 312 if(aEdgeA.getStart().equal(aEdgeA.getEnd(), fTools::getSmallValue())) 313 { 314 return false; 315 } 316 317 if(aEdgeB.getStart().equal(aEdgeB.getEnd(), fTools::getSmallValue())) 318 { 319 return false; 320 } 321 322 // check if one point is on the other edge (a touch, not a cut) 323 const B2DVector aDeltaB(aEdgeB.getDeltaX(), aEdgeB.getDeltaY()); 324 325 if(tools::isPointOnEdge(aEdgeA.getStart(), aEdgeB.getStart(), aDeltaB)) 326 { 327 return splitEdgeAtGivenPoint(aEdgeB, aEdgeA.getStart(), aCurrent); 328 } 329 330 if(tools::isPointOnEdge(aEdgeA.getEnd(), aEdgeB.getStart(), aDeltaB)) 331 { 332 return splitEdgeAtGivenPoint(aEdgeB, aEdgeA.getEnd(), aCurrent); 333 } 334 335 const B2DVector aDeltaA(aEdgeA.getDeltaX(), aEdgeA.getDeltaY()); 336 337 if(tools::isPointOnEdge(aEdgeB.getStart(), aEdgeA.getStart(), aDeltaA)) 338 { 339 return splitEdgeAtGivenPoint(aEdgeA, aEdgeB.getStart(), aCurrent); 340 } 341 342 if(tools::isPointOnEdge(aEdgeB.getEnd(), aEdgeA.getStart(), aDeltaA)) 343 { 344 return splitEdgeAtGivenPoint(aEdgeA, aEdgeB.getEnd(), aCurrent); 345 } 346 347 // check for cut inside edges. Use both t-values to choose the more precise 348 // one later 349 double fCutA(0.0); 350 double fCutB(0.0); 351 352 if(tools::findCut( 353 aEdgeA.getStart(), aDeltaA, 354 aEdgeB.getStart(), aDeltaB, 355 CUTFLAG_LINE, 356 &fCutA, 357 &fCutB)) 358 { 359 // use a simple metric (length criteria) for choosing the numerically 360 // better cut 361 const double fSimpleLengthA(aDeltaA.getX() + aDeltaA.getY()); 362 const double fSimpleLengthB(aDeltaB.getX() + aDeltaB.getY()); 363 const bool bAIsLonger(fSimpleLengthA > fSimpleLengthB); 364 B2DPoint* pNewPoint = bAIsLonger 365 ? new B2DPoint(aEdgeA.getStart() + (fCutA * aDeltaA)) 366 : new B2DPoint(aEdgeB.getStart() + (fCutB * aDeltaB)); 367 bool bRetval(false); 368 369 // try to split both edges 370 bRetval = splitEdgeAtGivenPoint(aEdgeA, *pNewPoint, aCurrent); 371 bRetval |= splitEdgeAtGivenPoint(aEdgeB, *pNewPoint, aCurrent); 372 373 if(bRetval) 374 { 375 maNewPoints.push_back(pNewPoint); 376 } 377 else 378 { 379 delete pNewPoint; 380 } 381 382 return bRetval; 383 } 384 385 return false; 386 } 387 388 void solveHorizontalEdges(TrDeSimpleEdges& rTrDeSimpleEdges) 389 { 390 if(rTrDeSimpleEdges.size() && maTrDeEdgeEntries.size()) 391 { 392 // there were horizontal edges. These can be excluded, but 393 // cuts with other edges need to be solved and added before 394 // ignoring them 395 sal_uInt32 a(0); 396 397 for(a = 0; a < rTrDeSimpleEdges.size(); a++) 398 { 399 // get horizontal edge as candidate; prepare it's range and fixed Y 400 const TrDeSimpleEdge& rHorEdge = rTrDeSimpleEdges[a]; 401 const B1DRange aRange(rHorEdge.getStart().getX(), rHorEdge.getEnd().getX()); 402 const double fFixedY(rHorEdge.getStart().getY()); 403 404 // loop over traversing edges 405 TrDeEdgeEntries::iterator aCurrent(maTrDeEdgeEntries.begin()); 406 407 do 408 { 409 // get compare edge 410 TrDeEdgeEntries::reference aCompare(*aCurrent++); 411 412 if(fTools::lessOrEqual(aCompare.getEnd().getY(), fFixedY)) 413 { 414 // edge ends above horizontal edge, continue 415 continue; 416 } 417 418 if(fTools::moreOrEqual(aCompare.getStart().getY(), fFixedY)) 419 { 420 // edge starts below horizontal edge, continue 421 continue; 422 } 423 424 // vertical overlap, get horizontal range 425 const B1DRange aCompareRange(aCompare.getStart().getX(), aCompare.getEnd().getX()); 426 427 if(aRange.overlaps(aCompareRange)) 428 { 429 // possible cut, get cut point 430 const B2DPoint aSplit(aCompare.getCutPointForGivenY(fFixedY)); 431 432 if(fTools::more(aSplit.getX(), aRange.getMinimum()) 433 && fTools::less(aSplit.getX(), aRange.getMaximum())) 434 { 435 // cut is in XRange of horizontal edge, potenitally needed cut 436 B2DPoint* pNewPoint = new B2DPoint(aSplit); 437 438 if(splitEdgeAtGivenPoint(aCompare, *pNewPoint, aCurrent)) 439 { 440 maNewPoints.push_back(pNewPoint); 441 } 442 else 443 { 444 delete pNewPoint; 445 } 446 } 447 } 448 } 449 while(aCurrent != maTrDeEdgeEntries.end() 450 && fTools::less(aCurrent->getStart().getY(), fFixedY)); 451 } 452 } 453 } 454 455 public: 456 TrapezoidSubdivider( 457 const B2DPolyPolygon& rSourcePolyPolygon) 458 : mnInitialEdgeEntryCount(0), 459 maTrDeEdgeEntries(), 460 maPoints(), 461 maNewPoints() 462 { 463 B2DPolyPolygon aSource(rSourcePolyPolygon); 464 const sal_uInt32 nPolygonCount(rSourcePolyPolygon.count()); 465 TrDeSimpleEdges aTrDeSimpleEdges; 466 sal_uInt32 a(0), b(0); 467 sal_uInt32 nAllPointCount(0); 468 469 // ensure there are no curves used 470 if(aSource.areControlPointsUsed()) 471 { 472 aSource = aSource.getDefaultAdaptiveSubdivision(); 473 } 474 475 for(a = 0; a < nPolygonCount; a++) 476 { 477 // 1st run: count points 478 const B2DPolygon aPolygonCandidate(aSource.getB2DPolygon(a)); 479 const sal_uInt32 nCount(aPolygonCandidate.count()); 480 481 if(nCount > 2) 482 { 483 nAllPointCount += nCount; 484 } 485 } 486 487 if(nAllPointCount) 488 { 489 // reserve needed points. CAUTION: maPoints size is NOT to be changed anymore 490 // after 2nd loop since pointers to it are used in the edges 491 maPoints.reserve(nAllPointCount); 492 493 for(a = 0; a < nPolygonCount; a++) 494 { 495 // 2nd run: add points 496 const B2DPolygon aPolygonCandidate(aSource.getB2DPolygon(a)); 497 const sal_uInt32 nCount(aPolygonCandidate.count()); 498 499 if(nCount > 2) 500 { 501 for(b = 0; b < nCount; b++) 502 { 503 maPoints.push_back(aPolygonCandidate.getB2DPoint(b)); 504 } 505 } 506 } 507 508 // Moved the edge construction to a 3rd run: doing it in the 2nd run is 509 // possible(and i used it), but requires a working vector::reserve() 510 // implementation, else the vector will be reallocated and the pointers 511 // in the edges may be wrong. Security first here. 512 sal_uInt32 nStartIndex(0); 513 514 for(a = 0; a < nPolygonCount; a++) 515 { 516 const B2DPolygon aPolygonCandidate(aSource.getB2DPolygon(a)); 517 const sal_uInt32 nCount(aPolygonCandidate.count()); 518 519 if(nCount > 2) 520 { 521 // get the last point of the current polygon 522 B2DPoint* pPrev(&maPoints[nCount + nStartIndex - 1]); 523 524 for(b = 0; b < nCount; b++) 525 { 526 // get next point 527 B2DPoint* pCurr(&maPoints[nStartIndex++]); 528 529 if(fTools::equal(pPrev->getY(), pCurr->getY(), fTools::getSmallValue())) 530 { 531 // horizontal edge, check for single point 532 if(!fTools::equal(pPrev->getX(), pCurr->getX(), fTools::getSmallValue())) 533 { 534 // X-order not needed, just add 535 aTrDeSimpleEdges.push_back(TrDeSimpleEdge(pPrev, pCurr)); 536 537 const double fMiddle((pPrev->getY() + pCurr->getY()) * 0.5); 538 pPrev->setY(fMiddle); 539 pCurr->setY(fMiddle); 540 } 541 } 542 else 543 { 544 // vertical edge. Positive Y-direction is guaranteed by the 545 // TrDeEdgeEntry constructor 546 maTrDeEdgeEntries.push_back(TrDeEdgeEntry(pPrev, pCurr, 0)); 547 mnInitialEdgeEntryCount++; 548 } 549 550 // prepare next step 551 pPrev = pCurr; 552 } 553 } 554 } 555 } 556 557 if(maTrDeEdgeEntries.size()) 558 { 559 // single and initial sort of traversing edges 560 maTrDeEdgeEntries.sort(); 561 562 // solve horizontal edges if there are any detected 563 solveHorizontalEdges(aTrDeSimpleEdges); 564 } 565 } 566 567 ~TrapezoidSubdivider() 568 { 569 // delete the extra points created for cuts 570 const sal_uInt32 nCount(maNewPoints.size()); 571 572 for(sal_uInt32 a(0); a < nCount; a++) 573 { 574 delete maNewPoints[a]; 575 } 576 } 577 578 void Subdivide(B2DTrapezoidVector& ro_Result) 579 { 580 // This is the central subdivider. The strategy is to use the first two entries 581 // from the traversing edges as a potential trapezoid and do the needed corrections 582 // and adaptions on the way. 583 // 584 // There always must be two edges with the same YStart value: When adding the polygons 585 // in the constructor, there is always a topmost point from which two edges start; when 586 // the topmost is an edge, there is a start and end of this edge from which two edges 587 // start. All cases have two edges with same StartY (QED). 588 // 589 // Based on this these edges get corrected when: 590 // - one is longer than the other 591 // - they intersect 592 // - they intersect with other edges 593 // - another edge starts inside the thought trapezoid 594 // 595 // All this cases again produce a valid state so that the first two edges have a common 596 // Ystart again. Some cases lead to a restart of the process, some allow consuming the 597 // edges and create the intended trapezoid. 598 // 599 // Be careful when doing chages here: It is essential to keep all possible paths 600 // in valid states and to be numerically correct. This is especially needed e.g. 601 // by using fTools::equal(..) in the more robust small-value incarnation. 602 B1DRange aLeftRange; 603 B1DRange aRightRange; 604 605 if(!maTrDeEdgeEntries.empty()) 606 { 607 // measuring shows that the relation between edges and created trapezoids is 608 // mostly in the 1:1 range, thus reserve as much trapezoids as edges exist. Do 609 // not use maTrDeEdgeEntries.size() since that may be a non-constant time 610 // operation for Lists. Instead, use mnInitialEdgeEntryCount which will contain 611 // the roughly counted adds to the List 612 ro_Result.reserve(ro_Result.size() + mnInitialEdgeEntryCount); 613 } 614 615 while(!maTrDeEdgeEntries.empty()) 616 { 617 // Prepare current operator and get first edge 618 TrDeEdgeEntries::iterator aCurrent(maTrDeEdgeEntries.begin()); 619 TrDeEdgeEntries::reference aLeft(*aCurrent++); 620 621 if(aCurrent == maTrDeEdgeEntries.end()) 622 { 623 // Should not happen: No 2nd edge; consume the single edge 624 // to not have an endless loop and start next. During development 625 // i constantly had breakpoints here, so i am sure enough to add an 626 // assertion here 627 OSL_ENSURE(false, "Trapeziod decomposer in illegal state (!)"); 628 maTrDeEdgeEntries.pop_front(); 629 continue; 630 } 631 632 // get second edge 633 TrDeEdgeEntries::reference aRight(*aCurrent++); 634 635 if(!fTools::equal(aLeft.getStart().getY(), aRight.getStart().getY(), fTools::getSmallValue())) 636 { 637 // Should not happen: We have a 2nd edge, but YStart is on another 638 // line; consume the single edge to not have an endless loop and start 639 // next. During development i constantly had breakpoints here, so i am 640 // sure enough to add an assertion here 641 OSL_ENSURE(false, "Trapeziod decomposer in illegal state (!)"); 642 maTrDeEdgeEntries.pop_front(); 643 continue; 644 } 645 646 // aLeft and aRight build a thought trapezoid now. They have a common 647 // start line (same Y for start points). Potentially, one of the edges 648 // is longer than the other. It is only needed to look at the shorter 649 // length which build the potential trapezoid. To do so, get the end points 650 // locally and adapt the evtl. longer one. Use only aLeftEnd and aRightEnd 651 // from here on, not the aLeft.getEnd() or aRight.getEnd() accesses. 652 B2DPoint aLeftEnd(aLeft.getEnd()); 653 B2DPoint aRightEnd(aRight.getEnd()); 654 655 // check if end points are on the same line. If yes, no adaption 656 // needs to be prepared. Also remember which one actually is longer. 657 const bool bEndOnSameLine(fTools::equal(aLeftEnd.getY(), aRightEnd.getY(), fTools::getSmallValue())); 658 bool bLeftIsLonger(false); 659 660 if(!bEndOnSameLine) 661 { 662 // check which edge is longer and correct accordingly 663 bLeftIsLonger = fTools::more(aLeftEnd.getY(), aRightEnd.getY()); 664 665 if(bLeftIsLonger) 666 { 667 aLeftEnd = aLeft.getCutPointForGivenY(aRightEnd.getY()); 668 } 669 else 670 { 671 aRightEnd = aRight.getCutPointForGivenY(aLeftEnd.getY()); 672 } 673 } 674 675 // check for same start and end points 676 const bool bSameStartPoint(aLeft.getStart().equal(aRight.getStart(), fTools::getSmallValue())); 677 const bool bSameEndPoint(aLeftEnd.equal(aRightEnd, fTools::getSmallValue())); 678 679 // check the simple case that the edges form a 'blind' edge (deadend) 680 if(bSameStartPoint && bSameEndPoint) 681 { 682 // correct the longer edge if prepared 683 if(!bEndOnSameLine) 684 { 685 if(bLeftIsLonger) 686 { 687 B2DPoint* pNewPoint = new B2DPoint(aLeftEnd); 688 689 if(splitEdgeAtGivenPoint(aLeft, *pNewPoint, aCurrent)) 690 { 691 maNewPoints.push_back(pNewPoint); 692 } 693 else 694 { 695 delete pNewPoint; 696 } 697 } 698 else 699 { 700 B2DPoint* pNewPoint = new B2DPoint(aRightEnd); 701 702 if(splitEdgeAtGivenPoint(aRight, *pNewPoint, aCurrent)) 703 { 704 maNewPoints.push_back(pNewPoint); 705 } 706 else 707 { 708 delete pNewPoint; 709 } 710 } 711 } 712 713 // consume both edges and start next run 714 maTrDeEdgeEntries.pop_front(); 715 maTrDeEdgeEntries.pop_front(); 716 717 continue; 718 } 719 720 // check if the edges self-intersect. This can only happen when 721 // start and end point are different 722 bool bRangesSet(false); 723 724 if(!(bSameStartPoint || bSameEndPoint)) 725 { 726 // get XRanges of edges 727 aLeftRange = B1DRange(aLeft.getStart().getX(), aLeftEnd.getX()); 728 aRightRange = B1DRange(aRight.getStart().getX(), aRightEnd.getX()); 729 bRangesSet = true; 730 731 // use fast range test first 732 if(aLeftRange.overlaps(aRightRange)) 733 { 734 // real cut test and correction. If correction was needed, 735 // start new run 736 if(testAndCorrectEdgeIntersection(aLeft, aRight, aCurrent)) 737 { 738 continue; 739 } 740 } 741 } 742 743 // now we need to check if there are intersections with other edges 744 // or if other edges start inside the candidate trapezoid 745 if(aCurrent != maTrDeEdgeEntries.end() 746 && fTools::less(aCurrent->getStart().getY(), aLeftEnd.getY())) 747 { 748 // get XRanges of edges 749 if(!bRangesSet) 750 { 751 aLeftRange = B1DRange(aLeft.getStart().getX(), aLeftEnd.getX()); 752 aRightRange = B1DRange(aRight.getStart().getX(), aRightEnd.getX()); 753 } 754 755 // build full XRange for fast check 756 B1DRange aAllRange(aLeftRange); 757 aAllRange.expand(aRightRange); 758 759 // prepare loop iterator; aCurrent needs to stay unchanged for 760 // eventual sorted insertions of new EdgeNodes. Also prepare stop flag 761 TrDeEdgeEntries::iterator aLoop(aCurrent); 762 bool bDone(false); 763 764 do 765 { 766 // get compare edge and it's XRange 767 TrDeEdgeEntries::reference aCompare(*aLoop++); 768 769 // avoid edges using the same start point as one of 770 // the edges. These can neither have their start point 771 // in the thought trapezoid nor cut with one of the edges 772 if(aCompare.getStart().equal(aRight.getStart(), fTools::getSmallValue())) 773 { 774 continue; 775 } 776 777 // get compare XRange 778 const B1DRange aCompareRange(aCompare.getStart().getX(), aCompare.getEnd().getX()); 779 780 // use fast range test first 781 if(aAllRange.overlaps(aCompareRange)) 782 { 783 // check for start point inside thought trapezoid 784 if(fTools::more(aCompare.getStart().getY(), aLeft.getStart().getY())) 785 { 786 // calculate the two possible split points at compare's Y 787 const B2DPoint aSplitLeft(aLeft.getCutPointForGivenY(aCompare.getStart().getY())); 788 const B2DPoint aSplitRight(aRight.getCutPointForGivenY(aCompare.getStart().getY())); 789 790 // check for start point of aCompare being inside thought 791 // trapezoid 792 if(aCompare.getStart().getX() >= aSplitLeft.getX() && 793 aCompare.getStart().getX() <= aSplitRight.getX()) 794 { 795 // is inside, correct and restart loop 796 B2DPoint* pNewLeft = new B2DPoint(aSplitLeft); 797 798 if(splitEdgeAtGivenPoint(aLeft, *pNewLeft, aCurrent)) 799 { 800 maNewPoints.push_back(pNewLeft); 801 bDone = true; 802 } 803 else 804 { 805 delete pNewLeft; 806 } 807 808 B2DPoint* pNewRight = new B2DPoint(aSplitRight); 809 810 if(splitEdgeAtGivenPoint(aRight, *pNewRight, aCurrent)) 811 { 812 maNewPoints.push_back(pNewRight); 813 bDone = true; 814 } 815 else 816 { 817 delete pNewRight; 818 } 819 } 820 } 821 822 if(!bDone && aLeftRange.overlaps(aCompareRange)) 823 { 824 // test for concrete cut of compare edge with left edge 825 bDone = testAndCorrectEdgeIntersection(aLeft, aCompare, aCurrent); 826 } 827 828 if(!bDone && aRightRange.overlaps(aCompareRange)) 829 { 830 // test for concrete cut of compare edge with Right edge 831 bDone = testAndCorrectEdgeIntersection(aRight, aCompare, aCurrent); 832 } 833 } 834 } 835 while(!bDone 836 && aLoop != maTrDeEdgeEntries.end() 837 && fTools::less(aLoop->getStart().getY(), aLeftEnd.getY())); 838 839 if(bDone) 840 { 841 // something needed to be changed; start next loop 842 continue; 843 } 844 } 845 846 // when we get here, the intended trapezoid can be used. It needs to 847 // be corrected, eventually (if prepared); but this is no reason not to 848 // use it in the same loop iteration 849 if(!bEndOnSameLine) 850 { 851 if(bLeftIsLonger) 852 { 853 B2DPoint* pNewPoint = new B2DPoint(aLeftEnd); 854 855 if(splitEdgeAtGivenPoint(aLeft, *pNewPoint, aCurrent)) 856 { 857 maNewPoints.push_back(pNewPoint); 858 } 859 else 860 { 861 delete pNewPoint; 862 } 863 } 864 else 865 { 866 B2DPoint* pNewPoint = new B2DPoint(aRightEnd); 867 868 if(splitEdgeAtGivenPoint(aRight, *pNewPoint, aCurrent)) 869 { 870 maNewPoints.push_back(pNewPoint); 871 } 872 else 873 { 874 delete pNewPoint; 875 } 876 } 877 } 878 879 // the two edges start at the same Y, they use the same DeltaY, they 880 // do not cut themselves and not any other edge in range. Create a 881 // B2DTrapezoid and consume both edges 882 ro_Result.push_back( 883 B2DTrapezoid( 884 aLeft.getStart().getX(), 885 aRight.getStart().getX(), 886 aLeft.getStart().getY(), 887 aLeftEnd.getX(), 888 aRightEnd.getX(), 889 aLeftEnd.getY())); 890 891 maTrDeEdgeEntries.pop_front(); 892 maTrDeEdgeEntries.pop_front(); 893 } 894 } 895 }; 896 } // end of anonymous namespace 897 } // end of namespace basegfx 898 899 ////////////////////////////////////////////////////////////////////////////// 900 901 namespace basegfx 902 { 903 B2DTrapezoid::B2DTrapezoid( 904 const double& rfTopXLeft, 905 const double& rfTopXRight, 906 const double& rfTopY, 907 const double& rfBottomXLeft, 908 const double& rfBottomXRight, 909 const double& rfBottomY) 910 : mfTopXLeft(rfTopXLeft), 911 mfTopXRight(rfTopXRight), 912 mfTopY(rfTopY), 913 mfBottomXLeft(rfBottomXLeft), 914 mfBottomXRight(rfBottomXRight), 915 mfBottomY(rfBottomY) 916 { 917 // guarantee mfTopXRight >= mfTopXLeft 918 if(mfTopXLeft > mfTopXRight) 919 { 920 std::swap(mfTopXLeft, mfTopXRight); 921 } 922 923 // guarantee mfBottomXRight >= mfBottomXLeft 924 if(mfBottomXLeft > mfBottomXRight) 925 { 926 std::swap(mfBottomXLeft, mfBottomXRight); 927 } 928 929 // guarantee mfBottomY >= mfTopY 930 if(mfTopY > mfBottomY) 931 { 932 std::swap(mfTopY, mfBottomY); 933 std::swap(mfTopXLeft, mfBottomXLeft); 934 std::swap(mfTopXRight, mfBottomXRight); 935 } 936 } 937 938 B2DPolygon B2DTrapezoid::getB2DPolygon() const 939 { 940 B2DPolygon aRetval; 941 942 aRetval.append(B2DPoint(getTopXLeft(), getTopY())); 943 aRetval.append(B2DPoint(getTopXRight(), getTopY())); 944 aRetval.append(B2DPoint(getBottomXRight(), getBottomY())); 945 aRetval.append(B2DPoint(getBottomXLeft(), getBottomY())); 946 aRetval.setClosed(true); 947 948 return aRetval; 949 } 950 } // end of namespace basegfx 951 952 ////////////////////////////////////////////////////////////////////////////// 953 954 namespace basegfx 955 { 956 namespace tools 957 { 958 // convert Source PolyPolygon to trapezoids 959 void trapezoidSubdivide(B2DTrapezoidVector& ro_Result, const B2DPolyPolygon& rSourcePolyPolygon) 960 { 961 trapezoidhelper::TrapezoidSubdivider aTrapezoidSubdivider(rSourcePolyPolygon); 962 963 aTrapezoidSubdivider.Subdivide(ro_Result); 964 } 965 966 void createLineTrapezoidFromEdge( 967 B2DTrapezoidVector& ro_Result, 968 const B2DPoint& rPointA, 969 const B2DPoint& rPointB, 970 double fLineWidth) 971 { 972 if(fTools::lessOrEqual(fLineWidth, 0.0)) 973 { 974 // no line witdh 975 return; 976 } 977 978 if(rPointA.equal(rPointB, fTools::getSmallValue())) 979 { 980 // points are equal, no edge 981 return; 982 } 983 984 const double fHalfLineWidth(0.5 * fLineWidth); 985 986 if(fTools::equal(rPointA.getX(), rPointB.getX(), fTools::getSmallValue())) 987 { 988 // vertical line 989 const double fLeftX(rPointA.getX() - fHalfLineWidth); 990 const double fRightX(rPointA.getX() + fHalfLineWidth); 991 992 ro_Result.push_back( 993 B2DTrapezoid( 994 fLeftX, 995 fRightX, 996 std::min(rPointA.getY(), rPointB.getY()), 997 fLeftX, 998 fRightX, 999 std::max(rPointA.getY(), rPointB.getY()))); 1000 } 1001 else if(fTools::equal(rPointA.getY(), rPointB.getY(), fTools::getSmallValue())) 1002 { 1003 // horizontal line 1004 const double fLeftX(std::min(rPointA.getX(), rPointB.getX())); 1005 const double fRightX(std::max(rPointA.getX(), rPointB.getX())); 1006 1007 ro_Result.push_back( 1008 B2DTrapezoid( 1009 fLeftX, 1010 fRightX, 1011 rPointA.getY() - fHalfLineWidth, 1012 fLeftX, 1013 fRightX, 1014 rPointA.getY() + fHalfLineWidth)); 1015 } 1016 else 1017 { 1018 // diagonal line 1019 // create perpendicular vector 1020 const B2DVector aDelta(rPointB - rPointA); 1021 B2DVector aPerpendicular(-aDelta.getY(), aDelta.getX()); 1022 aPerpendicular.setLength(fHalfLineWidth); 1023 1024 // create StartLow, StartHigh, EndLow and EndHigh 1025 const B2DPoint aStartLow(rPointA + aPerpendicular); 1026 const B2DPoint aStartHigh(rPointA - aPerpendicular); 1027 const B2DPoint aEndHigh(rPointB - aPerpendicular); 1028 const B2DPoint aEndLow(rPointB + aPerpendicular); 1029 1030 // create EdgeEntries 1031 basegfx::trapezoidhelper::TrDeEdgeEntries aTrDeEdgeEntries; 1032 1033 aTrDeEdgeEntries.push_back(basegfx::trapezoidhelper::TrDeEdgeEntry(&aStartLow, &aStartHigh, 0)); 1034 aTrDeEdgeEntries.push_back(basegfx::trapezoidhelper::TrDeEdgeEntry(&aStartHigh, &aEndHigh, 0)); 1035 aTrDeEdgeEntries.push_back(basegfx::trapezoidhelper::TrDeEdgeEntry(&aEndHigh, &aEndLow, 0)); 1036 aTrDeEdgeEntries.push_back(basegfx::trapezoidhelper::TrDeEdgeEntry(&aEndLow, &aStartLow, 0)); 1037 aTrDeEdgeEntries.sort(); 1038 1039 // here we know we have exactly four edges, and they do not cut, touch or 1040 // intersect. This makes processing much easier. Get the first two as start 1041 // edges for the thought trapezoid 1042 basegfx::trapezoidhelper::TrDeEdgeEntries::iterator aCurrent(aTrDeEdgeEntries.begin()); 1043 basegfx::trapezoidhelper::TrDeEdgeEntries::reference aLeft(*aCurrent++); 1044 basegfx::trapezoidhelper::TrDeEdgeEntries::reference aRight(*aCurrent++); 1045 const bool bEndOnSameLine(fTools::equal(aLeft.getEnd().getY(), aRight.getEnd().getY(), fTools::getSmallValue())); 1046 1047 if(bEndOnSameLine) 1048 { 1049 // create two triangle trapezoids 1050 ro_Result.push_back( 1051 B2DTrapezoid( 1052 aLeft.getStart().getX(), 1053 aRight.getStart().getX(), 1054 aLeft.getStart().getY(), 1055 aLeft.getEnd().getX(), 1056 aRight.getEnd().getX(), 1057 aLeft.getEnd().getY())); 1058 1059 basegfx::trapezoidhelper::TrDeEdgeEntries::reference aLeft2(*aCurrent++); 1060 basegfx::trapezoidhelper::TrDeEdgeEntries::reference aRight2(*aCurrent++); 1061 1062 ro_Result.push_back( 1063 B2DTrapezoid( 1064 aLeft2.getStart().getX(), 1065 aRight2.getStart().getX(), 1066 aLeft2.getStart().getY(), 1067 aLeft2.getEnd().getX(), 1068 aRight2.getEnd().getX(), 1069 aLeft2.getEnd().getY())); 1070 } 1071 else 1072 { 1073 // create three trapezoids. Check which edge is longer and 1074 // correct accordingly 1075 const bool bLeftIsLonger(fTools::more(aLeft.getEnd().getY(), aRight.getEnd().getY())); 1076 1077 if(bLeftIsLonger) 1078 { 1079 basegfx::trapezoidhelper::TrDeEdgeEntries::reference aRight2(*aCurrent++); 1080 basegfx::trapezoidhelper::TrDeEdgeEntries::reference aLeft2(*aCurrent++); 1081 const B2DPoint aSplitLeft(aLeft.getCutPointForGivenY(aRight.getEnd().getY())); 1082 const B2DPoint aSplitRight(aRight2.getCutPointForGivenY(aLeft.getEnd().getY())); 1083 1084 ro_Result.push_back( 1085 B2DTrapezoid( 1086 aLeft.getStart().getX(), 1087 aRight.getStart().getX(), 1088 aLeft.getStart().getY(), 1089 aSplitLeft.getX(), 1090 aRight.getEnd().getX(), 1091 aRight.getEnd().getY())); 1092 1093 ro_Result.push_back( 1094 B2DTrapezoid( 1095 aSplitLeft.getX(), 1096 aRight.getEnd().getX(), 1097 aRight.getEnd().getY(), 1098 aLeft2.getStart().getX(), 1099 aSplitRight.getX(), 1100 aLeft2.getStart().getY())); 1101 1102 ro_Result.push_back( 1103 B2DTrapezoid( 1104 aLeft2.getStart().getX(), 1105 aSplitRight.getX(), 1106 aLeft2.getStart().getY(), 1107 aLeft2.getEnd().getX(), 1108 aRight2.getEnd().getX(), 1109 aLeft2.getEnd().getY())); 1110 } 1111 else 1112 { 1113 basegfx::trapezoidhelper::TrDeEdgeEntries::reference aLeft2(*aCurrent++); 1114 basegfx::trapezoidhelper::TrDeEdgeEntries::reference aRight2(*aCurrent++); 1115 const B2DPoint aSplitRight(aRight.getCutPointForGivenY(aLeft.getEnd().getY())); 1116 const B2DPoint aSplitLeft(aLeft2.getCutPointForGivenY(aRight.getEnd().getY())); 1117 1118 ro_Result.push_back( 1119 B2DTrapezoid( 1120 aLeft.getStart().getX(), 1121 aRight.getStart().getX(), 1122 aLeft.getStart().getY(), 1123 aLeft.getEnd().getX(), 1124 aSplitRight.getX(), 1125 aLeft.getEnd().getY())); 1126 1127 ro_Result.push_back( 1128 B2DTrapezoid( 1129 aLeft.getEnd().getX(), 1130 aSplitRight.getX(), 1131 aLeft.getEnd().getY(), 1132 aSplitLeft.getX(), 1133 aRight.getEnd().getX(), 1134 aRight2.getStart().getY())); 1135 1136 ro_Result.push_back( 1137 B2DTrapezoid( 1138 aSplitLeft.getX(), 1139 aRight.getEnd().getX(), 1140 aRight2.getStart().getY(), 1141 aLeft2.getEnd().getX(), 1142 aRight2.getEnd().getX(), 1143 aLeft2.getEnd().getY())); 1144 } 1145 } 1146 } 1147 } 1148 1149 void createLineTrapezoidFromB2DPolygon( 1150 B2DTrapezoidVector& ro_Result, 1151 const B2DPolygon& rPolygon, 1152 double fLineWidth) 1153 { 1154 if(fTools::lessOrEqual(fLineWidth, 0.0)) 1155 { 1156 return; 1157 } 1158 1159 // ensure there are no curves used 1160 B2DPolygon aSource(rPolygon); 1161 1162 if(aSource.areControlPointsUsed()) 1163 { 1164 const double fPrecisionFactor = 0.25; 1165 aSource = adaptiveSubdivideByDistance( aSource, fLineWidth * fPrecisionFactor ); 1166 } 1167 1168 const sal_uInt32 nPointCount(aSource.count()); 1169 1170 if(!nPointCount) 1171 { 1172 return; 1173 } 1174 1175 const sal_uInt32 nEdgeCount(aSource.isClosed() ? nPointCount : nPointCount - 1); 1176 B2DPoint aCurrent(aSource.getB2DPoint(0)); 1177 1178 ro_Result.reserve(ro_Result.size() + (3 * nEdgeCount)); 1179 1180 for(sal_uInt32 a(0); a < nEdgeCount; a++) 1181 { 1182 const sal_uInt32 nNextIndex((a + 1) % nPointCount); 1183 const B2DPoint aNext(aSource.getB2DPoint(nNextIndex)); 1184 1185 createLineTrapezoidFromEdge(ro_Result, aCurrent, aNext, fLineWidth); 1186 aCurrent = aNext; 1187 } 1188 } 1189 1190 void createLineTrapezoidFromB2DPolyPolygon( 1191 B2DTrapezoidVector& ro_Result, 1192 const B2DPolyPolygon& rPolyPolygon, 1193 double fLineWidth) 1194 { 1195 if(fTools::lessOrEqual(fLineWidth, 0.0)) 1196 { 1197 return; 1198 } 1199 1200 // ensure there are no curves used 1201 B2DPolyPolygon aSource(rPolyPolygon); 1202 1203 if(aSource.areControlPointsUsed()) 1204 { 1205 aSource = aSource.getDefaultAdaptiveSubdivision(); 1206 } 1207 1208 const sal_uInt32 nCount(aSource.count()); 1209 1210 if(!nCount) 1211 { 1212 return; 1213 } 1214 1215 for(sal_uInt32 a(0); a < nCount; a++) 1216 { 1217 createLineTrapezoidFromB2DPolygon( 1218 ro_Result, 1219 aSource.getB2DPolygon(a), 1220 fLineWidth); 1221 } 1222 } 1223 1224 } // end of namespace tools 1225 } // end of namespace basegfx 1226 1227 ////////////////////////////////////////////////////////////////////////////// 1228 // eof 1229