LCOV - code coverage report
Current view: top level - basegfx/source/polygon - b2dpolygoncutandtouch.cxx (source / functions) Hit Total Coverage
Test: commit e02a6cb2c3e2b23b203b422e4e0680877f232636 Lines: 0 436 0.0 %
Date: 2014-04-14 Functions: 0 31 0.0 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.10