basegfx/source/polygon/b2dpolygoncutandtouch.cxx

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