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

Generated by: LCOV version 1.11