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 <sal/log.hxx>
  23 #include <basegfx/numeric/ftools.hxx>
  24 #include <basegfx/point/b2dpoint.hxx>
  25 #include <basegfx/vector/b2dvector.hxx>
  26 #include <basegfx/range/b2drange.hxx>
  27 #include <basegfx/polygon/b2dpolygontools.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 nEdgeCount(rPolygon.count() ? rPolygon.count() - 1 : 0);
 183
 184             if(!rPointVector.empty() && nEdgeCount)
 185             {
 186                 for( const auto& rTempPoint : rPointVector )
 187                 {
 188                     const double fCutPosInPolygon(static_cast<double>(rTempPoint.getIndex()) + rTempPoint.getCut());
 189                     const double fRelativeCutPos(fCutPosInPolygon / static_cast<double>(nEdgeCount));
 190                     rTempPoints.emplace_back(rTempPoint.getPoint(), nInd, fRelativeCutPos);
 191                 }
 192             }
 193         }
 194
 195     } // end of anonymous namespace
 196 } // end of namespace basegfx
 197
 198 namespace basegfx
 199 {
 200     namespace
 201     {
 202
 203         // predefines for calls to this methods before method implementation
 204
 205         void findCuts(const B2DPolygon& rCandidate, temporaryPointVector& rTempPoints, size_t* pPointLimit = nullptr);
 206         void findTouches(const B2DPolygon& rEdgePolygon, const B2DPolygon& rPointPolygon, temporaryPointVector& rTempPoints);
 207         void findCuts(const B2DPolygon& rCandidateA, const B2DPolygon& rCandidateB, temporaryPointVector& rTempPointsA, temporaryPointVector& rTempPointsB);
 208
 209         void findEdgeCutsTwoEdges(
 210             const B2DPoint& rCurrA, const B2DPoint& rNextA,
 211             const B2DPoint& rCurrB, const B2DPoint& rNextB,
 212             sal_uInt32 nIndA, sal_uInt32 nIndB,
 213             temporaryPointVector& rTempPointsA, temporaryPointVector& rTempPointsB)
 214         {
 215             // no null length edges
 216             if(rCurrA.equal(rNextA) || rCurrB.equal(rNextB))
 217                 return;
 218
 219             // no common start/end points, this can be no cuts
 220             if(rCurrB.equal(rCurrA) || rCurrB.equal(rNextA) || rNextB.equal(rCurrA) || rNextB.equal(rNextA))
 221                 return;
 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                 return;
 229
 230             const double fZero(0.0);
 231             const double fOne(1.0);
 232             fCut = (aVecB.getY() * (rCurrB.getX() - rCurrA.getX()) + aVecB.getX() * (rCurrA.getY() - rCurrB.getY())) / fCut;
 233
 234             if (!fTools::betweenOrEqualEither(fCut, fZero, fOne))
 235                 return;
 236
 237             // it's a candidate, but also need to test parameter value of cut on line 2
 238             double fCut2;
 239
 240             // choose the more precise version
 241             if(fabs(aVecB.getX()) > fabs(aVecB.getY()))
 242             {
 243                 fCut2 = (rCurrA.getX() + (fCut * aVecA.getX()) - rCurrB.getX()) / aVecB.getX();
 244             }
 245             else
 246             {
 247                 fCut2 = (rCurrA.getY() + (fCut * aVecA.getY()) - rCurrB.getY()) / aVecB.getY();
 248             }
 249
 250             if (fTools::betweenOrEqualEither(fCut2, fZero, fOne))
 251             {
 252                 // cut is in range, add point. Two edges can have only one cut, but
 253                 // add a cut point to each list. The lists may be the same for
 254                 // self intersections.
 255                 const B2DPoint aCutPoint(interpolate(rCurrA, rNextA, fCut));
 256                 rTempPointsA.emplace_back(aCutPoint, nIndA, fCut);
 257                 rTempPointsB.emplace_back(aCutPoint, nIndB, fCut2);
 258             }
 259         }
 260
 261         void findCutsAndTouchesAndCommonForBezier(const B2DPolygon& rCandidateA, const B2DPolygon& rCandidateB, temporaryPointVector& rTempPointsA, temporaryPointVector& rTempPointsB)
 262         {
 263             // #i76891#
 264             // This new method is necessary since in findEdgeCutsBezierAndEdge and in findEdgeCutsTwoBeziers
 265             // it is not sufficient to use findCuts() recursively. This will indeed find the cuts between the
 266             // segments of the two temporarily adaptive subdivided bezier segments, but not the touches or
 267             // equal points of them.
 268             // It would be possible to find the touches using findTouches(), but at last with common points
 269             // the adding of cut points (temporary points) would fail. But for these temporarily adaptive
 270             // subdivided bezier segments, common points may be not very likely, but the bug shows that it
 271             // happens.
 272             // Touch points are a little bit more likely than common points. All in all it is best to use
 273             // a specialized method here which can profit from knowing that it is working on a special
 274             // family of B2DPolygons: no curve segments included and not closed.
 275             OSL_ENSURE(!rCandidateA.areControlPointsUsed() && !rCandidateB.areControlPointsUsed(), "findCutsAndTouchesAndCommonForBezier only works with subdivided polygons (!)");
 276             OSL_ENSURE(!rCandidateA.isClosed() && !rCandidateB.isClosed(), "findCutsAndTouchesAndCommonForBezier only works with opened polygons (!)");
 277             const sal_uInt32 nPointCountA(rCandidateA.count());
 278             const sal_uInt32 nPointCountB(rCandidateB.count());
 279
 280             if(nPointCountA <= 1 || nPointCountB <= 1)
 281                 return;
 282
 283             const sal_uInt32 nEdgeCountA(nPointCountA - 1);
 284             const sal_uInt32 nEdgeCountB(nPointCountB - 1);
 285             B2DPoint aCurrA(rCandidateA.getB2DPoint(0));
 286
 287             for(sal_uInt32 a(0); a < nEdgeCountA; a++)
 288             {
 289                 const B2DPoint aNextA(rCandidateA.getB2DPoint(a + 1));
 290                 const B2DRange aRangeA(aCurrA, aNextA);
 291                 B2DPoint aCurrB(rCandidateB.getB2DPoint(0));
 292
 293                 for(sal_uInt32 b(0); b < nEdgeCountB; b++)
 294                 {
 295                     const B2DPoint aNextB(rCandidateB.getB2DPoint(b + 1));
 296                     const B2DRange aRangeB(aCurrB, aNextB);
 297
 298                     if(aRangeA.overlaps(aRangeB))
 299                     {
 300                         // no null length edges
 301                         if(!(aCurrA.equal(aNextA) || aCurrB.equal(aNextB)))
 302                         {
 303                             const B2DVector aVecA(aNextA - aCurrA);
 304                             const B2DVector aVecB(aNextB - aCurrB);
 305                             double fCutA(aVecA.cross(aVecB));
 306
 307                             if(!fTools::equalZero(fCutA))
 308                             {
 309                                 const double fZero(0.0);
 310                                 const double fOne(1.0);
 311                                 fCutA = (aVecB.getY() * (aCurrB.getX() - aCurrA.getX()) + aVecB.getX() * (aCurrA.getY() - aCurrB.getY())) / fCutA;
 312
 313                                 // use range [0.0 .. 1.0[, thus in the loop, all direct aCurrA cuts will be registered
 314                                 // as 0.0 cut. The 1.0 cut will be registered in the next loop step
 315                                 if(fTools::moreOrEqual(fCutA, fZero) && fTools::less(fCutA, fOne))
 316                                 {
 317                                     // it's a candidate, but also need to test parameter value of cut on line 2
 318                                     double fCutB;
 319
 320                                     // choose the more precise version
 321                                     if(fabs(aVecB.getX()) > fabs(aVecB.getY()))
 322                                     {
 323                                         fCutB = (aCurrA.getX() + (fCutA * aVecA.getX()) - aCurrB.getX()) / aVecB.getX();
 324                                     }
 325                                     else
 326                                     {
 327                                         fCutB = (aCurrA.getY() + (fCutA * aVecA.getY()) - aCurrB.getY()) / aVecB.getY();
 328                                     }
 329
 330                                     // use range [0.0 .. 1.0[, thus in the loop, all direct aCurrA cuts will be registered
 331                                     // as 0.0 cut. The 1.0 cut will be registered in the next loop step
 332                                     if(fTools::moreOrEqual(fCutB, fZero) && fTools::less(fCutB, fOne))
 333                                     {
 334                                         // cut is in both ranges. Add points for A and B
 335                                         // #i111715# use fTools::equal instead of fTools::equalZero for better accuracy
 336                                         if(fTools::equal(fCutA, fZero))
 337                                         {
 338                                             // ignore for start point in first edge; this is handled
 339                                             // by outer methods and would just produce a double point
 340                                             if(a)
 341                                             {
 342                                                 rTempPointsA.emplace_back(aCurrA, a, 0.0);
 343                                             }
 344                                         }
 345                                         else
 346                                         {
 347                                             const B2DPoint aCutPoint(interpolate(aCurrA, aNextA, fCutA));
 348                                             rTempPointsA.emplace_back(aCutPoint, a, fCutA);
 349                                         }
 350
 351                                         // #i111715# use fTools::equal instead of fTools::equalZero for better accuracy
 352                                         if(fTools::equal(fCutB, fZero))
 353                                         {
 354                                             // ignore for start point in first edge; this is handled
 355                                             // by outer methods and would just produce a double point
 356                                             if(b)
 357                                             {
 358                                                 rTempPointsB.emplace_back(aCurrB, b, 0.0);
 359                                             }
 360                                         }
 361                                         else
 362                                         {
 363                                             const B2DPoint aCutPoint(interpolate(aCurrB, aNextB, fCutB));
 364                                             rTempPointsB.emplace_back(aCutPoint, b, fCutB);
 365                                         }
 366                                     }
 367                                 }
 368                             }
 369                         }
 370                     }
 371
 372                     // prepare next step
 373                     aCurrB = aNextB;
 374                 }
 375
 376                 // prepare next step
 377                 aCurrA = aNextA;
 378             }
 379         }
 380
 381         void findEdgeCutsBezierAndEdge(
 382             const B2DCubicBezier& rCubicA,
 383             const B2DPoint& rCurrB, const B2DPoint& rNextB,
 384             sal_uInt32 nIndA, sal_uInt32 nIndB,
 385             temporaryPointVector& rTempPointsA, temporaryPointVector& rTempPointsB)
 386         {
 387             // find all cuts between given bezier segment and edge. Add an entry to the tempPoints
 388             // for each common point with the cut value describing the relative position on given
 389             // bezier segment and edge.
 390             B2DPolygon aTempPolygonA;
 391             B2DPolygon aTempPolygonEdge;
 392             temporaryPointVector aTempPointVectorA;
 393             temporaryPointVector aTempPointVectorEdge;
 394
 395             // create subdivided polygons and find cuts between them
 396             // Keep adaptiveSubdivideByCount due to needed quality
 397             aTempPolygonA.reserve(SUBDIVIDE_FOR_CUT_TEST_COUNT + 8);
 398             aTempPolygonA.append(rCubicA.getStartPoint());
 399             rCubicA.adaptiveSubdivideByCount(aTempPolygonA, SUBDIVIDE_FOR_CUT_TEST_COUNT);
 400             aTempPolygonEdge.append(rCurrB);
 401             aTempPolygonEdge.append(rNextB);
 402
 403             // #i76891# using findCuts recursively is not sufficient here
 404             findCutsAndTouchesAndCommonForBezier(aTempPolygonA, aTempPolygonEdge, aTempPointVectorA, aTempPointVectorEdge);
 405
 406             if(!aTempPointVectorA.empty())
 407             {
 408                 // adapt tempVector entries to segment
 409                 adaptAndTransferCutsWithBezierSegment(aTempPointVectorA, aTempPolygonA, nIndA, rTempPointsA);
 410             }
 411
 412             // append remapped tempVector entries for edge to tempPoints for edge
 413             for(const temporaryPoint & rTempPoint : aTempPointVectorEdge)
 414             {
 415                 rTempPointsB.emplace_back(rTempPoint.getPoint(), nIndB, rTempPoint.getCut());
 416             }
 417         }
 418
 419         void findEdgeCutsTwoBeziers(
 420             const B2DCubicBezier& rCubicA,
 421             const B2DCubicBezier& rCubicB,
 422             sal_uInt32 nIndA, sal_uInt32 nIndB,
 423             temporaryPointVector& rTempPointsA, temporaryPointVector& rTempPointsB)
 424         {
 425             // find all cuts between the two given bezier segments. Add an entry to the tempPoints
 426             // for each common point with the cut value describing the relative position on given
 427             // bezier segments.
 428             B2DPolygon aTempPolygonA;
 429             B2DPolygon aTempPolygonB;
 430             temporaryPointVector aTempPointVectorA;
 431             temporaryPointVector aTempPointVectorB;
 432
 433             // create subdivided polygons and find cuts between them
 434             // Keep adaptiveSubdivideByCount due to needed quality
 435             aTempPolygonA.reserve(SUBDIVIDE_FOR_CUT_TEST_COUNT + 8);
 436             aTempPolygonA.append(rCubicA.getStartPoint());
 437             rCubicA.adaptiveSubdivideByCount(aTempPolygonA, SUBDIVIDE_FOR_CUT_TEST_COUNT);
 438             aTempPolygonB.reserve(SUBDIVIDE_FOR_CUT_TEST_COUNT + 8);
 439             aTempPolygonB.append(rCubicB.getStartPoint());
 440             rCubicB.adaptiveSubdivideByCount(aTempPolygonB, SUBDIVIDE_FOR_CUT_TEST_COUNT);
 441
 442             // #i76891# using findCuts recursively is not sufficient here
 443             findCutsAndTouchesAndCommonForBezier(aTempPolygonA, aTempPolygonB, aTempPointVectorA, aTempPointVectorB);
 444
 445             if(!aTempPointVectorA.empty())
 446             {
 447                 // adapt tempVector entries to segment
 448                 adaptAndTransferCutsWithBezierSegment(aTempPointVectorA, aTempPolygonA, nIndA, rTempPointsA);
 449             }
 450
 451             if(!aTempPointVectorB.empty())
 452             {
 453                 // adapt tempVector entries to segment
 454                 adaptAndTransferCutsWithBezierSegment(aTempPointVectorB, aTempPolygonB, nIndB, rTempPointsB);
 455             }
 456         }
 457
 458         void findEdgeCutsOneBezier(
 459             const B2DCubicBezier& rCubicA,
 460             sal_uInt32 nInd, temporaryPointVector& rTempPoints)
 461         {
 462             // avoid expensive part of this method if possible
 463             // TODO: use hasAnyExtremum() method instead when it becomes available
 464             double fDummy;
 465             const bool bHasAnyExtremum = rCubicA.getMinimumExtremumPosition( fDummy );
 466             if( !bHasAnyExtremum )
 467                 return;
 468
 469             // find all self-intersections on the given bezier segment. Add an entry to the tempPoints
 470             // for each self intersection point with the cut value describing the relative position on given
 471             // bezier segment.
 472             B2DPolygon aTempPolygon;
 473             temporaryPointVector aTempPointVector;
 474
 475             // create subdivided polygon and find cuts on it
 476             // Keep adaptiveSubdivideByCount due to needed quality
 477             aTempPolygon.reserve(SUBDIVIDE_FOR_CUT_TEST_COUNT + 8);
 478             aTempPolygon.append(rCubicA.getStartPoint());
 479             rCubicA.adaptiveSubdivideByCount(aTempPolygon, SUBDIVIDE_FOR_CUT_TEST_COUNT);
 480             findCuts(aTempPolygon, aTempPointVector);
 481
 482             if(!aTempPointVector.empty())
 483             {
 484                 // adapt tempVector entries to segment
 485                 adaptAndTransferCutsWithBezierSegment(aTempPointVector, aTempPolygon, nInd, rTempPoints);
 486             }
 487         }
 488
 489         void findCuts(const B2DPolygon& rCandidate, temporaryPointVector& rTempPoints, size_t* pPointLimit)
 490         {
 491             // find out if there are edges with intersections (self-cuts). If yes, add
 492             // entries to rTempPoints accordingly
 493             const sal_uInt32 nPointCount(rCandidate.count());
 494
 495             if(!nPointCount)
 496                 return;
 497
 498             const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1);
 499
 500             if(!nEdgeCount)
 501                 return;
 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                         if (pPointLimit && rTempPoints.size() > *pPointLimit)
 591                             break;
 592
 593                         // prepare next step
 594                         aCurrB = aNextB;
 595                     }
 596
 597                     // prepare next step
 598                     aCurrA = aNextA;
 599                 }
 600             }
 601
 602             if (pPointLimit)
 603             {
 604                 if (rTempPoints.size() > *pPointLimit)
 605                     *pPointLimit = 0;
 606                 else
 607                     *pPointLimit -= rTempPoints.size();
 608             }
 609         }
 610
 611     } // end of anonymous namespace
 612 } // end of namespace basegfx
 613
 614 namespace basegfx
 615 {
 616     namespace
 617     {
 618
 619         void findTouchesOnEdge(
 620             const B2DPoint& rCurr, const B2DPoint& rNext, const B2DPolygon& rPointPolygon,
 621             sal_uInt32 nInd, temporaryPointVector& rTempPoints)
 622         {
 623             // find out if points from rPointPolygon are positioned on given edge. If Yes, add
 624             // points there to represent touches (which may be enter or leave nodes later).
 625             const sal_uInt32 nPointCount(rPointPolygon.count());
 626
 627             if(!nPointCount)
 628                 return;
 629
 630             const B2DRange aRange(rCurr, rNext);
 631             const B2DVector aEdgeVector(rNext - rCurr);
 632             bool bTestUsingX(fabs(aEdgeVector.getX()) > fabs(aEdgeVector.getY()));
 633
 634             for(sal_uInt32 a(0); a < nPointCount; a++)
 635             {
 636                 const B2DPoint aTestPoint(rPointPolygon.getB2DPoint(a));
 637
 638                 if(aRange.isInside(aTestPoint))
 639                 {
 640                     if(!aTestPoint.equal(rCurr) && !aTestPoint.equal(rNext))
 641                     {
 642                         const B2DVector aTestVector(aTestPoint - rCurr);
 643
 644                         if(areParallel(aEdgeVector, aTestVector))
 645                         {
 646                             const double fCut(bTestUsingX
 647                                 ? aTestVector.getX() / aEdgeVector.getX()
 648                                 : aTestVector.getY() / aEdgeVector.getY());
 649                             const double fZero(0.0);
 650                             const double fOne(1.0);
 651
 652                             if(fTools::more(fCut, fZero) && fTools::less(fCut, fOne))
 653                             {
 654                                 rTempPoints.emplace_back(aTestPoint, nInd, fCut);
 655                             }
 656                         }
 657                     }
 658                 }
 659             }
 660         }
 661
 662         void findTouchesOnCurve(
 663             const B2DCubicBezier& rCubicA, const B2DPolygon& rPointPolygon,
 664             sal_uInt32 nInd, temporaryPointVector& rTempPoints)
 665         {
 666             // find all points from rPointPolygon which touch the given bezier segment. Add an entry
 667             // for each touch to the given pointVector. The cut for that entry is the relative position on
 668             // the given bezier segment.
 669             B2DPolygon aTempPolygon;
 670             temporaryPointVector aTempPointVector;
 671
 672             // create subdivided polygon and find cuts on it
 673             // Keep adaptiveSubdivideByCount due to needed quality
 674             aTempPolygon.reserve(SUBDIVIDE_FOR_CUT_TEST_COUNT + 8);
 675             aTempPolygon.append(rCubicA.getStartPoint());
 676             rCubicA.adaptiveSubdivideByCount(aTempPolygon, SUBDIVIDE_FOR_CUT_TEST_COUNT);
 677             findTouches(aTempPolygon, rPointPolygon, aTempPointVector);
 678
 679             if(!aTempPointVector.empty())
 680             {
 681                 // adapt tempVector entries to segment
 682                 adaptAndTransferCutsWithBezierSegment(aTempPointVector, aTempPolygon, nInd, rTempPoints);
 683             }
 684         }
 685
 686         void findTouches(const B2DPolygon& rEdgePolygon, const B2DPolygon& rPointPolygon, temporaryPointVector& rTempPoints)
 687         {
 688             // find out if points from rPointPolygon touch edges from rEdgePolygon. If yes,
 689             // add entries to rTempPoints
 690             const sal_uInt32 nPointCount(rPointPolygon.count());
 691             const sal_uInt32 nEdgePointCount(rEdgePolygon.count());
 692
 693             if(!(nPointCount && nEdgePointCount))
 694                 return;
 695
 696             const sal_uInt32 nEdgeCount(rEdgePolygon.isClosed() ? nEdgePointCount : nEdgePointCount - 1);
 697             B2DPoint aCurr(rEdgePolygon.getB2DPoint(0));
 698
 699             for(sal_uInt32 a(0); a < nEdgeCount; a++)
 700             {
 701                 const sal_uInt32 nNextIndex((a + 1) % nEdgePointCount);
 702                 const B2DPoint aNext(rEdgePolygon.getB2DPoint(nNextIndex));
 703
 704                 if(!aCurr.equal(aNext))
 705                 {
 706                     bool bHandleAsSimpleEdge(true);
 707
 708                     if(rEdgePolygon.areControlPointsUsed())
 709                     {
 710                         const B2DPoint aNextControlPoint(rEdgePolygon.getNextControlPoint(a));
 711                         const B2DPoint aPrevControlPoint(rEdgePolygon.getPrevControlPoint(nNextIndex));
 712                         const bool bEdgeIsCurve(!aNextControlPoint.equal(aCurr) || !aPrevControlPoint.equal(aNext));
 713
 714                         if(bEdgeIsCurve)
 715                         {
 716                             bHandleAsSimpleEdge = false;
 717                             const B2DCubicBezier aCubicA(aCurr, aNextControlPoint, aPrevControlPoint, aNext);
 718                             findTouchesOnCurve(aCubicA, rPointPolygon, a, rTempPoints);
 719                         }
 720                     }
 721
 722                     if(bHandleAsSimpleEdge)
 723                     {
 724                         findTouchesOnEdge(aCurr, aNext, rPointPolygon, a, rTempPoints);
 725                     }
 726                 }
 727
 728                 // next step
 729                 aCurr = aNext;
 730             }
 731         }
 732
 733     } // end of anonymous namespace
 734 } // end of namespace basegfx
 735
 736 namespace basegfx
 737 {
 738     namespace
 739     {
 740
 741         void findCuts(const B2DPolygon& rCandidateA, const B2DPolygon& rCandidateB, temporaryPointVector& rTempPointsA, temporaryPointVector& rTempPointsB)
 742         {
 743             // find out if edges from both polygons cut. If so, add entries to rTempPoints which
 744             // should be added to the polygons accordingly
 745             const sal_uInt32 nPointCountA(rCandidateA.count());
 746             const sal_uInt32 nPointCountB(rCandidateB.count());
 747
 748             if(!(nPointCountA && nPointCountB))
 749                 return;
 750
 751             const sal_uInt32 nEdgeCountA(rCandidateA.isClosed() ? nPointCountA : nPointCountA - 1);
 752             const sal_uInt32 nEdgeCountB(rCandidateB.isClosed() ? nPointCountB : nPointCountB - 1);
 753
 754             if(!(nEdgeCountA && nEdgeCountB))
 755                 return;
 756
 757             const bool bCurvesInvolved(rCandidateA.areControlPointsUsed() || rCandidateB.areControlPointsUsed());
 758
 759             if(bCurvesInvolved)
 760             {
 761                 B2DCubicBezier aCubicA;
 762                 B2DCubicBezier aCubicB;
 763
 764                 for(sal_uInt32 a(0); a < nEdgeCountA; a++)
 765                 {
 766                     rCandidateA.getBezierSegment(a, aCubicA);
 767                     aCubicA.testAndSolveTrivialBezier();
 768                     const bool bEdgeAIsCurve(aCubicA.isBezier());
 769                     const B2DRange aRangeA(aCubicA.getRange());
 770
 771                     for(sal_uInt32 b(0); b < nEdgeCountB; b++)
 772                     {
 773                         rCandidateB.getBezierSegment(b, aCubicB);
 774                         aCubicB.testAndSolveTrivialBezier();
 775                         const B2DRange aRangeB(aCubicB.getRange());
 776
 777                         // consecutive segments touch of course
 778                         bool bOverlap = false;
 779                         if( b > a+1)
 780                             bOverlap = aRangeA.overlaps(aRangeB);
 781                         else
 782                             bOverlap = aRangeA.overlapsMore(aRangeB);
 783                         if( bOverlap)
 784                         {
 785                             const bool bEdgeBIsCurve(aCubicB.isBezier());
 786                             if(bEdgeAIsCurve && bEdgeBIsCurve)
 787                             {
 788                                 // test for bezier-bezier cuts
 789                                 findEdgeCutsTwoBeziers(aCubicA, aCubicB, a, b, rTempPointsA, rTempPointsB);
 790                             }
 791                             else if(bEdgeAIsCurve)
 792                             {
 793                                 // test for bezier-edge cuts
 794                                 findEdgeCutsBezierAndEdge(aCubicA, aCubicB.getStartPoint(), aCubicB.getEndPoint(), a, b, rTempPointsA, rTempPointsB);
 795                             }
 796                             else if(bEdgeBIsCurve)
 797                             {
 798                                 // test for bezier-edge cuts
 799                                 findEdgeCutsBezierAndEdge(aCubicB, aCubicA.getStartPoint(), aCubicA.getEndPoint(), b, a, rTempPointsB, rTempPointsA);
 800                             }
 801                             else
 802                             {
 803                                 // test for simple edge-edge cuts
 804                                 findEdgeCutsTwoEdges(aCubicA.getStartPoint(), aCubicA.getEndPoint(), aCubicB.getStartPoint(), aCubicB.getEndPoint(),
 805                                     a, b, rTempPointsA, rTempPointsB);
 806                             }
 807                         }
 808                     }
 809                 }
 810             }
 811             else
 812             {
 813                 B2DPoint aCurrA(rCandidateA.getB2DPoint(0));
 814
 815                 for(sal_uInt32 a(0); a < nEdgeCountA; a++)
 816                 {
 817                     const B2DPoint aNextA(rCandidateA.getB2DPoint(a + 1 == nPointCountA ? 0 : a + 1));
 818                     const B2DRange aRangeA(aCurrA, aNextA);
 819                     B2DPoint aCurrB(rCandidateB.getB2DPoint(0));
 820
 821                     for(sal_uInt32 b(0); b < nEdgeCountB; b++)
 822                     {
 823                         const B2DPoint aNextB(rCandidateB.getB2DPoint(b + 1 == nPointCountB ? 0 : b + 1));
 824                         const B2DRange aRangeB(aCurrB, aNextB);
 825
 826                         // consecutive segments touch of course
 827                         bool bOverlap = false;
 828                         if( b > a+1)
 829                             bOverlap = aRangeA.overlaps(aRangeB);
 830                         else
 831                             bOverlap = aRangeA.overlapsMore(aRangeB);
 832                         if( bOverlap)
 833                         {
 834                             // test for simple edge-edge cuts
 835                             findEdgeCutsTwoEdges(aCurrA, aNextA, aCurrB, aNextB, a, b, rTempPointsA, rTempPointsB);
 836                         }
 837
 838                         // prepare next step
 839                         aCurrB = aNextB;
 840                     }
 841
 842                     // prepare next step
 843                     aCurrA = aNextA;
 844                 }
 845             }
 846         }
 847
 848     } // end of anonymous namespace
 849 } // end of namespace basegfx
 850
 851 namespace basegfx::utils
 852 {
 853
 854         B2DPolygon addPointsAtCutsAndTouches(const B2DPolygon& rCandidate, size_t* pPointLimit)
 855         {
 856             if(rCandidate.count())
 857             {
 858                 temporaryPointVector aTempPoints;
 859
 860                 findTouches(rCandidate, rCandidate, aTempPoints);
 861                 findCuts(rCandidate, aTempPoints, pPointLimit);
 862                 if (pPointLimit && !*pPointLimit)
 863                 {
 864                     SAL_WARN("basegfx", "addPointsAtCutsAndTouches hit point limit");
 865                     return rCandidate;
 866                 }
 867
 868                 return mergeTemporaryPointsAndPolygon(rCandidate, aTempPoints);
 869             }
 870             else
 871             {
 872                 return rCandidate;
 873             }
 874         }
 875
 876         B2DPolyPolygon addPointsAtCutsAndTouches(const B2DPolyPolygon& rCandidate, size_t* pPointLimit)
 877         {
 878             const sal_uInt32 nCount(rCandidate.count());
 879
 880             if(nCount)
 881             {
 882                 B2DPolyPolygon aRetval;
 883
 884                 if(nCount == 1)
 885                 {
 886                     // remove self intersections
 887                     aRetval.append(addPointsAtCutsAndTouches(rCandidate.getB2DPolygon(0), pPointLimit));
 888                 }
 889                 else
 890                 {
 891                     // first solve self cuts and self touches for all contained single polygons
 892                     std::unique_ptr<temporaryPolygonData[]> pTempData(new temporaryPolygonData[nCount]);
 893                     sal_uInt32 a, b;
 894
 895                     for(a = 0; a < nCount; a++)
 896                     {
 897                         // use polygons with solved self intersections
 898                         pTempData[a].setPolygon(addPointsAtCutsAndTouches(rCandidate.getB2DPolygon(a), pPointLimit));
 899                     }
 900
 901                     if (pPointLimit && !*pPointLimit)
 902                     {
 903                         SAL_WARN("basegfx", "addPointsAtCutsAndTouches hit point limit");
 904                         return rCandidate;
 905                     }
 906
 907                     // now cuts and touches between the polygons
 908                     for(a = 0; a < nCount; a++)
 909                     {
 910                         for(b = 0; b < nCount; b++)
 911                         {
 912                             if(a != b)
 913                             {
 914                                 // look for touches, compare each edge polygon to all other points
 915                                 if(pTempData[a].getRange().overlaps(pTempData[b].getRange()))
 916                                 {
 917                                     findTouches(pTempData[a].getPolygon(), pTempData[b].getPolygon(), pTempData[a].getTemporaryPointVector());
 918                                 }
 919                             }
 920
 921                             if(a < b)
 922                             {
 923                                 // look for cuts, compare each edge polygon to following ones
 924                                 if(pTempData[a].getRange().overlaps(pTempData[b].getRange()))
 925                                 {
 926                                     findCuts(pTempData[a].getPolygon(), pTempData[b].getPolygon(), pTempData[a].getTemporaryPointVector(), pTempData[b].getTemporaryPointVector());
 927                                 }
 928                             }
 929                         }
 930                     }
 931
 932                     // consolidate the result
 933                     for(a = 0; a < nCount; a++)
 934                     {
 935                         aRetval.append(mergeTemporaryPointsAndPolygon(pTempData[a].getPolygon(), pTempData[a].getTemporaryPointVector()));
 936                     }
 937                 }
 938
 939                 return aRetval;
 940             }
 941             else
 942             {
 943                 return rCandidate;
 944             }
 945         }
 946
 947         B2DPolygon addPointsAtCuts(const B2DPolygon& rCandidate, const B2DPoint& rStart, const B2DPoint& rEnd)
 948         {
 949             const sal_uInt32 nCount(rCandidate.count());
 950
 951             if(nCount && !rStart.equal(rEnd))
 952             {
 953                 const B2DRange aPolygonRange(rCandidate.getB2DRange());
 954                 const B2DRange aEdgeRange(rStart, rEnd);
 955
 956                 if(aPolygonRange.overlaps(aEdgeRange))
 957                 {
 958                     const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nCount : nCount - 1);
 959                     temporaryPointVector aTempPoints;
 960                     temporaryPointVector aUnusedTempPoints;
 961                     B2DCubicBezier aCubic;
 962
 963                     for(sal_uInt32 a(0); a < nEdgeCount; a++)
 964                     {
 965                         rCandidate.getBezierSegment(a, aCubic);
 966                         B2DRange aCubicRange(aCubic.getStartPoint(), aCubic.getEndPoint());
 967
 968                         if(aCubic.isBezier())
 969                         {
 970                             aCubicRange.expand(aCubic.getControlPointA());
 971                             aCubicRange.expand(aCubic.getControlPointB());
 972
 973                             if(aCubicRange.overlaps(aEdgeRange))
 974                             {
 975                                 findEdgeCutsBezierAndEdge(aCubic, rStart, rEnd, a, 0, aTempPoints, aUnusedTempPoints);
 976                             }
 977                         }
 978                         else
 979                         {
 980                             if(aCubicRange.overlaps(aEdgeRange))
 981                             {
 982                                 findEdgeCutsTwoEdges(aCubic.getStartPoint(), aCubic.getEndPoint(), rStart, rEnd, a, 0, aTempPoints, aUnusedTempPoints);
 983                             }
 984                         }
 985                     }
 986
 987                     return mergeTemporaryPointsAndPolygon(rCandidate, aTempPoints);
 988                 }
 989             }
 990
 991             return rCandidate;
 992         }
 993
 994         B2DPolygon addPointsAtCuts(const B2DPolygon& rCandidate, const B2DPolyPolygon& rPolyMask)
 995         {
 996             const sal_uInt32 nCountA(rCandidate.count());
 997             const sal_uInt32 nCountM(rPolyMask.count());
 998
 999             if(nCountA && nCountM)
1000             {
1001                 const B2DRange aRangeA(rCandidate.getB2DRange());
1002                 const B2DRange aRangeM(rPolyMask.getB2DRange());
1003
1004                 if(aRangeA.overlaps(aRangeM))
1005                 {
1006                     const sal_uInt32 nEdgeCountA(rCandidate.isClosed() ? nCountA : nCountA - 1);
1007                     temporaryPointVector aTempPointsA;
1008                     temporaryPointVector aUnusedTempPointsB;
1009
1010                     for(sal_uInt32 m(0); m < nCountM; m++)
1011                     {
1012                         const B2DPolygon& aMask(rPolyMask.getB2DPolygon(m));
1013                         const sal_uInt32 nCountB(aMask.count());
1014
1015                         if(nCountB)
1016                         {
1017                             B2DCubicBezier aCubicA;
1018                             B2DCubicBezier aCubicB;
1019
1020                             for(sal_uInt32 a(0); a < nEdgeCountA; a++)
1021                             {
1022                                 rCandidate.getBezierSegment(a, aCubicA);
1023                                 const bool bCubicAIsCurve(aCubicA.isBezier());
1024                                 B2DRange aCubicRangeA(aCubicA.getStartPoint(), aCubicA.getEndPoint());
1025
1026                                 if(bCubicAIsCurve)
1027                                 {
1028                                     aCubicRangeA.expand(aCubicA.getControlPointA());
1029                                     aCubicRangeA.expand(aCubicA.getControlPointB());
1030                                 }
1031
1032                                 for(sal_uInt32 b(0); b < nCountB; b++)
1033                                 {
1034                                     aMask.getBezierSegment(b, aCubicB);
1035                                     const bool bCubicBIsCurve(aCubicB.isBezier());
1036                                     B2DRange aCubicRangeB(aCubicB.getStartPoint(), aCubicB.getEndPoint());
1037
1038                                     if(bCubicBIsCurve)
1039                                     {
1040                                         aCubicRangeB.expand(aCubicB.getControlPointA());
1041                                         aCubicRangeB.expand(aCubicB.getControlPointB());
1042                                     }
1043
1044                                     if(aCubicRangeA.overlaps(aCubicRangeB))
1045                                     {
1046                                         if(bCubicAIsCurve && bCubicBIsCurve)
1047                                         {
1048                                             findEdgeCutsTwoBeziers(aCubicA, aCubicB, a, b, aTempPointsA, aUnusedTempPointsB);
1049                                         }
1050                                         else if(bCubicAIsCurve)
1051                                         {
1052                                             findEdgeCutsBezierAndEdge(aCubicA, aCubicB.getStartPoint(), aCubicB.getEndPoint(), a, b, aTempPointsA, aUnusedTempPointsB);
1053                                         }
1054                                         else if(bCubicBIsCurve)
1055                                         {
1056                                             findEdgeCutsBezierAndEdge(aCubicB, aCubicA.getStartPoint(), aCubicA.getEndPoint(), b, a, aUnusedTempPointsB, aTempPointsA);
1057                                         }
1058                                         else
1059                                         {
1060                                             findEdgeCutsTwoEdges(aCubicA.getStartPoint(), aCubicA.getEndPoint(), aCubicB.getStartPoint(), aCubicB.getEndPoint(), a, b, aTempPointsA, aUnusedTempPointsB);
1061                                         }
1062                                     }
1063                                 }
1064                             }
1065                         }
1066                     }
1067
1068                     return mergeTemporaryPointsAndPolygon(rCandidate, aTempPointsA);
1069                 }
1070             }
1071
1072             return rCandidate;
1073         }
1074
1075 } // end of namespace
1076
1077 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */