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 <osl/diagnose.h> 27 #include <basegfx/numeric/ftools.hxx> 28 #include <basegfx/polygon/b2dpolypolygoncutter.hxx> 29 #include <basegfx/point/b2dpoint.hxx> 30 #include <basegfx/vector/b2dvector.hxx> 31 #include <basegfx/polygon/b2dpolygon.hxx> 32 #include <basegfx/polygon/b2dpolygontools.hxx> 33 #include <basegfx/polygon/b2dpolygoncutandtouch.hxx> 34 #include <basegfx/range/b2drange.hxx> 35 #include <basegfx/polygon/b2dpolypolygontools.hxx> 36 #include <basegfx/curve/b2dcubicbezier.hxx> 37 #include <vector> 38 #include <algorithm> 39 40 ////////////////////////////////////////////////////////////////////////////// 41 42 namespace basegfx 43 { 44 namespace 45 { 46 ////////////////////////////////////////////////////////////////////////////// 47 48 struct StripHelper 49 { 50 B2DRange maRange; 51 sal_Int32 mnDepth; 52 B2VectorOrientation meOrinetation; 53 }; 54 55 ////////////////////////////////////////////////////////////////////////////// 56 57 struct PN 58 { 59 public: 60 B2DPoint maPoint; 61 sal_uInt32 mnI; 62 sal_uInt32 mnIP; 63 sal_uInt32 mnIN; 64 }; 65 66 ////////////////////////////////////////////////////////////////////////////// 67 68 struct VN 69 { 70 public: 71 B2DVector maPrev; 72 B2DVector maNext; 73 74 // to have the correct curve segments in the crossover checks, 75 // it is necessary to keep the original next vectors, too. Else, 76 // it may happen to use a already switched next vector which 77 // would interpolate the wrong comparison point 78 B2DVector maOriginalNext; 79 }; 80 81 ////////////////////////////////////////////////////////////////////////////// 82 83 struct SN 84 { 85 public: 86 PN* mpPN; 87 88 bool operator<(const SN& rComp) const 89 { 90 if(fTools::equal(mpPN->maPoint.getX(), rComp.mpPN->maPoint.getX())) 91 { 92 if(fTools::equal(mpPN->maPoint.getY(), rComp.mpPN->maPoint.getY())) 93 { 94 return (mpPN->mnI < rComp.mpPN->mnI); 95 } 96 else 97 { 98 return fTools::less(mpPN->maPoint.getY(), rComp.mpPN->maPoint.getY()); 99 } 100 } 101 else 102 { 103 return fTools::less(mpPN->maPoint.getX(), rComp.mpPN->maPoint.getX()); 104 } 105 } 106 }; 107 108 ////////////////////////////////////////////////////////////////////////////// 109 110 typedef ::std::vector< PN > PNV; 111 typedef ::std::vector< VN > VNV; 112 typedef ::std::vector< SN > SNV; 113 114 ////////////////////////////////////////////////////////////////////////////// 115 116 class solver 117 { 118 private: 119 const B2DPolyPolygon maOriginal; 120 PNV maPNV; 121 VNV maVNV; 122 SNV maSNV; 123 124 unsigned mbIsCurve : 1; 125 unsigned mbChanged : 1; 126 127 void impAddPolygon(const sal_uInt32 aPos, const B2DPolygon& rGeometry) 128 { 129 const sal_uInt32 nCount(rGeometry.count()); 130 PN aNewPN; 131 VN aNewVN; 132 SN aNewSN; 133 134 for(sal_uInt32 a(0); a < nCount; a++) 135 { 136 const B2DPoint aPoint(rGeometry.getB2DPoint(a)); 137 aNewPN.maPoint = aPoint; 138 aNewPN.mnI = aPos + a; 139 aNewPN.mnIP = aPos + ((a != 0) ? a - 1 : nCount - 1); 140 aNewPN.mnIN = aPos + ((a + 1 == nCount) ? 0 : a + 1); 141 maPNV.push_back(aNewPN); 142 143 if(mbIsCurve) 144 { 145 aNewVN.maPrev = rGeometry.getPrevControlPoint(a) - aPoint; 146 aNewVN.maNext = rGeometry.getNextControlPoint(a) - aPoint; 147 aNewVN.maOriginalNext = aNewVN.maNext; 148 maVNV.push_back(aNewVN); 149 } 150 151 aNewSN.mpPN = &maPNV[maPNV.size() - 1]; 152 maSNV.push_back(aNewSN); 153 } 154 } 155 156 bool impLeftOfEdges(const B2DVector& rVecA, const B2DVector& rVecB, const B2DVector& rTest) 157 { 158 // tests if rTest is left of both directed line segments along the line -rVecA, rVecB. Test is 159 // with border. 160 if(rVecA.cross(rVecB) > 0.0) 161 { 162 // b is left turn seen from a, test if Test is left of both and so inside (left is seeen as inside) 163 const bool bBoolA(fTools::moreOrEqual(rVecA.cross(rTest), 0.0)); 164 const bool bBoolB(fTools::lessOrEqual(rVecB.cross(rTest), 0.0)); 165 166 return (bBoolA && bBoolB); 167 } 168 else 169 { 170 // b is right turn seen from a, test if Test is right of both and so outside (left is seeen as inside) 171 const bool bBoolA(fTools::lessOrEqual(rVecA.cross(rTest), 0.0)); 172 const bool bBoolB(fTools::moreOrEqual(rVecB.cross(rTest), 0.0)); 173 174 return (!(bBoolA && bBoolB)); 175 } 176 } 177 178 void impSwitchNext(PN& rPNa, PN& rPNb) 179 { 180 ::std::swap(rPNa.mnIN, rPNb.mnIN); 181 182 if(mbIsCurve) 183 { 184 VN& rVNa = maVNV[rPNa.mnI]; 185 VN& rVNb = maVNV[rPNb.mnI]; 186 187 ::std::swap(rVNa.maNext, rVNb.maNext); 188 } 189 190 if(!mbChanged) 191 { 192 mbChanged = true; 193 } 194 } 195 196 B2DCubicBezier createSegment(const PN& rPN, bool bPrev) const 197 { 198 const B2DPoint& rStart(rPN.maPoint); 199 const B2DPoint& rEnd(maPNV[bPrev ? rPN.mnIP : rPN.mnIN].maPoint); 200 const B2DVector& rCPA(bPrev ? maVNV[rPN.mnI].maPrev : maVNV[rPN.mnI].maNext); 201 // Use maOriginalNext, not maNext to create the original (yet unchanged) 202 // curve segment. Otherwise, this segment would NOT ne correct. 203 const B2DVector& rCPB(bPrev ? maVNV[maPNV[rPN.mnIP].mnI].maOriginalNext : maVNV[maPNV[rPN.mnIN].mnI].maPrev); 204 205 return B2DCubicBezier(rStart, rStart + rCPA, rEnd + rCPB, rEnd); 206 } 207 208 void impHandleCommon(PN& rPNa, PN& rPNb) 209 { 210 if(mbIsCurve) 211 { 212 const B2DCubicBezier aNextA(createSegment(rPNa, false)); 213 const B2DCubicBezier aPrevA(createSegment(rPNa, true)); 214 215 if(aNextA.equal(aPrevA)) 216 { 217 // deadend on A (identical edge) 218 return; 219 } 220 221 const B2DCubicBezier aNextB(createSegment(rPNb, false)); 222 const B2DCubicBezier aPrevB(createSegment(rPNb, true)); 223 224 if(aNextB.equal(aPrevB)) 225 { 226 // deadend on B (identical edge) 227 return; 228 } 229 230 if(aPrevA.equal(aPrevB)) 231 { 232 // common edge in same direction 233 if(aNextA.equal(aNextB)) 234 { 235 // common edge in same direction continues 236 return; 237 } 238 else 239 { 240 // common edge in same direction leave 241 // action is done on enter 242 return; 243 } 244 } 245 else if(aPrevA.equal(aNextB)) 246 { 247 // common edge in opposite direction 248 if(aNextA.equal(aPrevB)) 249 { 250 // common edge in opposite direction continues 251 return; 252 } 253 else 254 { 255 // common edge in opposite direction leave 256 impSwitchNext(rPNa, rPNb); 257 } 258 } 259 else if(aNextA.equal(aNextB)) 260 { 261 // common edge in same direction enter 262 // search leave edge 263 PN* pPNa2 = &maPNV[rPNa.mnIN]; 264 PN* pPNb2 = &maPNV[rPNb.mnIN]; 265 bool bOnEdge(true); 266 267 do 268 { 269 const B2DCubicBezier aNextA2(createSegment(*pPNa2, false)); 270 const B2DCubicBezier aNextB2(createSegment(*pPNb2, false)); 271 272 if(aNextA2.equal(aNextB2)) 273 { 274 pPNa2 = &maPNV[pPNa2->mnIN]; 275 pPNb2 = &maPNV[pPNb2->mnIN]; 276 } 277 else 278 { 279 bOnEdge = false; 280 } 281 } 282 while(bOnEdge && pPNa2 != &rPNa && pPNa2 != &rPNa); 283 284 if(bOnEdge) 285 { 286 // loop over two identical polygon paths 287 return; 288 } 289 else 290 { 291 // enter at rPNa, rPNb; leave at pPNa2, pPNb2. No common edges 292 // at enter/leave. Check for crossover. 293 const B2DVector aPrevCA(aPrevA.interpolatePoint(0.5) - aPrevA.getStartPoint()); 294 const B2DVector aNextCA(aNextA.interpolatePoint(0.5) - aNextA.getStartPoint()); 295 const B2DVector aPrevCB(aPrevB.interpolatePoint(0.5) - aPrevB.getStartPoint()); 296 const bool bEnter(impLeftOfEdges(aPrevCA, aNextCA, aPrevCB)); 297 298 const B2DCubicBezier aNextA2(createSegment(*pPNa2, false)); 299 const B2DCubicBezier aPrevA2(createSegment(*pPNa2, true)); 300 const B2DCubicBezier aNextB2(createSegment(*pPNb2, false)); 301 const B2DVector aPrevCA2(aPrevA2.interpolatePoint(0.5) - aPrevA2.getStartPoint()); 302 const B2DVector aNextCA2(aNextA2.interpolatePoint(0.5) - aNextA2.getStartPoint()); 303 const B2DVector aNextCB2(aNextB2.interpolatePoint(0.5) - aNextB2.getStartPoint()); 304 const bool bLeave(impLeftOfEdges(aPrevCA2, aNextCA2, aNextCB2)); 305 306 if(bEnter != bLeave) 307 { 308 // crossover 309 impSwitchNext(rPNa, rPNb); 310 } 311 } 312 } 313 else if(aNextA.equal(aPrevB)) 314 { 315 // common edge in opposite direction enter 316 impSwitchNext(rPNa, rPNb); 317 } 318 else 319 { 320 // no common edges, check for crossover 321 const B2DVector aPrevCA(aPrevA.interpolatePoint(0.5) - aPrevA.getStartPoint()); 322 const B2DVector aNextCA(aNextA.interpolatePoint(0.5) - aNextA.getStartPoint()); 323 const B2DVector aPrevCB(aPrevB.interpolatePoint(0.5) - aPrevB.getStartPoint()); 324 const B2DVector aNextCB(aNextB.interpolatePoint(0.5) - aNextB.getStartPoint()); 325 326 const bool bEnter(impLeftOfEdges(aPrevCA, aNextCA, aPrevCB)); 327 const bool bLeave(impLeftOfEdges(aPrevCA, aNextCA, aNextCB)); 328 329 if(bEnter != bLeave) 330 { 331 // crossover 332 impSwitchNext(rPNa, rPNb); 333 } 334 } 335 } 336 else 337 { 338 const B2DPoint& rNextA(maPNV[rPNa.mnIN].maPoint); 339 const B2DPoint& rPrevA(maPNV[rPNa.mnIP].maPoint); 340 341 if(rNextA.equal(rPrevA)) 342 { 343 // deadend on A 344 return; 345 } 346 347 const B2DPoint& rNextB(maPNV[rPNb.mnIN].maPoint); 348 const B2DPoint& rPrevB(maPNV[rPNb.mnIP].maPoint); 349 350 if(rNextB.equal(rPrevB)) 351 { 352 // deadend on B 353 return; 354 } 355 356 if(rPrevA.equal(rPrevB)) 357 { 358 // common edge in same direction 359 if(rNextA.equal(rNextB)) 360 { 361 // common edge in same direction continues 362 return; 363 } 364 else 365 { 366 // common edge in same direction leave 367 // action is done on enter 368 return; 369 } 370 } 371 else if(rPrevA.equal(rNextB)) 372 { 373 // common edge in opposite direction 374 if(rNextA.equal(rPrevB)) 375 { 376 // common edge in opposite direction continues 377 return; 378 } 379 else 380 { 381 // common edge in opposite direction leave 382 impSwitchNext(rPNa, rPNb); 383 } 384 } 385 else if(rNextA.equal(rNextB)) 386 { 387 // common edge in same direction enter 388 // search leave edge 389 PN* pPNa2 = &maPNV[rPNa.mnIN]; 390 PN* pPNb2 = &maPNV[rPNb.mnIN]; 391 bool bOnEdge(true); 392 393 do 394 { 395 const B2DPoint& rNextA2(maPNV[pPNa2->mnIN].maPoint); 396 const B2DPoint& rNextB2(maPNV[pPNb2->mnIN].maPoint); 397 398 if(rNextA2.equal(rNextB2)) 399 { 400 pPNa2 = &maPNV[pPNa2->mnIN]; 401 pPNb2 = &maPNV[pPNb2->mnIN]; 402 } 403 else 404 { 405 bOnEdge = false; 406 } 407 } 408 while(bOnEdge && pPNa2 != &rPNa && pPNa2 != &rPNa); 409 410 if(bOnEdge) 411 { 412 // loop over two identical polygon paths 413 return; 414 } 415 else 416 { 417 // enter at rPNa, rPNb; leave at pPNa2, pPNb2. No common edges 418 // at enter/leave. Check for crossover. 419 const B2DPoint& aPointE(rPNa.maPoint); 420 const B2DVector aPrevAE(rPrevA - aPointE); 421 const B2DVector aNextAE(rNextA - aPointE); 422 const B2DVector aPrevBE(rPrevB - aPointE); 423 424 const B2DPoint& aPointL(pPNa2->maPoint); 425 const B2DVector aPrevAL(maPNV[pPNa2->mnIP].maPoint - aPointL); 426 const B2DVector aNextAL(maPNV[pPNa2->mnIN].maPoint - aPointL); 427 const B2DVector aNextBL(maPNV[pPNb2->mnIN].maPoint - aPointL); 428 429 const bool bEnter(impLeftOfEdges(aPrevAE, aNextAE, aPrevBE)); 430 const bool bLeave(impLeftOfEdges(aPrevAL, aNextAL, aNextBL)); 431 432 if(bEnter != bLeave) 433 { 434 // crossover; switch start or end 435 impSwitchNext(rPNa, rPNb); 436 } 437 } 438 } 439 else if(rNextA.equal(rPrevB)) 440 { 441 // common edge in opposite direction enter 442 impSwitchNext(rPNa, rPNb); 443 } 444 else 445 { 446 // no common edges, check for crossover 447 const B2DPoint& aPoint(rPNa.maPoint); 448 const B2DVector aPrevA(rPrevA - aPoint); 449 const B2DVector aNextA(rNextA - aPoint); 450 const B2DVector aPrevB(rPrevB - aPoint); 451 const B2DVector aNextB(rNextB - aPoint); 452 453 const bool bEnter(impLeftOfEdges(aPrevA, aNextA, aPrevB)); 454 const bool bLeave(impLeftOfEdges(aPrevA, aNextA, aNextB)); 455 456 if(bEnter != bLeave) 457 { 458 // crossover 459 impSwitchNext(rPNa, rPNb); 460 } 461 } 462 } 463 } 464 465 void impSolve() 466 { 467 // sort by point to identify common nodes 468 ::std::sort(maSNV.begin(), maSNV.end()); 469 470 // handle common nodes 471 const sal_uInt32 nNodeCount(maSNV.size()); 472 473 for(sal_uInt32 a(0); a < nNodeCount - 1; a++) 474 { 475 // test a before using it, not after. Also use nPointCount instead of aSortNodes.size() 476 PN& rPNb = *(maSNV[a].mpPN); 477 478 for(sal_uInt32 b(a + 1); b < nNodeCount && rPNb.maPoint.equal(maSNV[b].mpPN->maPoint); b++) 479 { 480 impHandleCommon(rPNb, *maSNV[b].mpPN); 481 } 482 } 483 } 484 485 public: 486 solver(const B2DPolygon& rOriginal) 487 : maOriginal(B2DPolyPolygon(rOriginal)), 488 mbIsCurve(false), 489 mbChanged(false) 490 { 491 const sal_uInt32 nOriginalCount(rOriginal.count()); 492 493 if(nOriginalCount) 494 { 495 B2DPolygon aGeometry(tools::addPointsAtCutsAndTouches(rOriginal)); 496 aGeometry.removeDoublePoints(); 497 aGeometry = tools::simplifyCurveSegments(aGeometry); 498 mbIsCurve = aGeometry.areControlPointsUsed(); 499 500 const sal_uInt32 nPointCount(aGeometry.count()); 501 502 // If it's not a pezier polygon, at least four points are needed to create 503 // a self-intersection. If it's a bezier polygon, the minimum point number 504 // is two, since with a single point You get a curve, but no self-intersection 505 if(nPointCount > 3 || (nPointCount > 1 && mbIsCurve)) 506 { 507 // reserve space in point, control and sort vector. 508 maSNV.reserve(nPointCount); 509 maPNV.reserve(nPointCount); 510 maVNV.reserve(mbIsCurve ? nPointCount : 0); 511 512 // fill data 513 impAddPolygon(0, aGeometry); 514 515 // solve common nodes 516 impSolve(); 517 } 518 } 519 } 520 521 solver(const B2DPolyPolygon& rOriginal) 522 : maOriginal(rOriginal), 523 mbIsCurve(false), 524 mbChanged(false) 525 { 526 sal_uInt32 nOriginalCount(maOriginal.count()); 527 528 if(nOriginalCount) 529 { 530 B2DPolyPolygon aGeometry(tools::addPointsAtCutsAndTouches(maOriginal, true)); 531 aGeometry.removeDoublePoints(); 532 aGeometry = tools::simplifyCurveSegments(aGeometry); 533 mbIsCurve = aGeometry.areControlPointsUsed(); 534 nOriginalCount = aGeometry.count(); 535 536 if(nOriginalCount) 537 { 538 sal_uInt32 nPointCount(0); 539 sal_uInt32 a(0); 540 541 // count points 542 for(a = 0; a < nOriginalCount; a++) 543 { 544 const B2DPolygon aCandidate(aGeometry.getB2DPolygon(a)); 545 const sal_uInt32 nCandCount(aCandidate.count()); 546 547 // If it's not a bezier curve, at least three points would be needed to have a 548 // topological relevant (not empty) polygon. Since its not known here if trivial 549 // edges (dead ends) will be kept or sorted out, add non-bezier polygons with 550 // more than one point. 551 // For bezier curves, the minimum for defining an area is also one. 552 if(nCandCount) 553 { 554 nPointCount += nCandCount; 555 } 556 } 557 558 if(nPointCount) 559 { 560 // reserve space in point, control and sort vector. 561 maSNV.reserve(nPointCount); 562 maPNV.reserve(nPointCount); 563 maVNV.reserve(mbIsCurve ? nPointCount : 0); 564 565 // fill data 566 sal_uInt32 nInsertIndex(0); 567 568 for(a = 0; a < nOriginalCount; a++) 569 { 570 const B2DPolygon aCandidate(aGeometry.getB2DPolygon(a)); 571 const sal_uInt32 nCandCount(aCandidate.count()); 572 573 // use same condition as above, the data vector is 574 // pre-allocated 575 if(nCandCount) 576 { 577 impAddPolygon(nInsertIndex, aCandidate); 578 nInsertIndex += nCandCount; 579 } 580 } 581 582 // solve common nodes 583 impSolve(); 584 } 585 } 586 } 587 } 588 589 B2DPolyPolygon getB2DPolyPolygon() 590 { 591 if(mbChanged) 592 { 593 B2DPolyPolygon aRetval; 594 const sal_uInt32 nCount(maPNV.size()); 595 sal_uInt32 nCountdown(nCount); 596 597 for(sal_uInt32 a(0); nCountdown && a < nCount; a++) 598 { 599 PN& rPN = maPNV[a]; 600 601 if(SAL_MAX_UINT32 != rPN.mnI) 602 { 603 // unused node, start new part polygon 604 B2DPolygon aNewPart; 605 PN* pPNCurr = &rPN; 606 607 do 608 { 609 const B2DPoint& rPoint = pPNCurr->maPoint; 610 aNewPart.append(rPoint); 611 612 if(mbIsCurve) 613 { 614 const VN& rVNCurr = maVNV[pPNCurr->mnI]; 615 616 if(!rVNCurr.maPrev.equalZero()) 617 { 618 aNewPart.setPrevControlPoint(aNewPart.count() - 1, rPoint + rVNCurr.maPrev); 619 } 620 621 if(!rVNCurr.maNext.equalZero()) 622 { 623 aNewPart.setNextControlPoint(aNewPart.count() - 1, rPoint + rVNCurr.maNext); 624 } 625 } 626 627 pPNCurr->mnI = SAL_MAX_UINT32; 628 nCountdown--; 629 pPNCurr = &(maPNV[pPNCurr->mnIN]); 630 } 631 while(pPNCurr != &rPN && SAL_MAX_UINT32 != pPNCurr->mnI); 632 633 // close and add 634 aNewPart.setClosed(true); 635 aRetval.append(aNewPart); 636 } 637 } 638 639 return aRetval; 640 } 641 else 642 { 643 // no change, return original 644 return maOriginal; 645 } 646 } 647 }; 648 649 ////////////////////////////////////////////////////////////////////////////// 650 651 } // end of anonymous namespace 652 } // end of namespace basegfx 653 654 ////////////////////////////////////////////////////////////////////////////// 655 656 namespace basegfx 657 { 658 namespace tools 659 { 660 ////////////////////////////////////////////////////////////////////////////// 661 662 B2DPolyPolygon solveCrossovers(const B2DPolyPolygon& rCandidate) 663 { 664 if(rCandidate.count() > 1L) 665 { 666 solver aSolver(rCandidate); 667 return aSolver.getB2DPolyPolygon(); 668 } 669 else 670 { 671 return rCandidate; 672 } 673 } 674 675 ////////////////////////////////////////////////////////////////////////////// 676 677 B2DPolyPolygon solveCrossovers(const B2DPolygon& rCandidate) 678 { 679 solver aSolver(rCandidate); 680 return aSolver.getB2DPolyPolygon(); 681 } 682 683 ////////////////////////////////////////////////////////////////////////////// 684 685 B2DPolyPolygon stripNeutralPolygons(const B2DPolyPolygon& rCandidate) 686 { 687 B2DPolyPolygon aRetval; 688 689 for(sal_uInt32 a(0L); a < rCandidate.count(); a++) 690 { 691 const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a)); 692 693 if(ORIENTATION_NEUTRAL != tools::getOrientation(aCandidate)) 694 { 695 aRetval.append(aCandidate); 696 } 697 } 698 699 return aRetval; 700 } 701 702 ////////////////////////////////////////////////////////////////////////////// 703 704 B2DPolyPolygon stripDispensablePolygons(const B2DPolyPolygon& rCandidate, bool bKeepAboveZero) 705 { 706 const sal_uInt32 nCount(rCandidate.count()); 707 B2DPolyPolygon aRetval; 708 709 if(nCount) 710 { 711 if(nCount == 1L) 712 { 713 if(!bKeepAboveZero && ORIENTATION_POSITIVE == tools::getOrientation(rCandidate.getB2DPolygon(0L))) 714 { 715 aRetval = rCandidate; 716 } 717 } 718 else 719 { 720 sal_uInt32 a, b; 721 ::std::vector< StripHelper > aHelpers; 722 aHelpers.resize(nCount); 723 724 for(a = 0L; a < nCount; a++) 725 { 726 const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a)); 727 StripHelper* pNewHelper = &(aHelpers[a]); 728 pNewHelper->maRange = tools::getRange(aCandidate); 729 pNewHelper->meOrinetation = tools::getOrientation(aCandidate); 730 pNewHelper->mnDepth = (ORIENTATION_NEGATIVE == pNewHelper->meOrinetation ? -1L : 0L); 731 } 732 733 for(a = 0L; a < nCount - 1L; a++) 734 { 735 const B2DPolygon aCandA(rCandidate.getB2DPolygon(a)); 736 StripHelper& rHelperA = aHelpers[a]; 737 738 for(b = a + 1L; b < nCount; b++) 739 { 740 const B2DPolygon aCandB(rCandidate.getB2DPolygon(b)); 741 StripHelper& rHelperB = aHelpers[b]; 742 const bool bAInB(rHelperB.maRange.isInside(rHelperA.maRange) && tools::isInside(aCandB, aCandA, true)); 743 const bool bBInA(rHelperA.maRange.isInside(rHelperB.maRange) && tools::isInside(aCandA, aCandB, true)); 744 745 if(bAInB && bBInA) 746 { 747 // congruent 748 if(rHelperA.meOrinetation == rHelperB.meOrinetation) 749 { 750 // two polys or two holes. Lower one of them to get one of them out of the way. 751 // Since each will be contained in the other one, both will be increased, too. 752 // So, for lowering, increase only one of them 753 rHelperA.mnDepth++; 754 } 755 else 756 { 757 // poly and hole. They neutralize, so get rid of both. Move securely below zero. 758 rHelperA.mnDepth = -((sal_Int32)nCount); 759 rHelperB.mnDepth = -((sal_Int32)nCount); 760 } 761 } 762 else 763 { 764 if(bAInB) 765 { 766 if(ORIENTATION_NEGATIVE == rHelperB.meOrinetation) 767 { 768 rHelperA.mnDepth--; 769 } 770 else 771 { 772 rHelperA.mnDepth++; 773 } 774 } 775 else if(bBInA) 776 { 777 if(ORIENTATION_NEGATIVE == rHelperA.meOrinetation) 778 { 779 rHelperB.mnDepth--; 780 } 781 else 782 { 783 rHelperB.mnDepth++; 784 } 785 } 786 } 787 } 788 } 789 790 for(a = 0L; a < nCount; a++) 791 { 792 const StripHelper& rHelper = aHelpers[a]; 793 bool bAcceptEntry(bKeepAboveZero ? 1L <= rHelper.mnDepth : 0L == rHelper.mnDepth); 794 795 if(bAcceptEntry) 796 { 797 aRetval.append(rCandidate.getB2DPolygon(a)); 798 } 799 } 800 } 801 } 802 803 return aRetval; 804 } 805 806 ////////////////////////////////////////////////////////////////////////////// 807 808 B2DPolyPolygon prepareForPolygonOperation(const B2DPolygon& rCandidate) 809 { 810 solver aSolver(rCandidate); 811 B2DPolyPolygon aRetval(stripNeutralPolygons(aSolver.getB2DPolyPolygon())); 812 813 return correctOrientations(aRetval); 814 } 815 816 B2DPolyPolygon prepareForPolygonOperation(const B2DPolyPolygon& rCandidate) 817 { 818 solver aSolver(rCandidate); 819 B2DPolyPolygon aRetval(stripNeutralPolygons(aSolver.getB2DPolyPolygon())); 820 821 return correctOrientations(aRetval); 822 } 823 824 B2DPolyPolygon solvePolygonOperationOr(const B2DPolyPolygon& rCandidateA, const B2DPolyPolygon& rCandidateB) 825 { 826 if(!rCandidateA.count()) 827 { 828 return rCandidateB; 829 } 830 else if(!rCandidateB.count()) 831 { 832 return rCandidateA; 833 } 834 else 835 { 836 // concatenate polygons, solve crossovers and throw away all sub-polygons 837 // which have a depth other than 0. 838 B2DPolyPolygon aRetval(rCandidateA); 839 840 aRetval.append(rCandidateB); 841 aRetval = solveCrossovers(aRetval); 842 aRetval = stripNeutralPolygons(aRetval); 843 844 return stripDispensablePolygons(aRetval, false); 845 } 846 } 847 848 B2DPolyPolygon solvePolygonOperationXor(const B2DPolyPolygon& rCandidateA, const B2DPolyPolygon& rCandidateB) 849 { 850 if(!rCandidateA.count()) 851 { 852 return rCandidateB; 853 } 854 else if(!rCandidateB.count()) 855 { 856 return rCandidateA; 857 } 858 else 859 { 860 // XOR is pretty simple: By definition it is the simple concatenation of 861 // the single polygons since we imply XOR fill rule. Make it intersection-free 862 // and correct orientations 863 B2DPolyPolygon aRetval(rCandidateA); 864 865 aRetval.append(rCandidateB); 866 aRetval = solveCrossovers(aRetval); 867 aRetval = stripNeutralPolygons(aRetval); 868 869 return correctOrientations(aRetval); 870 } 871 } 872 873 B2DPolyPolygon solvePolygonOperationAnd(const B2DPolyPolygon& rCandidateA, const B2DPolyPolygon& rCandidateB) 874 { 875 if(!rCandidateA.count()) 876 { 877 return B2DPolyPolygon(); 878 } 879 else if(!rCandidateB.count()) 880 { 881 return B2DPolyPolygon(); 882 } 883 else 884 { 885 // concatenate polygons, solve crossovers and throw away all sub-polygons 886 // with a depth of < 1. This means to keep all polygons where at least two 887 // polygons do overlap. 888 B2DPolyPolygon aRetval(rCandidateA); 889 890 aRetval.append(rCandidateB); 891 aRetval = solveCrossovers(aRetval); 892 aRetval = stripNeutralPolygons(aRetval); 893 894 return stripDispensablePolygons(aRetval, true); 895 } 896 } 897 898 B2DPolyPolygon solvePolygonOperationDiff(const B2DPolyPolygon& rCandidateA, const B2DPolyPolygon& rCandidateB) 899 { 900 if(!rCandidateA.count()) 901 { 902 return B2DPolyPolygon(); 903 } 904 else if(!rCandidateB.count()) 905 { 906 return rCandidateA; 907 } 908 else 909 { 910 // Make B topologically to holes and append to A 911 B2DPolyPolygon aRetval(rCandidateB); 912 913 aRetval.flip(); 914 aRetval.append(rCandidateA); 915 916 // solve crossovers and throw away all sub-polygons which have a 917 // depth other than 0. 918 aRetval = basegfx::tools::solveCrossovers(aRetval); 919 aRetval = basegfx::tools::stripNeutralPolygons(aRetval); 920 921 return basegfx::tools::stripDispensablePolygons(aRetval, false); 922 } 923 } 924 925 B2DPolyPolygon mergeToSinglePolyPolygon(const std::vector< basegfx::B2DPolyPolygon >& rInput) 926 { 927 std::vector< basegfx::B2DPolyPolygon > aInput(rInput); 928 929 // first step: prepareForPolygonOperation and simple merge of non-overlapping 930 // PolyPolygons for speedup; this is possible for the wanted OR-operation 931 if(aInput.size()) 932 { 933 std::vector< basegfx::B2DPolyPolygon > aResult; 934 aResult.reserve(aInput.size()); 935 936 for(sal_uInt32 a(0); a < aInput.size(); a++) 937 { 938 const basegfx::B2DPolyPolygon aCandidate(prepareForPolygonOperation(aInput[a])); 939 940 if(aResult.size()) 941 { 942 const B2DRange aCandidateRange(aCandidate.getB2DRange()); 943 bool bCouldMergeSimple(false); 944 945 for(sal_uInt32 b(0); !bCouldMergeSimple && b < aResult.size(); b++) 946 { 947 basegfx::B2DPolyPolygon aTarget(aResult[b]); 948 const B2DRange aTargetRange(aTarget.getB2DRange()); 949 950 if(!aCandidateRange.overlaps(aTargetRange)) 951 { 952 aTarget.append(aCandidate); 953 aResult[b] = aTarget; 954 bCouldMergeSimple = true; 955 } 956 } 957 958 if(!bCouldMergeSimple) 959 { 960 aResult.push_back(aCandidate); 961 } 962 } 963 else 964 { 965 aResult.push_back(aCandidate); 966 } 967 } 968 969 aInput = aResult; 970 } 971 972 // second step: melt pairwise to a single PolyPolygon 973 while(aInput.size() > 1) 974 { 975 std::vector< basegfx::B2DPolyPolygon > aResult; 976 aResult.reserve((aInput.size() / 2) + 1); 977 978 for(sal_uInt32 a(0); a < aInput.size(); a += 2) 979 { 980 if(a + 1 < aInput.size()) 981 { 982 // a pair for processing 983 aResult.push_back(solvePolygonOperationOr(aInput[a], aInput[a + 1])); 984 } 985 else 986 { 987 // last single PolyPolygon; copy to target to not lose it 988 aResult.push_back(aInput[a]); 989 } 990 } 991 992 aInput = aResult; 993 } 994 995 // third step: get result 996 if(1 == aInput.size()) 997 { 998 return aInput[0]; 999 } 1000 1001 return B2DPolyPolygon(); 1002 } 1003 1004 ////////////////////////////////////////////////////////////////////////////// 1005 1006 } // end of namespace tools 1007 } // end of namespace basegfx 1008 1009 ////////////////////////////////////////////////////////////////////////////// 1010 // eof 1011