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