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 createNonzeroConform(const B2DPolyPolygon& rCandidate) 705 { 706 B2DPolyPolygon aCandidate; 707 708 // remove all self-intersections and intersections 709 if(rCandidate.count() == 1) 710 { 711 aCandidate = basegfx::tools::solveCrossovers(rCandidate.getB2DPolygon(0)); 712 } 713 else 714 { 715 aCandidate = basegfx::tools::solveCrossovers(rCandidate); 716 } 717 718 // cleanup evtl. neutral polygons 719 aCandidate = basegfx::tools::stripNeutralPolygons(aCandidate); 720 721 // remove all polygons which have the same orientation as the polygon they are directly contained in 722 const sal_uInt32 nCount(aCandidate.count()); 723 724 if(nCount > 1) 725 { 726 sal_uInt32 a, b; 727 ::std::vector< StripHelper > aHelpers; 728 aHelpers.resize(nCount); 729 730 for(a = 0; a < nCount; a++) 731 { 732 const B2DPolygon aCand(aCandidate.getB2DPolygon(a)); 733 StripHelper* pNewHelper = &(aHelpers[a]); 734 pNewHelper->maRange = tools::getRange(aCand); 735 pNewHelper->meOrinetation = tools::getOrientation(aCand); 736 737 // initialize with own orientation 738 pNewHelper->mnDepth = (ORIENTATION_NEGATIVE == pNewHelper->meOrinetation ? -1 : 1); 739 } 740 741 for(a = 0; a < nCount - 1; a++) 742 { 743 const B2DPolygon aCandA(aCandidate.getB2DPolygon(a)); 744 StripHelper& rHelperA = aHelpers[a]; 745 746 for(b = a + 1; b < nCount; b++) 747 { 748 const B2DPolygon aCandB(aCandidate.getB2DPolygon(b)); 749 StripHelper& rHelperB = aHelpers[b]; 750 const bool bAInB(rHelperB.maRange.isInside(rHelperA.maRange) && tools::isInside(aCandB, aCandA, true)); 751 752 if(bAInB) 753 { 754 // A is inside B, add orientation of B to A 755 rHelperA.mnDepth += (ORIENTATION_NEGATIVE == rHelperB.meOrinetation ? -1 : 1); 756 } 757 758 const bool bBInA(rHelperA.maRange.isInside(rHelperB.maRange) && tools::isInside(aCandA, aCandB, true)); 759 760 if(bBInA) 761 { 762 // B is inside A, add orientation of A to B 763 rHelperB.mnDepth += (ORIENTATION_NEGATIVE == rHelperA.meOrinetation ? -1 : 1); 764 } 765 } 766 } 767 768 const B2DPolyPolygon aSource(aCandidate); 769 aCandidate.clear(); 770 771 for(a = 0L; a < nCount; a++) 772 { 773 const StripHelper& rHelper = aHelpers[a]; 774 // for contained unequal oriented polygons sum will be 0 775 // for contained equal it will be >=2 or <=-2 776 // for free polygons (not contained) it will be 1 or -1 777 // -> accept all which are >=-1 && <= 1 778 bool bAcceptEntry(rHelper.mnDepth >= -1 && rHelper.mnDepth <= 1); 779 780 if(bAcceptEntry) 781 { 782 aCandidate.append(aSource.getB2DPolygon(a)); 783 } 784 } 785 } 786 787 return aCandidate; 788 } 789 790 ////////////////////////////////////////////////////////////////////////////// 791 792 B2DPolyPolygon stripDispensablePolygons(const B2DPolyPolygon& rCandidate, bool bKeepAboveZero) 793 { 794 const sal_uInt32 nCount(rCandidate.count()); 795 B2DPolyPolygon aRetval; 796 797 if(nCount) 798 { 799 if(nCount == 1L) 800 { 801 if(!bKeepAboveZero && ORIENTATION_POSITIVE == tools::getOrientation(rCandidate.getB2DPolygon(0L))) 802 { 803 aRetval = rCandidate; 804 } 805 } 806 else 807 { 808 sal_uInt32 a, b; 809 ::std::vector< StripHelper > aHelpers; 810 aHelpers.resize(nCount); 811 812 for(a = 0L; a < nCount; a++) 813 { 814 const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a)); 815 StripHelper* pNewHelper = &(aHelpers[a]); 816 pNewHelper->maRange = tools::getRange(aCandidate); 817 pNewHelper->meOrinetation = tools::getOrientation(aCandidate); 818 pNewHelper->mnDepth = (ORIENTATION_NEGATIVE == pNewHelper->meOrinetation ? -1L : 0L); 819 } 820 821 for(a = 0L; a < nCount - 1L; a++) 822 { 823 const B2DPolygon aCandA(rCandidate.getB2DPolygon(a)); 824 StripHelper& rHelperA = aHelpers[a]; 825 826 for(b = a + 1L; b < nCount; b++) 827 { 828 const B2DPolygon aCandB(rCandidate.getB2DPolygon(b)); 829 StripHelper& rHelperB = aHelpers[b]; 830 const bool bAInB(rHelperB.maRange.isInside(rHelperA.maRange) && tools::isInside(aCandB, aCandA, true)); 831 const bool bBInA(rHelperA.maRange.isInside(rHelperB.maRange) && tools::isInside(aCandA, aCandB, true)); 832 833 if(bAInB && bBInA) 834 { 835 // congruent 836 if(rHelperA.meOrinetation == rHelperB.meOrinetation) 837 { 838 // two polys or two holes. Lower one of them to get one of them out of the way. 839 // Since each will be contained in the other one, both will be increased, too. 840 // So, for lowering, increase only one of them 841 rHelperA.mnDepth++; 842 } 843 else 844 { 845 // poly and hole. They neutralize, so get rid of both. Move securely below zero. 846 rHelperA.mnDepth = -((sal_Int32)nCount); 847 rHelperB.mnDepth = -((sal_Int32)nCount); 848 } 849 } 850 else 851 { 852 if(bAInB) 853 { 854 if(ORIENTATION_NEGATIVE == rHelperB.meOrinetation) 855 { 856 rHelperA.mnDepth--; 857 } 858 else 859 { 860 rHelperA.mnDepth++; 861 } 862 } 863 else if(bBInA) 864 { 865 if(ORIENTATION_NEGATIVE == rHelperA.meOrinetation) 866 { 867 rHelperB.mnDepth--; 868 } 869 else 870 { 871 rHelperB.mnDepth++; 872 } 873 } 874 } 875 } 876 } 877 878 for(a = 0L; a < nCount; a++) 879 { 880 const StripHelper& rHelper = aHelpers[a]; 881 bool bAcceptEntry(bKeepAboveZero ? 1L <= rHelper.mnDepth : 0L == rHelper.mnDepth); 882 883 if(bAcceptEntry) 884 { 885 aRetval.append(rCandidate.getB2DPolygon(a)); 886 } 887 } 888 } 889 } 890 891 return aRetval; 892 } 893 894 ////////////////////////////////////////////////////////////////////////////// 895 896 B2DPolyPolygon prepareForPolygonOperation(const B2DPolygon& rCandidate) 897 { 898 solver aSolver(rCandidate); 899 B2DPolyPolygon aRetval(stripNeutralPolygons(aSolver.getB2DPolyPolygon())); 900 901 return correctOrientations(aRetval); 902 } 903 904 B2DPolyPolygon prepareForPolygonOperation(const B2DPolyPolygon& rCandidate) 905 { 906 solver aSolver(rCandidate); 907 B2DPolyPolygon aRetval(stripNeutralPolygons(aSolver.getB2DPolyPolygon())); 908 909 return correctOrientations(aRetval); 910 } 911 912 B2DPolyPolygon solvePolygonOperationOr(const B2DPolyPolygon& rCandidateA, const B2DPolyPolygon& rCandidateB) 913 { 914 if(!rCandidateA.count()) 915 { 916 return rCandidateB; 917 } 918 else if(!rCandidateB.count()) 919 { 920 return rCandidateA; 921 } 922 else 923 { 924 // concatenate polygons, solve crossovers and throw away all sub-polygons 925 // which have a depth other than 0. 926 B2DPolyPolygon aRetval(rCandidateA); 927 928 aRetval.append(rCandidateB); 929 aRetval = solveCrossovers(aRetval); 930 aRetval = stripNeutralPolygons(aRetval); 931 932 return stripDispensablePolygons(aRetval, false); 933 } 934 } 935 936 B2DPolyPolygon solvePolygonOperationXor(const B2DPolyPolygon& rCandidateA, const B2DPolyPolygon& rCandidateB) 937 { 938 if(!rCandidateA.count()) 939 { 940 return rCandidateB; 941 } 942 else if(!rCandidateB.count()) 943 { 944 return rCandidateA; 945 } 946 else 947 { 948 // XOR is pretty simple: By definition it is the simple concatenation of 949 // the single polygons since we imply XOR fill rule. Make it intersection-free 950 // and correct orientations 951 B2DPolyPolygon aRetval(rCandidateA); 952 953 aRetval.append(rCandidateB); 954 aRetval = solveCrossovers(aRetval); 955 aRetval = stripNeutralPolygons(aRetval); 956 957 return correctOrientations(aRetval); 958 } 959 } 960 961 B2DPolyPolygon solvePolygonOperationAnd(const B2DPolyPolygon& rCandidateA, const B2DPolyPolygon& rCandidateB) 962 { 963 if(!rCandidateA.count()) 964 { 965 return B2DPolyPolygon(); 966 } 967 else if(!rCandidateB.count()) 968 { 969 return B2DPolyPolygon(); 970 } 971 else 972 { 973 // concatenate polygons, solve crossovers and throw away all sub-polygons 974 // with a depth of < 1. This means to keep all polygons where at least two 975 // polygons do overlap. 976 B2DPolyPolygon aRetval(rCandidateA); 977 978 aRetval.append(rCandidateB); 979 aRetval = solveCrossovers(aRetval); 980 aRetval = stripNeutralPolygons(aRetval); 981 982 return stripDispensablePolygons(aRetval, true); 983 } 984 } 985 986 B2DPolyPolygon solvePolygonOperationDiff(const B2DPolyPolygon& rCandidateA, const B2DPolyPolygon& rCandidateB) 987 { 988 if(!rCandidateA.count()) 989 { 990 return B2DPolyPolygon(); 991 } 992 else if(!rCandidateB.count()) 993 { 994 return rCandidateA; 995 } 996 else 997 { 998 // Make B topologically to holes and append to A 999 B2DPolyPolygon aRetval(rCandidateB); 1000 1001 aRetval.flip(); 1002 aRetval.append(rCandidateA); 1003 1004 // solve crossovers and throw away all sub-polygons which have a 1005 // depth other than 0. 1006 aRetval = basegfx::tools::solveCrossovers(aRetval); 1007 aRetval = basegfx::tools::stripNeutralPolygons(aRetval); 1008 1009 return basegfx::tools::stripDispensablePolygons(aRetval, false); 1010 } 1011 } 1012 1013 B2DPolyPolygon mergeToSinglePolyPolygon(const B2DPolyPolygonVector& rInput) 1014 { 1015 B2DPolyPolygonVector aInput(rInput); 1016 1017 // first step: prepareForPolygonOperation and simple merge of non-overlapping 1018 // PolyPolygons for speedup; this is possible for the wanted OR-operation 1019 if(aInput.size()) 1020 { 1021 B2DPolyPolygonVector aResult; 1022 aResult.reserve(aInput.size()); 1023 1024 for(sal_uInt32 a(0); a < aInput.size(); a++) 1025 { 1026 const basegfx::B2DPolyPolygon aCandidate(prepareForPolygonOperation(aInput[a])); 1027 1028 if(aResult.size()) 1029 { 1030 const B2DRange aCandidateRange(aCandidate.getB2DRange()); 1031 bool bCouldMergeSimple(false); 1032 1033 for(sal_uInt32 b(0); !bCouldMergeSimple && b < aResult.size(); b++) 1034 { 1035 basegfx::B2DPolyPolygon aTarget(aResult[b]); 1036 const B2DRange aTargetRange(aTarget.getB2DRange()); 1037 1038 if(!aCandidateRange.overlaps(aTargetRange)) 1039 { 1040 aTarget.append(aCandidate); 1041 aResult[b] = aTarget; 1042 bCouldMergeSimple = true; 1043 } 1044 } 1045 1046 if(!bCouldMergeSimple) 1047 { 1048 aResult.push_back(aCandidate); 1049 } 1050 } 1051 else 1052 { 1053 aResult.push_back(aCandidate); 1054 } 1055 } 1056 1057 aInput = aResult; 1058 } 1059 1060 // second step: melt pairwise to a single PolyPolygon 1061 while(aInput.size() > 1) 1062 { 1063 B2DPolyPolygonVector aResult; 1064 aResult.reserve((aInput.size() / 2) + 1); 1065 1066 for(sal_uInt32 a(0); a < aInput.size(); a += 2) 1067 { 1068 if(a + 1 < aInput.size()) 1069 { 1070 // a pair for processing 1071 aResult.push_back(solvePolygonOperationOr(aInput[a], aInput[a + 1])); 1072 } 1073 else 1074 { 1075 // last single PolyPolygon; copy to target to not lose it 1076 aResult.push_back(aInput[a]); 1077 } 1078 } 1079 1080 aInput = aResult; 1081 } 1082 1083 // third step: get result 1084 if(1 == aInput.size()) 1085 { 1086 return aInput[0]; 1087 } 1088 1089 return B2DPolyPolygon(); 1090 } 1091 1092 ////////////////////////////////////////////////////////////////////////////// 1093 1094 } // end of namespace tools 1095 } // end of namespace basegfx 1096 1097 ////////////////////////////////////////////////////////////////////////////// 1098 // eof 1099