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