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 <basegfx/polygon/b2dpolygoncutandtouch.hxx> 31 #include <osl/diagnose.h> 32 #include <basegfx/numeric/ftools.hxx> 33 #include <basegfx/point/b2dpoint.hxx> 34 #include <basegfx/vector/b2dvector.hxx> 35 #include <basegfx/range/b2drange.hxx> 36 #include <basegfx/polygon/b2dpolygontools.hxx> 37 #include <basegfx/polygon/b2dpolypolygontools.hxx> 38 #include <basegfx/curve/b2dcubicbezier.hxx> 39 40 #include <vector> 41 #include <algorithm> 42 43 ////////////////////////////////////////////////////////////////////////////// 44 // defines 45 46 #define SUBDIVIDE_FOR_CUT_TEST_COUNT (50) 47 48 ////////////////////////////////////////////////////////////////////////////// 49 50 namespace basegfx 51 { 52 namespace 53 { 54 //////////////////////////////////////////////////////////////////////////////// 55 56 class temporaryPoint 57 { 58 B2DPoint maPoint; // the new point 59 sal_uInt32 mnIndex; // index after which to insert 60 double mfCut; // parametric cut description [0.0 .. 1.0] 61 62 public: 63 temporaryPoint(const B2DPoint& rNewPoint, sal_uInt32 nIndex, double fCut) 64 : maPoint(rNewPoint), 65 mnIndex(nIndex), 66 mfCut(fCut) 67 { 68 } 69 70 bool operator<(const temporaryPoint& rComp) const 71 { 72 if(mnIndex == rComp.mnIndex) 73 { 74 return (mfCut < rComp.mfCut); 75 } 76 77 return (mnIndex < rComp.mnIndex); 78 } 79 80 const B2DPoint& getPoint() const { return maPoint; } 81 sal_uInt32 getIndex() const { return mnIndex; } 82 double getCut() const { return mfCut; } 83 }; 84 85 //////////////////////////////////////////////////////////////////////////////// 86 87 typedef ::std::vector< temporaryPoint > temporaryPointVector; 88 89 //////////////////////////////////////////////////////////////////////////////// 90 91 class temporaryPolygonData 92 { 93 B2DPolygon maPolygon; 94 B2DRange maRange; 95 temporaryPointVector maPoints; 96 97 public: 98 const B2DPolygon& getPolygon() const { return maPolygon; } 99 void setPolygon(const B2DPolygon& rNew) { maPolygon = rNew; maRange = tools::getRange(maPolygon); } 100 const B2DRange& getRange() const { return maRange; } 101 temporaryPointVector& getTemporaryPointVector() { return maPoints; } 102 }; 103 104 //////////////////////////////////////////////////////////////////////////////// 105 106 B2DPolygon mergeTemporaryPointsAndPolygon(const B2DPolygon& rCandidate, temporaryPointVector& rTempPoints) 107 { 108 // #i76891# mergeTemporaryPointsAndPolygon redesigned to be able to correctly handle 109 // single edges with/without control points 110 // #i101491# added counter for non-changing element count 111 const sal_uInt32 nTempPointCount(rTempPoints.size()); 112 113 if(nTempPointCount) 114 { 115 B2DPolygon aRetval; 116 const sal_uInt32 nCount(rCandidate.count()); 117 118 if(nCount) 119 { 120 // sort temp points to assure increasing fCut values and increasing indices 121 ::std::sort(rTempPoints.begin(), rTempPoints.end()); 122 123 // prepare loop 124 B2DCubicBezier aEdge; 125 sal_uInt32 nNewInd(0L); 126 127 // add start point 128 aRetval.append(rCandidate.getB2DPoint(0)); 129 130 for(sal_uInt32 a(0L); a < nCount; a++) 131 { 132 // get edge 133 rCandidate.getBezierSegment(a, aEdge); 134 135 if(aEdge.isBezier()) 136 { 137 // control vectors involved for this edge 138 double fLeftStart(0.0); 139 140 // now add all points targeted to be at this index 141 while(nNewInd < nTempPointCount && rTempPoints[nNewInd].getIndex() == a) 142 { 143 const temporaryPoint& rTempPoint = rTempPoints[nNewInd++]; 144 145 // split curve segment. Splits need to come sorted and need to be < 1.0. Also, 146 // since original segment is consumed from left to right, the cut values need 147 // to be scaled to the remaining part 148 B2DCubicBezier aLeftPart; 149 const double fRelativeSplitPoint((rTempPoint.getCut() - fLeftStart) / (1.0 - fLeftStart)); 150 aEdge.split(fRelativeSplitPoint, &aLeftPart, &aEdge); 151 fLeftStart = rTempPoint.getCut(); 152 153 // add left bow 154 aRetval.appendBezierSegment(aLeftPart.getControlPointA(), aLeftPart.getControlPointB(), rTempPoint.getPoint()); 155 } 156 157 // add remaining bow 158 aRetval.appendBezierSegment(aEdge.getControlPointA(), aEdge.getControlPointB(), aEdge.getEndPoint()); 159 } 160 else 161 { 162 // add all points targeted to be at this index 163 while(nNewInd < nTempPointCount && rTempPoints[nNewInd].getIndex() == a) 164 { 165 const temporaryPoint& rTempPoint = rTempPoints[nNewInd++]; 166 const B2DPoint aNewPoint(rTempPoint.getPoint()); 167 168 // do not add points double 169 if(!aRetval.getB2DPoint(aRetval.count() - 1L).equal(aNewPoint)) 170 { 171 aRetval.append(aNewPoint); 172 } 173 } 174 175 // add edge end point 176 aRetval.append(aEdge.getEndPoint()); 177 } 178 } 179 } 180 181 if(rCandidate.isClosed()) 182 { 183 // set closed flag and correct last point (which is added double now). 184 tools::closeWithGeometryChange(aRetval); 185 } 186 187 return aRetval; 188 } 189 else 190 { 191 return rCandidate; 192 } 193 } 194 195 //////////////////////////////////////////////////////////////////////////////// 196 197 void adaptAndTransferCutsWithBezierSegment( 198 const temporaryPointVector& rPointVector, const B2DPolygon& rPolygon, 199 sal_uInt32 nInd, temporaryPointVector& rTempPoints) 200 { 201 // assuming that the subdivision to create rPolygon used aequidistant pieces 202 // (as in adaptiveSubdivideByCount) it is now possible to calculate back the 203 // cut positions in the polygon to relative cut positions on the original bezier 204 // segment. 205 const sal_uInt32 nTempPointCount(rPointVector.size()); 206 const sal_uInt32 nEdgeCount(rPolygon.count() ? rPolygon.count() - 1L : 0L); 207 208 if(nTempPointCount && nEdgeCount) 209 { 210 for(sal_uInt32 a(0L); a < nTempPointCount; a++) 211 { 212 const temporaryPoint& rTempPoint = rPointVector[a]; 213 const double fCutPosInPolygon((double)rTempPoint.getIndex() + rTempPoint.getCut()); 214 const double fRelativeCutPos(fCutPosInPolygon / (double)nEdgeCount); 215 rTempPoints.push_back(temporaryPoint(rTempPoint.getPoint(), nInd, fRelativeCutPos)); 216 } 217 } 218 } 219 220 //////////////////////////////////////////////////////////////////////////////// 221 222 } // end of anonymous namespace 223 } // end of namespace basegfx 224 225 ////////////////////////////////////////////////////////////////////////////// 226 227 namespace basegfx 228 { 229 namespace 230 { 231 //////////////////////////////////////////////////////////////////////////////// 232 // predefines for calls to this methods before method implementation 233 234 void findCuts(const B2DPolygon& rCandidate, temporaryPointVector& rTempPoints); 235 void findTouches(const B2DPolygon& rEdgePolygon, const B2DPolygon& rPointPolygon, temporaryPointVector& rTempPoints); 236 void findCuts(const B2DPolygon& rCandidateA, const B2DPolygon& rCandidateB, temporaryPointVector& rTempPointsA, temporaryPointVector& rTempPointsB); 237 238 //////////////////////////////////////////////////////////////////////////////// 239 240 void findEdgeCutsTwoEdges( 241 const B2DPoint& rCurrA, const B2DPoint& rNextA, 242 const B2DPoint& rCurrB, const B2DPoint& rNextB, 243 sal_uInt32 nIndA, sal_uInt32 nIndB, 244 temporaryPointVector& rTempPointsA, temporaryPointVector& rTempPointsB) 245 { 246 // no null length edges 247 if(!(rCurrA.equal(rNextA) || rCurrB.equal(rNextB))) 248 { 249 // no common start/end points, this can be no cuts 250 if(!(rCurrB.equal(rCurrA) || rCurrB.equal(rNextA) || rNextB.equal(rCurrA) || rNextB.equal(rNextA))) 251 { 252 const B2DVector aVecA(rNextA - rCurrA); 253 const B2DVector aVecB(rNextB - rCurrB); 254 double fCut(aVecA.cross(aVecB)); 255 256 if(!fTools::equalZero(fCut)) 257 { 258 const double fZero(0.0); 259 const double fOne(1.0); 260 fCut = (aVecB.getY() * (rCurrB.getX() - rCurrA.getX()) + aVecB.getX() * (rCurrA.getY() - rCurrB.getY())) / fCut; 261 262 if(fTools::more(fCut, fZero) && fTools::less(fCut, fOne)) 263 { 264 // it's a candidate, but also need to test parameter value of cut on line 2 265 double fCut2; 266 267 // choose the more precise version 268 if(fabs(aVecB.getX()) > fabs(aVecB.getY())) 269 { 270 fCut2 = (rCurrA.getX() + (fCut * aVecA.getX()) - rCurrB.getX()) / aVecB.getX(); 271 } 272 else 273 { 274 fCut2 = (rCurrA.getY() + (fCut * aVecA.getY()) - rCurrB.getY()) / aVecB.getY(); 275 } 276 277 if(fTools::more(fCut2, fZero) && fTools::less(fCut2, fOne)) 278 { 279 // cut is in range, add point. Two edges can have only one cut, but 280 // add a cut point to each list. The lists may be the same for 281 // self intersections. 282 const B2DPoint aCutPoint(interpolate(rCurrA, rNextA, fCut)); 283 rTempPointsA.push_back(temporaryPoint(aCutPoint, nIndA, fCut)); 284 rTempPointsB.push_back(temporaryPoint(aCutPoint, nIndB, fCut2)); 285 } 286 } 287 } 288 } 289 } 290 } 291 292 //////////////////////////////////////////////////////////////////////////////// 293 294 void findCutsAndTouchesAndCommonForBezier(const B2DPolygon& rCandidateA, const B2DPolygon& rCandidateB, temporaryPointVector& rTempPointsA, temporaryPointVector& rTempPointsB) 295 { 296 // #i76891# 297 // This new method is necessary since in findEdgeCutsBezierAndEdge and in findEdgeCutsTwoBeziers 298 // it is not sufficient to use findCuts() recursively. This will indeed find the cuts between the 299 // segments of the two temporarily adaptive subdivided bezier segments, but not the touches or 300 // equal points of them. 301 // It would be possible to find the toches using findTouches(), but at last with commpn points 302 // the adding of cut points (temporary points) would fail. But for these temporarily adaptive 303 // subdivided bezier segments, common points may be not very likely, but the bug shows that it 304 // happens. 305 // Touch points are a little bit more likely than common points. All in all it is best to use 306 // a specialized method here which can profit from knowing that it is working on a special 307 // family of B2DPolygons: no curve segments included and not closed. 308 OSL_ENSURE(!rCandidateA.areControlPointsUsed() && !rCandidateB.areControlPointsUsed(), "findCutsAndTouchesAndCommonForBezier only works with subdivided polygons (!)"); 309 OSL_ENSURE(!rCandidateA.isClosed() && !rCandidateB.isClosed(), "findCutsAndTouchesAndCommonForBezier only works with opened polygons (!)"); 310 const sal_uInt32 nPointCountA(rCandidateA.count()); 311 const sal_uInt32 nPointCountB(rCandidateB.count()); 312 313 if(nPointCountA > 1 && nPointCountB > 1) 314 { 315 const sal_uInt32 nEdgeCountA(nPointCountA - 1); 316 const sal_uInt32 nEdgeCountB(nPointCountB - 1); 317 B2DPoint aCurrA(rCandidateA.getB2DPoint(0L)); 318 319 for(sal_uInt32 a(0L); a < nEdgeCountA; a++) 320 { 321 const B2DPoint aNextA(rCandidateA.getB2DPoint(a + 1L)); 322 const B2DRange aRangeA(aCurrA, aNextA); 323 B2DPoint aCurrB(rCandidateB.getB2DPoint(0L)); 324 325 for(sal_uInt32 b(0L); b < nEdgeCountB; b++) 326 { 327 const B2DPoint aNextB(rCandidateB.getB2DPoint(b + 1L)); 328 const B2DRange aRangeB(aCurrB, aNextB); 329 330 if(aRangeA.overlaps(aRangeB)) 331 { 332 // no null length edges 333 if(!(aCurrA.equal(aNextA) || aCurrB.equal(aNextB))) 334 { 335 const B2DVector aVecA(aNextA - aCurrA); 336 const B2DVector aVecB(aNextB - aCurrB); 337 double fCutA(aVecA.cross(aVecB)); 338 339 if(!fTools::equalZero(fCutA)) 340 { 341 const double fZero(0.0); 342 const double fOne(1.0); 343 fCutA = (aVecB.getY() * (aCurrB.getX() - aCurrA.getX()) + aVecB.getX() * (aCurrA.getY() - aCurrB.getY())) / fCutA; 344 345 // use range [0.0 .. 1.0[, thus in the loop, all direct aCurrA cuts will be registered 346 // as 0.0 cut. The 1.0 cut will be registered in the next loop step 347 if(fTools::moreOrEqual(fCutA, fZero) && fTools::less(fCutA, fOne)) 348 { 349 // it's a candidate, but also need to test parameter value of cut on line 2 350 double fCutB; 351 352 // choose the more precise version 353 if(fabs(aVecB.getX()) > fabs(aVecB.getY())) 354 { 355 fCutB = (aCurrA.getX() + (fCutA * aVecA.getX()) - aCurrB.getX()) / aVecB.getX(); 356 } 357 else 358 { 359 fCutB = (aCurrA.getY() + (fCutA * aVecA.getY()) - aCurrB.getY()) / aVecB.getY(); 360 } 361 362 // use range [0.0 .. 1.0[, thus in the loop, all direct aCurrA cuts will be registered 363 // as 0.0 cut. The 1.0 cut will be registered in the next loop step 364 if(fTools::moreOrEqual(fCutB, fZero) && fTools::less(fCutB, fOne)) 365 { 366 // cut is in both ranges. Add points for A and B 367 // #i111715# use fTools::equal instead of fTools::equalZero for better accuracy 368 if(fTools::equal(fCutA, fZero)) 369 { 370 // ignore for start point in first edge; this is handled 371 // by outer methods and would just produce a double point 372 if(a) 373 { 374 rTempPointsA.push_back(temporaryPoint(aCurrA, a, 0.0)); 375 } 376 } 377 else 378 { 379 const B2DPoint aCutPoint(interpolate(aCurrA, aNextA, fCutA)); 380 rTempPointsA.push_back(temporaryPoint(aCutPoint, a, fCutA)); 381 } 382 383 // #i111715# use fTools::equal instead of fTools::equalZero for better accuracy 384 if(fTools::equal(fCutB, fZero)) 385 { 386 // ignore for start point in first edge; this is handled 387 // by outer methods and would just produce a double point 388 if(b) 389 { 390 rTempPointsB.push_back(temporaryPoint(aCurrB, b, 0.0)); 391 } 392 } 393 else 394 { 395 const B2DPoint aCutPoint(interpolate(aCurrB, aNextB, fCutB)); 396 rTempPointsB.push_back(temporaryPoint(aCutPoint, b, fCutB)); 397 } 398 } 399 } 400 } 401 } 402 } 403 404 // prepare next step 405 aCurrB = aNextB; 406 } 407 408 // prepare next step 409 aCurrA = aNextA; 410 } 411 } 412 } 413 414 //////////////////////////////////////////////////////////////////////////////// 415 416 void findEdgeCutsBezierAndEdge( 417 const B2DCubicBezier& rCubicA, 418 const B2DPoint& rCurrB, const B2DPoint& rNextB, 419 sal_uInt32 nIndA, sal_uInt32 nIndB, 420 temporaryPointVector& rTempPointsA, temporaryPointVector& rTempPointsB) 421 { 422 // find all cuts between given bezier segment and edge. Add an entry to the tempPoints 423 // for each common point with the cut value describing the relative position on given 424 // bezier segment and edge. 425 B2DPolygon aTempPolygonA; 426 B2DPolygon aTempPolygonEdge; 427 temporaryPointVector aTempPointVectorA; 428 temporaryPointVector aTempPointVectorEdge; 429 430 // create subdivided polygons and find cuts between them 431 // Keep adaptiveSubdivideByCount due to needed quality 432 aTempPolygonA.reserve(SUBDIVIDE_FOR_CUT_TEST_COUNT + 8); 433 aTempPolygonA.append(rCubicA.getStartPoint()); 434 rCubicA.adaptiveSubdivideByCount(aTempPolygonA, SUBDIVIDE_FOR_CUT_TEST_COUNT); 435 aTempPolygonEdge.append(rCurrB); 436 aTempPolygonEdge.append(rNextB); 437 438 // #i76891# using findCuts recursively is not sufficient here 439 findCutsAndTouchesAndCommonForBezier(aTempPolygonA, aTempPolygonEdge, aTempPointVectorA, aTempPointVectorEdge); 440 441 if(aTempPointVectorA.size()) 442 { 443 // adapt tempVector entries to segment 444 adaptAndTransferCutsWithBezierSegment(aTempPointVectorA, aTempPolygonA, nIndA, rTempPointsA); 445 } 446 447 // append remapped tempVector entries for edge to tempPoints for edge 448 for(sal_uInt32 a(0L); a < aTempPointVectorEdge.size(); a++) 449 { 450 const temporaryPoint& rTempPoint = aTempPointVectorEdge[a]; 451 rTempPointsB.push_back(temporaryPoint(rTempPoint.getPoint(), nIndB, rTempPoint.getCut())); 452 } 453 } 454 455 //////////////////////////////////////////////////////////////////////////////// 456 457 void findEdgeCutsTwoBeziers( 458 const B2DCubicBezier& rCubicA, 459 const B2DCubicBezier& rCubicB, 460 sal_uInt32 nIndA, sal_uInt32 nIndB, 461 temporaryPointVector& rTempPointsA, temporaryPointVector& rTempPointsB) 462 { 463 // find all cuts between the two given bezier segments. Add an entry to the tempPoints 464 // for each common point with the cut value describing the relative position on given 465 // bezier segments. 466 B2DPolygon aTempPolygonA; 467 B2DPolygon aTempPolygonB; 468 temporaryPointVector aTempPointVectorA; 469 temporaryPointVector aTempPointVectorB; 470 471 // create subdivided polygons and find cuts between them 472 // Keep adaptiveSubdivideByCount due to needed quality 473 aTempPolygonA.reserve(SUBDIVIDE_FOR_CUT_TEST_COUNT + 8); 474 aTempPolygonA.append(rCubicA.getStartPoint()); 475 rCubicA.adaptiveSubdivideByCount(aTempPolygonA, SUBDIVIDE_FOR_CUT_TEST_COUNT); 476 aTempPolygonB.reserve(SUBDIVIDE_FOR_CUT_TEST_COUNT + 8); 477 aTempPolygonB.append(rCubicB.getStartPoint()); 478 rCubicB.adaptiveSubdivideByCount(aTempPolygonB, SUBDIVIDE_FOR_CUT_TEST_COUNT); 479 480 // #i76891# using findCuts recursively is not sufficient here 481 findCutsAndTouchesAndCommonForBezier(aTempPolygonA, aTempPolygonB, aTempPointVectorA, aTempPointVectorB); 482 483 if(aTempPointVectorA.size()) 484 { 485 // adapt tempVector entries to segment 486 adaptAndTransferCutsWithBezierSegment(aTempPointVectorA, aTempPolygonA, nIndA, rTempPointsA); 487 } 488 489 if(aTempPointVectorB.size()) 490 { 491 // adapt tempVector entries to segment 492 adaptAndTransferCutsWithBezierSegment(aTempPointVectorB, aTempPolygonB, nIndB, rTempPointsB); 493 } 494 } 495 496 //////////////////////////////////////////////////////////////////////////////// 497 498 void findEdgeCutsOneBezier( 499 const B2DCubicBezier& rCubicA, 500 sal_uInt32 nInd, temporaryPointVector& rTempPoints) 501 { 502 // avoid expensive part of this method if possible 503 // TODO: use hasAnyExtremum() method instead when it becomes available 504 double fDummy; 505 const bool bHasAnyExtremum = rCubicA.getMinimumExtremumPosition( fDummy ); 506 if( !bHasAnyExtremum ) 507 return; 508 509 // find all self-intersections on the given bezier segment. Add an entry to the tempPoints 510 // for each self intersection point with the cut value describing the relative position on given 511 // bezier segment. 512 B2DPolygon aTempPolygon; 513 temporaryPointVector aTempPointVector; 514 515 // create subdivided polygon and find cuts on it 516 // Keep adaptiveSubdivideByCount due to needed quality 517 aTempPolygon.reserve(SUBDIVIDE_FOR_CUT_TEST_COUNT + 8); 518 aTempPolygon.append(rCubicA.getStartPoint()); 519 rCubicA.adaptiveSubdivideByCount(aTempPolygon, SUBDIVIDE_FOR_CUT_TEST_COUNT); 520 findCuts(aTempPolygon, aTempPointVector); 521 522 if(aTempPointVector.size()) 523 { 524 // adapt tempVector entries to segment 525 adaptAndTransferCutsWithBezierSegment(aTempPointVector, aTempPolygon, nInd, rTempPoints); 526 } 527 } 528 529 //////////////////////////////////////////////////////////////////////////////// 530 531 void findCuts(const B2DPolygon& rCandidate, temporaryPointVector& rTempPoints) 532 { 533 // find out if there are edges with intersections (self-cuts). If yes, add 534 // entries to rTempPoints accordingly 535 const sal_uInt32 nPointCount(rCandidate.count()); 536 537 if(nPointCount) 538 { 539 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1L); 540 541 if(nEdgeCount) 542 { 543 const bool bCurvesInvolved(rCandidate.areControlPointsUsed()); 544 545 if(bCurvesInvolved) 546 { 547 B2DCubicBezier aCubicA; 548 B2DCubicBezier aCubicB; 549 550 for(sal_uInt32 a(0L); a < nEdgeCount - 1L; a++) 551 { 552 rCandidate.getBezierSegment(a, aCubicA); 553 aCubicA.testAndSolveTrivialBezier(); 554 const bool bEdgeAIsCurve(aCubicA.isBezier()); 555 const B2DRange aRangeA(aCubicA.getRange()); 556 557 if(bEdgeAIsCurve) 558 { 559 // curved segments may have self-intersections, do not forget those (!) 560 findEdgeCutsOneBezier(aCubicA, a, rTempPoints); 561 } 562 563 for(sal_uInt32 b(a + 1L); b < nEdgeCount; b++) 564 { 565 rCandidate.getBezierSegment(b, aCubicB); 566 aCubicB.testAndSolveTrivialBezier(); 567 const bool bEdgeBIsCurve(aCubicB.isBezier()); 568 const B2DRange aRangeB(aCubicB.getRange()); 569 570 // only overlapping segments need to be tested 571 // consecutive segments touch of course 572 bool bOverlap = false; 573 if( b > a+1) 574 bOverlap = aRangeA.overlaps(aRangeB); 575 else 576 bOverlap = aRangeA.overlapsMore(aRangeB); 577 if( bOverlap) 578 { 579 if(bEdgeAIsCurve && bEdgeBIsCurve) 580 { 581 // test for bezier-bezier cuts 582 findEdgeCutsTwoBeziers(aCubicA, aCubicB, a, b, rTempPoints, rTempPoints); 583 } 584 else if(bEdgeAIsCurve) 585 { 586 // test for bezier-edge cuts 587 findEdgeCutsBezierAndEdge(aCubicA, aCubicB.getStartPoint(), aCubicB.getEndPoint(), a, b, rTempPoints, rTempPoints); 588 } 589 else if(bEdgeBIsCurve) 590 { 591 // test for bezier-edge cuts 592 findEdgeCutsBezierAndEdge(aCubicB, aCubicA.getStartPoint(), aCubicA.getEndPoint(), b, a, rTempPoints, rTempPoints); 593 } 594 else 595 { 596 // test for simple edge-edge cuts 597 findEdgeCutsTwoEdges(aCubicA.getStartPoint(), aCubicA.getEndPoint(), aCubicB.getStartPoint(), aCubicB.getEndPoint(), 598 a, b, rTempPoints, rTempPoints); 599 } 600 } 601 } 602 } 603 } 604 else 605 { 606 B2DPoint aCurrA(rCandidate.getB2DPoint(0L)); 607 608 for(sal_uInt32 a(0L); a < nEdgeCount - 1L; a++) 609 { 610 const B2DPoint aNextA(rCandidate.getB2DPoint(a + 1L == nPointCount ? 0L : a + 1L)); 611 const B2DRange aRangeA(aCurrA, aNextA); 612 B2DPoint aCurrB(rCandidate.getB2DPoint(a + 1L)); 613 614 for(sal_uInt32 b(a + 1L); b < nEdgeCount; b++) 615 { 616 const B2DPoint aNextB(rCandidate.getB2DPoint(b + 1L == nPointCount ? 0L : b + 1L)); 617 const B2DRange aRangeB(aCurrB, aNextB); 618 619 // consecutive segments touch of course 620 bool bOverlap = false; 621 if( b > a+1) 622 bOverlap = aRangeA.overlaps(aRangeB); 623 else 624 bOverlap = aRangeA.overlapsMore(aRangeB); 625 if( bOverlap) 626 { 627 findEdgeCutsTwoEdges(aCurrA, aNextA, aCurrB, aNextB, a, b, rTempPoints, rTempPoints); 628 } 629 630 // prepare next step 631 aCurrB = aNextB; 632 } 633 634 // prepare next step 635 aCurrA = aNextA; 636 } 637 } 638 } 639 } 640 } 641 642 //////////////////////////////////////////////////////////////////////////////// 643 644 } // end of anonymous namespace 645 } // end of namespace basegfx 646 647 ////////////////////////////////////////////////////////////////////////////// 648 649 namespace basegfx 650 { 651 namespace 652 { 653 //////////////////////////////////////////////////////////////////////////////// 654 655 void findTouchesOnEdge( 656 const B2DPoint& rCurr, const B2DPoint& rNext, const B2DPolygon& rPointPolygon, 657 sal_uInt32 nInd, temporaryPointVector& rTempPoints) 658 { 659 // find out if points from rPointPolygon are positioned on given edge. If Yes, add 660 // points there to represent touches (which may be enter or leave nodes later). 661 const sal_uInt32 nPointCount(rPointPolygon.count()); 662 663 if(nPointCount) 664 { 665 const B2DRange aRange(rCurr, rNext); 666 const B2DVector aEdgeVector(rNext - rCurr); 667 B2DVector aNormalizedEdgeVector(aEdgeVector); 668 aNormalizedEdgeVector.normalize(); 669 bool bTestUsingX(fabs(aEdgeVector.getX()) > fabs(aEdgeVector.getY())); 670 671 for(sal_uInt32 a(0L); a < nPointCount; a++) 672 { 673 const B2DPoint aTestPoint(rPointPolygon.getB2DPoint(a)); 674 675 if(aRange.isInside(aTestPoint)) 676 { 677 if(!aTestPoint.equal(rCurr) && !aTestPoint.equal(rNext)) 678 { 679 const B2DVector aTestVector(aTestPoint - rCurr); 680 681 if(areParallel(aNormalizedEdgeVector, aTestVector)) 682 { 683 const double fCut((bTestUsingX) 684 ? aTestVector.getX() / aEdgeVector.getX() 685 : aTestVector.getY() / aEdgeVector.getY()); 686 const double fZero(0.0); 687 const double fOne(1.0); 688 689 if(fTools::more(fCut, fZero) && fTools::less(fCut, fOne)) 690 { 691 rTempPoints.push_back(temporaryPoint(aTestPoint, nInd, fCut)); 692 } 693 } 694 } 695 } 696 } 697 } 698 } 699 700 //////////////////////////////////////////////////////////////////////////////// 701 702 void findTouchesOnCurve( 703 const B2DCubicBezier& rCubicA, const B2DPolygon& rPointPolygon, 704 sal_uInt32 nInd, temporaryPointVector& rTempPoints) 705 { 706 // find all points from rPointPolygon which touch the given bezier segment. Add an entry 707 // for each touch to the given pointVector. The cut for that entry is the relative position on 708 // the given bezier segment. 709 B2DPolygon aTempPolygon; 710 temporaryPointVector aTempPointVector; 711 712 // create subdivided polygon and find cuts on it 713 // Keep adaptiveSubdivideByCount due to needed quality 714 aTempPolygon.reserve(SUBDIVIDE_FOR_CUT_TEST_COUNT + 8); 715 aTempPolygon.append(rCubicA.getStartPoint()); 716 rCubicA.adaptiveSubdivideByCount(aTempPolygon, SUBDIVIDE_FOR_CUT_TEST_COUNT); 717 findTouches(aTempPolygon, rPointPolygon, aTempPointVector); 718 719 if(aTempPointVector.size()) 720 { 721 // adapt tempVector entries to segment 722 adaptAndTransferCutsWithBezierSegment(aTempPointVector, aTempPolygon, nInd, rTempPoints); 723 } 724 } 725 726 //////////////////////////////////////////////////////////////////////////////// 727 728 void findTouches(const B2DPolygon& rEdgePolygon, const B2DPolygon& rPointPolygon, temporaryPointVector& rTempPoints) 729 { 730 // find out if points from rPointPolygon touch edges from rEdgePolygon. If yes, 731 // add entries to rTempPoints 732 const sal_uInt32 nPointCount(rPointPolygon.count()); 733 const sal_uInt32 nEdgePointCount(rEdgePolygon.count()); 734 735 if(nPointCount && nEdgePointCount) 736 { 737 const sal_uInt32 nEdgeCount(rEdgePolygon.isClosed() ? nEdgePointCount : nEdgePointCount - 1L); 738 B2DPoint aCurr(rEdgePolygon.getB2DPoint(0)); 739 740 for(sal_uInt32 a(0L); a < nEdgeCount; a++) 741 { 742 const sal_uInt32 nNextIndex((a + 1) % nEdgePointCount); 743 const B2DPoint aNext(rEdgePolygon.getB2DPoint(nNextIndex)); 744 745 if(!aCurr.equal(aNext)) 746 { 747 bool bHandleAsSimpleEdge(true); 748 749 if(rEdgePolygon.areControlPointsUsed()) 750 { 751 const B2DPoint aNextControlPoint(rEdgePolygon.getNextControlPoint(a)); 752 const B2DPoint aPrevControlPoint(rEdgePolygon.getPrevControlPoint(nNextIndex)); 753 const bool bEdgeIsCurve(!aNextControlPoint.equal(aCurr) || !aPrevControlPoint.equal(aNext)); 754 755 if(bEdgeIsCurve) 756 { 757 bHandleAsSimpleEdge = false; 758 const B2DCubicBezier aCubicA(aCurr, aNextControlPoint, aPrevControlPoint, aNext); 759 findTouchesOnCurve(aCubicA, rPointPolygon, a, rTempPoints); 760 } 761 } 762 763 if(bHandleAsSimpleEdge) 764 { 765 findTouchesOnEdge(aCurr, aNext, rPointPolygon, a, rTempPoints); 766 } 767 } 768 769 // next step 770 aCurr = aNext; 771 } 772 } 773 } 774 775 //////////////////////////////////////////////////////////////////////////////// 776 777 } // end of anonymous namespace 778 } // end of namespace basegfx 779 780 ////////////////////////////////////////////////////////////////////////////// 781 782 namespace basegfx 783 { 784 namespace 785 { 786 //////////////////////////////////////////////////////////////////////////////// 787 788 void findCuts(const B2DPolygon& rCandidateA, const B2DPolygon& rCandidateB, temporaryPointVector& rTempPointsA, temporaryPointVector& rTempPointsB) 789 { 790 // find out if edges from both polygons cut. If so, add entries to rTempPoints which 791 // should be added to the polygons accordingly 792 const sal_uInt32 nPointCountA(rCandidateA.count()); 793 const sal_uInt32 nPointCountB(rCandidateB.count()); 794 795 if(nPointCountA && nPointCountB) 796 { 797 const sal_uInt32 nEdgeCountA(rCandidateA.isClosed() ? nPointCountA : nPointCountA - 1L); 798 const sal_uInt32 nEdgeCountB(rCandidateB.isClosed() ? nPointCountB : nPointCountB - 1L); 799 800 if(nEdgeCountA && nEdgeCountB) 801 { 802 const bool bCurvesInvolved(rCandidateA.areControlPointsUsed() || rCandidateB.areControlPointsUsed()); 803 804 if(bCurvesInvolved) 805 { 806 B2DCubicBezier aCubicA; 807 B2DCubicBezier aCubicB; 808 809 for(sal_uInt32 a(0L); a < nEdgeCountA; a++) 810 { 811 rCandidateA.getBezierSegment(a, aCubicA); 812 aCubicA.testAndSolveTrivialBezier(); 813 const bool bEdgeAIsCurve(aCubicA.isBezier()); 814 const B2DRange aRangeA(aCubicA.getRange()); 815 816 for(sal_uInt32 b(0L); b < nEdgeCountB; b++) 817 { 818 rCandidateB.getBezierSegment(b, aCubicB); 819 aCubicB.testAndSolveTrivialBezier(); 820 const bool bEdgeBIsCurve(aCubicB.isBezier()); 821 const B2DRange aRangeB(aCubicB.getRange()); 822 823 // consecutive segments touch of course 824 bool bOverlap = false; 825 if( b > a+1) 826 bOverlap = aRangeA.overlaps(aRangeB); 827 else 828 bOverlap = aRangeA.overlapsMore(aRangeB); 829 if( bOverlap) 830 { 831 if(bEdgeAIsCurve && bEdgeBIsCurve) 832 { 833 // test for bezier-bezier cuts 834 findEdgeCutsTwoBeziers(aCubicA, aCubicB, a, b, rTempPointsA, rTempPointsB); 835 } 836 else if(bEdgeAIsCurve) 837 { 838 // test for bezier-edge cuts 839 findEdgeCutsBezierAndEdge(aCubicA, aCubicB.getStartPoint(), aCubicB.getEndPoint(), a, b, rTempPointsA, rTempPointsB); 840 } 841 else if(bEdgeBIsCurve) 842 { 843 // test for bezier-edge cuts 844 findEdgeCutsBezierAndEdge(aCubicB, aCubicA.getStartPoint(), aCubicA.getEndPoint(), b, a, rTempPointsB, rTempPointsA); 845 } 846 else 847 { 848 // test for simple edge-edge cuts 849 findEdgeCutsTwoEdges(aCubicA.getStartPoint(), aCubicA.getEndPoint(), aCubicB.getStartPoint(), aCubicB.getEndPoint(), 850 a, b, rTempPointsA, rTempPointsB); 851 } 852 } 853 } 854 } 855 } 856 else 857 { 858 B2DPoint aCurrA(rCandidateA.getB2DPoint(0L)); 859 860 for(sal_uInt32 a(0L); a < nEdgeCountA; a++) 861 { 862 const B2DPoint aNextA(rCandidateA.getB2DPoint(a + 1L == nPointCountA ? 0L : a + 1L)); 863 const B2DRange aRangeA(aCurrA, aNextA); 864 B2DPoint aCurrB(rCandidateB.getB2DPoint(0L)); 865 866 for(sal_uInt32 b(0L); b < nEdgeCountB; b++) 867 { 868 const B2DPoint aNextB(rCandidateB.getB2DPoint(b + 1L == nPointCountB ? 0L : b + 1L)); 869 const B2DRange aRangeB(aCurrB, aNextB); 870 871 // consecutive segments touch of course 872 bool bOverlap = false; 873 if( b > a+1) 874 bOverlap = aRangeA.overlaps(aRangeB); 875 else 876 bOverlap = aRangeA.overlapsMore(aRangeB); 877 if( bOverlap) 878 { 879 // test for simple edge-edge cuts 880 findEdgeCutsTwoEdges(aCurrA, aNextA, aCurrB, aNextB, a, b, rTempPointsA, rTempPointsB); 881 } 882 883 // prepare next step 884 aCurrB = aNextB; 885 } 886 887 // prepare next step 888 aCurrA = aNextA; 889 } 890 } 891 } 892 } 893 } 894 895 //////////////////////////////////////////////////////////////////////////////// 896 897 } // end of anonymous namespace 898 } // end of namespace basegfx 899 900 ////////////////////////////////////////////////////////////////////////////// 901 902 namespace basegfx 903 { 904 namespace tools 905 { 906 //////////////////////////////////////////////////////////////////////////////// 907 908 B2DPolygon addPointsAtCutsAndTouches(const B2DPolygon& rCandidate) 909 { 910 if(rCandidate.count()) 911 { 912 temporaryPointVector aTempPoints; 913 914 findTouches(rCandidate, rCandidate, aTempPoints); 915 findCuts(rCandidate, aTempPoints); 916 917 return mergeTemporaryPointsAndPolygon(rCandidate, aTempPoints); 918 } 919 else 920 { 921 return rCandidate; 922 } 923 } 924 925 //////////////////////////////////////////////////////////////////////////////// 926 927 B2DPolyPolygon addPointsAtCutsAndTouches(const B2DPolyPolygon& rCandidate, bool bSelfIntersections) 928 { 929 const sal_uInt32 nCount(rCandidate.count()); 930 931 if(nCount) 932 { 933 B2DPolyPolygon aRetval; 934 935 if(1L == nCount) 936 { 937 if(bSelfIntersections) 938 { 939 // remove self intersections 940 aRetval.append(addPointsAtCutsAndTouches(rCandidate.getB2DPolygon(0L))); 941 } 942 else 943 { 944 // copy source 945 aRetval = rCandidate; 946 } 947 } 948 else 949 { 950 // first solve self cuts and self touches for all contained single polygons 951 temporaryPolygonData *pTempData = new temporaryPolygonData[nCount]; 952 sal_uInt32 a, b; 953 954 for(a = 0L; a < nCount; a++) 955 { 956 if(bSelfIntersections) 957 { 958 // use polygons with solved self intersections 959 pTempData[a].setPolygon(addPointsAtCutsAndTouches(rCandidate.getB2DPolygon(a))); 960 } 961 else 962 { 963 // copy given polygons 964 pTempData[a].setPolygon(rCandidate.getB2DPolygon(a)); 965 } 966 } 967 968 // now cuts and touches between the polygons 969 for(a = 0L; a < nCount; a++) 970 { 971 for(b = 0L; b < nCount; b++) 972 { 973 if(a != b) 974 { 975 // look for touches, compare each edge polygon to all other points 976 if(pTempData[a].getRange().overlaps(pTempData[b].getRange())) 977 { 978 findTouches(pTempData[a].getPolygon(), pTempData[b].getPolygon(), pTempData[a].getTemporaryPointVector()); 979 } 980 } 981 982 if(a < b) 983 { 984 // look for cuts, compare each edge polygon to following ones 985 if(pTempData[a].getRange().overlaps(pTempData[b].getRange())) 986 { 987 findCuts(pTempData[a].getPolygon(), pTempData[b].getPolygon(), pTempData[a].getTemporaryPointVector(), pTempData[b].getTemporaryPointVector()); 988 } 989 } 990 } 991 } 992 993 // consolidate the result 994 for(a = 0L; a < nCount; a++) 995 { 996 aRetval.append(mergeTemporaryPointsAndPolygon(pTempData[a].getPolygon(), pTempData[a].getTemporaryPointVector())); 997 } 998 999 delete[] pTempData; 1000 } 1001 1002 return aRetval; 1003 } 1004 else 1005 { 1006 return rCandidate; 1007 } 1008 } 1009 1010 //////////////////////////////////////////////////////////////////////////////// 1011 1012 B2DPolygon addPointsAtCutsAndTouches(const B2DPolyPolygon& rMask, const B2DPolygon& rCandidate) 1013 { 1014 if(rCandidate.count()) 1015 { 1016 temporaryPointVector aTempPoints; 1017 temporaryPointVector aTempPointsUnused; 1018 1019 for(sal_uInt32 a(0L); a < rMask.count(); a++) 1020 { 1021 const B2DPolygon aPartMask(rMask.getB2DPolygon(a)); 1022 1023 findTouches(rCandidate, aPartMask, aTempPoints); 1024 findCuts(rCandidate, aPartMask, aTempPoints, aTempPointsUnused); 1025 } 1026 1027 return mergeTemporaryPointsAndPolygon(rCandidate, aTempPoints); 1028 } 1029 else 1030 { 1031 return rCandidate; 1032 } 1033 } 1034 1035 //////////////////////////////////////////////////////////////////////////////// 1036 1037 B2DPolyPolygon addPointsAtCutsAndTouches(const B2DPolyPolygon& rMask, const B2DPolyPolygon& rCandidate) 1038 { 1039 B2DPolyPolygon aRetval; 1040 1041 for(sal_uInt32 a(0L); a < rCandidate.count(); a++) 1042 { 1043 aRetval.append(addPointsAtCutsAndTouches(rMask, rCandidate.getB2DPolygon(a))); 1044 } 1045 1046 return aRetval; 1047 } 1048 1049 //////////////////////////////////////////////////////////////////////////////// 1050 1051 B2DPolygon addPointsAtCuts(const B2DPolygon& rCandidate, const B2DPoint& rStart, const B2DPoint& rEnd) 1052 { 1053 const sal_uInt32 nCount(rCandidate.count()); 1054 1055 if(nCount && !rStart.equal(rEnd)) 1056 { 1057 const B2DRange aPolygonRange(rCandidate.getB2DRange()); 1058 const B2DRange aEdgeRange(rStart, rEnd); 1059 1060 if(aPolygonRange.overlaps(aEdgeRange)) 1061 { 1062 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nCount : nCount - 1); 1063 temporaryPointVector aTempPoints; 1064 temporaryPointVector aUnusedTempPoints; 1065 B2DCubicBezier aCubic; 1066 1067 for(sal_uInt32 a(0); a < nEdgeCount; a++) 1068 { 1069 rCandidate.getBezierSegment(a, aCubic); 1070 B2DRange aCubicRange(aCubic.getStartPoint(), aCubic.getEndPoint()); 1071 1072 if(aCubic.isBezier()) 1073 { 1074 aCubicRange.expand(aCubic.getControlPointA()); 1075 aCubicRange.expand(aCubic.getControlPointB()); 1076 1077 if(aCubicRange.overlaps(aEdgeRange)) 1078 { 1079 findEdgeCutsBezierAndEdge(aCubic, rStart, rEnd, a, 0, aTempPoints, aUnusedTempPoints); 1080 } 1081 } 1082 else 1083 { 1084 if(aCubicRange.overlaps(aEdgeRange)) 1085 { 1086 findEdgeCutsTwoEdges(aCubic.getStartPoint(), aCubic.getEndPoint(), rStart, rEnd, a, 0, aTempPoints, aUnusedTempPoints); 1087 } 1088 } 1089 } 1090 1091 return mergeTemporaryPointsAndPolygon(rCandidate, aTempPoints); 1092 } 1093 } 1094 1095 return rCandidate; 1096 } 1097 1098 B2DPolyPolygon addPointsAtCuts(const B2DPolyPolygon& rCandidate, const B2DPoint& rStart, const B2DPoint& rEnd) 1099 { 1100 B2DPolyPolygon aRetval; 1101 1102 for(sal_uInt32 a(0); a < rCandidate.count(); a++) 1103 { 1104 aRetval.append(addPointsAtCuts(rCandidate.getB2DPolygon(a), rStart, rEnd)); 1105 } 1106 1107 return aRetval; 1108 } 1109 1110 //////////////////////////////////////////////////////////////////////////////// 1111 1112 B2DPolygon addPointsAtCuts(const B2DPolygon& rCandidate, const B2DPolyPolygon& rPolyMask) 1113 { 1114 const sal_uInt32 nCountA(rCandidate.count()); 1115 const sal_uInt32 nCountM(rPolyMask.count()); 1116 1117 if(nCountA && nCountM) 1118 { 1119 const B2DRange aRangeA(rCandidate.getB2DRange()); 1120 const B2DRange aRangeM(rPolyMask.getB2DRange()); 1121 1122 if(aRangeA.overlaps(aRangeM)) 1123 { 1124 const sal_uInt32 nEdgeCountA(rCandidate.isClosed() ? nCountA : nCountA - 1); 1125 temporaryPointVector aTempPointsA; 1126 temporaryPointVector aUnusedTempPointsB; 1127 1128 for(sal_uInt32 m(0); m < nCountM; m++) 1129 { 1130 const B2DPolygon aMask(rPolyMask.getB2DPolygon(m)); 1131 const sal_uInt32 nCountB(aMask.count()); 1132 1133 if(nCountB) 1134 { 1135 B2DCubicBezier aCubicA; 1136 B2DCubicBezier aCubicB; 1137 1138 for(sal_uInt32 a(0); a < nEdgeCountA; a++) 1139 { 1140 rCandidate.getBezierSegment(a, aCubicA); 1141 const bool bCubicAIsCurve(aCubicA.isBezier()); 1142 B2DRange aCubicRangeA(aCubicA.getStartPoint(), aCubicA.getEndPoint()); 1143 1144 if(bCubicAIsCurve) 1145 { 1146 aCubicRangeA.expand(aCubicA.getControlPointA()); 1147 aCubicRangeA.expand(aCubicA.getControlPointB()); 1148 } 1149 1150 for(sal_uInt32 b(0); b < nCountB; b++) 1151 { 1152 aMask.getBezierSegment(b, aCubicB); 1153 const bool bCubicBIsCurve(aCubicB.isBezier()); 1154 B2DRange aCubicRangeB(aCubicB.getStartPoint(), aCubicB.getEndPoint()); 1155 1156 if(bCubicBIsCurve) 1157 { 1158 aCubicRangeB.expand(aCubicB.getControlPointA()); 1159 aCubicRangeB.expand(aCubicB.getControlPointB()); 1160 } 1161 1162 if(aCubicRangeA.overlaps(aCubicRangeB)) 1163 { 1164 if(bCubicAIsCurve && bCubicBIsCurve) 1165 { 1166 findEdgeCutsTwoBeziers(aCubicA, aCubicB, a, b, aTempPointsA, aUnusedTempPointsB); 1167 } 1168 else if(bCubicAIsCurve) 1169 { 1170 findEdgeCutsBezierAndEdge(aCubicA, aCubicB.getStartPoint(), aCubicB.getEndPoint(), a, b, aTempPointsA, aUnusedTempPointsB); 1171 } 1172 else if(bCubicBIsCurve) 1173 { 1174 findEdgeCutsBezierAndEdge(aCubicB, aCubicA.getStartPoint(), aCubicA.getEndPoint(), b, a, aUnusedTempPointsB, aTempPointsA); 1175 } 1176 else 1177 { 1178 findEdgeCutsTwoEdges(aCubicA.getStartPoint(), aCubicA.getEndPoint(), aCubicB.getStartPoint(), aCubicB.getEndPoint(), a, b, aTempPointsA, aUnusedTempPointsB); 1179 } 1180 } 1181 } 1182 } 1183 } 1184 } 1185 1186 return mergeTemporaryPointsAndPolygon(rCandidate, aTempPointsA); 1187 } 1188 } 1189 1190 return rCandidate; 1191 } 1192 1193 B2DPolyPolygon addPointsAtCuts(const B2DPolyPolygon& rCandidate, const B2DPolyPolygon& rMask) 1194 { 1195 B2DPolyPolygon aRetval; 1196 1197 for(sal_uInt32 a(0); a < rCandidate.count(); a++) 1198 { 1199 aRetval.append(addPointsAtCuts(rCandidate.getB2DPolygon(a), rMask)); 1200 } 1201 1202 return aRetval; 1203 } 1204 1205 B2DPolygon addPointsAtCuts(const B2DPolygon& rCandidate) 1206 { 1207 if(rCandidate.count()) 1208 { 1209 temporaryPointVector aTempPoints; 1210 1211 findCuts(rCandidate, aTempPoints); 1212 1213 return mergeTemporaryPointsAndPolygon(rCandidate, aTempPoints); 1214 } 1215 else 1216 { 1217 return rCandidate; 1218 } 1219 } 1220 1221 B2DPolyPolygon addPointsAtCuts(const B2DPolyPolygon& rCandidate, bool bSelfIntersections) 1222 { 1223 const sal_uInt32 nCount(rCandidate.count()); 1224 1225 if(nCount) 1226 { 1227 B2DPolyPolygon aRetval; 1228 1229 if(1 == nCount) 1230 { 1231 if(bSelfIntersections) 1232 { 1233 // remove self intersections 1234 aRetval.append(addPointsAtCuts(rCandidate.getB2DPolygon(0))); 1235 } 1236 else 1237 { 1238 // copy source 1239 aRetval = rCandidate; 1240 } 1241 } 1242 else 1243 { 1244 // first solve self cuts for all contained single polygons 1245 temporaryPolygonData *pTempData = new temporaryPolygonData[nCount]; 1246 sal_uInt32 a, b; 1247 1248 for(a = 0; a < nCount; a++) 1249 { 1250 if(bSelfIntersections) 1251 { 1252 // use polygons with solved self intersections 1253 pTempData[a].setPolygon(addPointsAtCuts(rCandidate.getB2DPolygon(a))); 1254 } 1255 else 1256 { 1257 // copy given polygons 1258 pTempData[a].setPolygon(rCandidate.getB2DPolygon(a)); 1259 } 1260 } 1261 1262 // now cuts and touches between the polygons 1263 for(a = 0; a < nCount; a++) 1264 { 1265 for(b = 0; b < nCount; b++) 1266 { 1267 if(a < b) 1268 { 1269 // look for cuts, compare each edge polygon to following ones 1270 if(pTempData[a].getRange().overlaps(pTempData[b].getRange())) 1271 { 1272 findCuts(pTempData[a].getPolygon(), pTempData[b].getPolygon(), pTempData[a].getTemporaryPointVector(), pTempData[b].getTemporaryPointVector()); 1273 } 1274 } 1275 } 1276 } 1277 1278 // consolidate the result 1279 for(a = 0L; a < nCount; a++) 1280 { 1281 aRetval.append(mergeTemporaryPointsAndPolygon(pTempData[a].getPolygon(), pTempData[a].getTemporaryPointVector())); 1282 } 1283 1284 delete[] pTempData; 1285 } 1286 1287 return aRetval; 1288 } 1289 else 1290 { 1291 return rCandidate; 1292 } 1293 } 1294 1295 //////////////////////////////////////////////////////////////////////////////// 1296 1297 } // end of namespace tools 1298 } // end of namespace basegfx 1299 1300 ////////////////////////////////////////////////////////////////////////////// 1301 // eof 1302