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