basegfx/source/polygon/b2dpolygoncutandtouch.cxx

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