basegfx/source/polygon/b2dpolygoncutandtouch.cxx

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