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