basegfx/source/polygon/b2dpolygoncutandtouch.cxx

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