LCOV - code coverage report
Current view: top level - basegfx/source/polygon - b2dpolypolygoncutter.cxx (source / functions) Hit Total Coverage
Test: commit c8344322a7af75b84dd3ca8f78b05543a976dfd5 Lines: 397 468 84.8 %
Date: 2015-06-13 12:38:46 Functions: 29 30 96.7 %
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 <osl/diagnose.h>
      21             : #include <basegfx/numeric/ftools.hxx>
      22             : #include <basegfx/polygon/b2dpolypolygoncutter.hxx>
      23             : #include <basegfx/point/b2dpoint.hxx>
      24             : #include <basegfx/vector/b2dvector.hxx>
      25             : #include <basegfx/polygon/b2dpolygon.hxx>
      26             : #include <basegfx/polygon/b2dpolygontools.hxx>
      27             : #include <basegfx/polygon/b2dpolygoncutandtouch.hxx>
      28             : #include <basegfx/range/b2drange.hxx>
      29             : #include <basegfx/polygon/b2dpolypolygontools.hxx>
      30             : #include <basegfx/curve/b2dcubicbezier.hxx>
      31             : #include <vector>
      32             : #include <algorithm>
      33             : 
      34             : namespace basegfx
      35             : {
      36             :     namespace
      37             :     {
      38             : 
      39        2239 :         struct StripHelper
      40             :         {
      41             :             B2DRange                                maRange;
      42             :             sal_Int32                               mnDepth;
      43             :             B2VectorOrientation                     meOrinetation;
      44             :         };
      45             : 
      46       84054 :         struct PN
      47             :         {
      48             :         public:
      49             :             B2DPoint                maPoint;
      50             :             sal_uInt32              mnI;
      51             :             sal_uInt32              mnIP;
      52             :             sal_uInt32              mnIN;
      53             :         };
      54             : 
      55       67748 :         struct VN
      56             :         {
      57             :         public:
      58             :             B2DVector               maPrev;
      59             :             B2DVector               maNext;
      60             : 
      61             :             // to have the correct curve segments in the crossover checks,
      62             :             // it is necessary to keep the original next vectors, too. Else,
      63             :             // it may happen to use a already switched next vector which
      64             :             // would interpolate the wrong comparison point
      65             :             B2DVector               maOriginalNext;
      66             :         };
      67             : 
      68             :         struct SN
      69             :         {
      70             :         public:
      71             :             PN*                     mpPN;
      72             : 
      73      187535 :             bool operator<(const SN& rComp) const
      74             :             {
      75      187535 :                 if(fTools::equal(mpPN->maPoint.getX(), rComp.mpPN->maPoint.getX()))
      76             :                 {
      77       19894 :                     if(fTools::equal(mpPN->maPoint.getY(), rComp.mpPN->maPoint.getY()))
      78             :                     {
      79         924 :                         return (mpPN->mnI < rComp.mpPN->mnI);
      80             :                     }
      81             :                     else
      82             :                     {
      83       18970 :                         return fTools::less(mpPN->maPoint.getY(), rComp.mpPN->maPoint.getY());
      84             :                     }
      85             :                 }
      86             :                 else
      87             :                 {
      88      167641 :                     return fTools::less(mpPN->maPoint.getX(), rComp.mpPN->maPoint.getX());
      89             :                 }
      90             :             }
      91             :         };
      92             : 
      93             :         typedef ::std::vector< PN > PNV;
      94             :         typedef ::std::vector< VN > VNV;
      95             :         typedef ::std::vector< SN > SNV;
      96             :         typedef ::std::pair< basegfx::B2DPoint /*orig*/, basegfx::B2DPoint /*repl*/ > CorrectionPair;
      97             :         typedef ::std::vector< CorrectionPair > CorrectionTable;
      98             : 
      99        2886 :         class solver
     100             :         {
     101             :         private:
     102             :             const B2DPolyPolygon    maOriginal;
     103             :             PNV                     maPNV;
     104             :             VNV                     maVNV;
     105             :             SNV                     maSNV;
     106             :             CorrectionTable         maCorrectionTable;
     107             : 
     108             :             bool                    mbIsCurve : 1;
     109             :             bool                    mbChanged : 1;
     110             : 
     111        4441 :             void impAddPolygon(const sal_uInt32 aPos, const B2DPolygon& rGeometry)
     112             :             {
     113        4441 :                 const sal_uInt32 nCount(rGeometry.count());
     114        4441 :                 PN aNewPN;
     115        8882 :                 VN aNewVN;
     116             :                 SN aNewSN;
     117             : 
     118       42027 :                 for(sal_uInt32 a(0); a < nCount; a++)
     119             :                 {
     120       37586 :                     const B2DPoint aPoint(rGeometry.getB2DPoint(a));
     121       37586 :                     aNewPN.maPoint = aPoint;
     122       37586 :                     aNewPN.mnI = aPos + a;
     123       37586 :                     aNewPN.mnIP = aPos + ((a != 0) ? a - 1 : nCount - 1);
     124       37586 :                     aNewPN.mnIN = aPos + ((a + 1 == nCount) ? 0 : a + 1);
     125       37586 :                     maPNV.push_back(aNewPN);
     126             : 
     127       37586 :                     if(mbIsCurve)
     128             :                     {
     129       29433 :                         aNewVN.maPrev = rGeometry.getPrevControlPoint(a) - aPoint;
     130       29433 :                         aNewVN.maNext = rGeometry.getNextControlPoint(a) - aPoint;
     131       29433 :                         aNewVN.maOriginalNext = aNewVN.maNext;
     132       29433 :                         maVNV.push_back(aNewVN);
     133             :                     }
     134             : 
     135       37586 :                     aNewSN.mpPN = &maPNV[maPNV.size() - 1];
     136       37586 :                     maSNV.push_back(aNewSN);
     137       42027 :                 }
     138        4441 :             }
     139             : 
     140         706 :             static bool impLeftOfEdges(const B2DVector& rVecA, const B2DVector& rVecB, const B2DVector& rTest)
     141             :             {
     142             :                 // tests if rTest is left of both directed line segments along the line -rVecA, rVecB. Test is
     143             :                 // with border.
     144         706 :                 if(rVecA.cross(rVecB) > 0.0)
     145             :                 {
     146             :                     // b is left turn seen from a, test if Test is left of both and so inside (left is seeen as inside)
     147         264 :                     const bool bBoolA(fTools::moreOrEqual(rVecA.cross(rTest), 0.0));
     148         264 :                     const bool bBoolB(fTools::lessOrEqual(rVecB.cross(rTest), 0.0));
     149             : 
     150         264 :                     return (bBoolA && bBoolB);
     151             :                 }
     152             :                 else
     153             :                 {
     154             :                     // b is right turn seen from a, test if Test is right of both and so outside (left is seeen as inside)
     155         442 :                     const bool bBoolA(fTools::lessOrEqual(rVecA.cross(rTest), 0.0));
     156         442 :                     const bool bBoolB(fTools::moreOrEqual(rVecB.cross(rTest), 0.0));
     157             : 
     158         442 :                     return (!(bBoolA && bBoolB));
     159             :                 }
     160             :             }
     161             : 
     162         625 :             void impSwitchNext(PN& rPNa, PN& rPNb)
     163             :             {
     164         625 :                 ::std::swap(rPNa.mnIN, rPNb.mnIN);
     165             : 
     166         625 :                 if(mbIsCurve)
     167             :                 {
     168         411 :                     VN& rVNa = maVNV[rPNa.mnI];
     169         411 :                     VN& rVNb = maVNV[rPNb.mnI];
     170             : 
     171         411 :                     ::std::swap(rVNa.maNext, rVNb.maNext);
     172             :                 }
     173             : 
     174         625 :                 if(!mbChanged)
     175             :                 {
     176         335 :                     mbChanged = true;
     177             :                 }
     178         625 :             }
     179             : 
     180        2014 :             B2DCubicBezier createSegment(const PN& rPN, bool bPrev) const
     181             :             {
     182        2014 :                 const B2DPoint& rStart(rPN.maPoint);
     183        2014 :                 const B2DPoint& rEnd(maPNV[bPrev ? rPN.mnIP : rPN.mnIN].maPoint);
     184        2014 :                 const B2DVector& rCPA(bPrev ? maVNV[rPN.mnI].maPrev : maVNV[rPN.mnI].maNext);
     185             :                 // Use maOriginalNext, not maNext to create the original (yet unchanged)
     186             :                 // curve segment. Otherwise, this segment would NOT ne correct.
     187        2014 :                 const B2DVector& rCPB(bPrev ? maVNV[maPNV[rPN.mnIP].mnI].maOriginalNext : maVNV[maPNV[rPN.mnIN].mnI].maPrev);
     188             : 
     189        2014 :                 return B2DCubicBezier(rStart, rStart + rCPA, rEnd + rCPB, rEnd);
     190             :             }
     191             : 
     192         766 :             void impHandleCommon(PN& rPNa, PN& rPNb)
     193             :             {
     194         766 :                 if(mbIsCurve)
     195             :                 {
     196         504 :                     const B2DCubicBezier aNextA(createSegment(rPNa, false));
     197         969 :                     const B2DCubicBezier aPrevA(createSegment(rPNa, true));
     198             : 
     199         504 :                     if(aNextA.equal(aPrevA))
     200             :                     {
     201             :                         // deadend on A (identical edge)
     202           6 :                         return;
     203             :                     }
     204             : 
     205         963 :                     const B2DCubicBezier aNextB(createSegment(rPNb, false));
     206         963 :                     const B2DCubicBezier aPrevB(createSegment(rPNb, true));
     207             : 
     208         498 :                     if(aNextB.equal(aPrevB))
     209             :                     {
     210             :                         // deadend on B (identical edge)
     211           2 :                         return;
     212             :                     }
     213             : 
     214         496 :                     if(aPrevA.equal(aPrevB))
     215             :                     {
     216             :                         // common edge in same direction
     217           6 :                         return;
     218             :                     }
     219         490 :                     else if(aPrevA.equal(aNextB))
     220             :                     {
     221             :                         // common edge in opposite direction
     222         317 :                         if(aNextA.equal(aPrevB))
     223             :                         {
     224             :                             // common edge in opposite direction continues
     225          24 :                             return;
     226             :                         }
     227             :                         else
     228             :                         {
     229             :                             // common edge in opposite direction leave
     230         293 :                             impSwitchNext(rPNa, rPNb);
     231             :                         }
     232             :                     }
     233         173 :                     else if(aNextA.equal(aNextB))
     234             :                     {
     235             :                         // common edge in same direction enter
     236             :                         // search leave edge
     237           1 :                         PN* pPNa2 = &maPNV[rPNa.mnIN];
     238           1 :                         PN* pPNb2 = &maPNV[rPNb.mnIN];
     239           1 :                         bool bOnEdge(true);
     240             : 
     241           5 :                         do
     242             :                         {
     243           5 :                             const B2DCubicBezier aNextA2(createSegment(*pPNa2, false));
     244          10 :                             const B2DCubicBezier aNextB2(createSegment(*pPNb2, false));
     245             : 
     246           5 :                             if(aNextA2.equal(aNextB2))
     247             :                             {
     248           5 :                                 pPNa2 = &maPNV[pPNa2->mnIN];
     249           5 :                                 pPNb2 = &maPNV[pPNb2->mnIN];
     250             :                             }
     251             :                             else
     252             :                             {
     253           0 :                                 bOnEdge = false;
     254           5 :                             }
     255             :                         }
     256           5 :                         while(bOnEdge && pPNa2 != &rPNa && pPNb2 != &rPNb);
     257             : 
     258           1 :                         if(bOnEdge)
     259             :                         {
     260             :                             // loop over two identical polygon paths
     261           1 :                             return;
     262             :                         }
     263             :                         else
     264             :                         {
     265             :                             // enter at rPNa, rPNb; leave at pPNa2, pPNb2. No common edges
     266             :                             // at enter/leave. Check for crossover.
     267           0 :                             const B2DVector aPrevCA(aPrevA.interpolatePoint(0.5) - aPrevA.getStartPoint());
     268           0 :                             const B2DVector aNextCA(aNextA.interpolatePoint(0.5) - aNextA.getStartPoint());
     269           0 :                             const B2DVector aPrevCB(aPrevB.interpolatePoint(0.5) - aPrevB.getStartPoint());
     270           0 :                             const bool bEnter(impLeftOfEdges(aPrevCA, aNextCA, aPrevCB));
     271             : 
     272           0 :                             const B2DCubicBezier aNextA2(createSegment(*pPNa2, false));
     273           0 :                             const B2DCubicBezier aPrevA2(createSegment(*pPNa2, true));
     274           0 :                             const B2DCubicBezier aNextB2(createSegment(*pPNb2, false));
     275           0 :                             const B2DVector aPrevCA2(aPrevA2.interpolatePoint(0.5) - aPrevA2.getStartPoint());
     276           0 :                             const B2DVector aNextCA2(aNextA2.interpolatePoint(0.5) - aNextA2.getStartPoint());
     277           0 :                             const B2DVector aNextCB2(aNextB2.interpolatePoint(0.5) - aNextB2.getStartPoint());
     278           0 :                             const bool bLeave(impLeftOfEdges(aPrevCA2, aNextCA2, aNextCB2));
     279             : 
     280           0 :                             if(bEnter != bLeave)
     281             :                             {
     282             :                                 // crossover
     283           0 :                                 impSwitchNext(rPNa, rPNb);
     284           0 :                             }
     285             :                         }
     286             :                     }
     287         172 :                     else if(aNextA.equal(aPrevB))
     288             :                     {
     289             :                         // common edge in opposite direction enter
     290          12 :                         impSwitchNext(rPNa, rPNb);
     291             :                     }
     292             :                     else
     293             :                     {
     294             :                         // no common edges, check for crossover
     295         160 :                         const B2DVector aPrevCA(aPrevA.interpolatePoint(0.5) - aPrevA.getStartPoint());
     296         320 :                         const B2DVector aNextCA(aNextA.interpolatePoint(0.5) - aNextA.getStartPoint());
     297         320 :                         const B2DVector aPrevCB(aPrevB.interpolatePoint(0.5) - aPrevB.getStartPoint());
     298         320 :                         const B2DVector aNextCB(aNextB.interpolatePoint(0.5) - aNextB.getStartPoint());
     299             : 
     300         160 :                         const bool bEnter(impLeftOfEdges(aPrevCA, aNextCA, aPrevCB));
     301         160 :                         const bool bLeave(impLeftOfEdges(aPrevCA, aNextCA, aNextCB));
     302             : 
     303         160 :                         if(bEnter != bLeave)
     304             :                         {
     305             :                             // crossover
     306         106 :                             impSwitchNext(rPNa, rPNb);
     307         160 :                         }
     308         465 :                     }
     309             :                 }
     310             :                 else
     311             :                 {
     312         262 :                     const B2DPoint& rNextA(maPNV[rPNa.mnIN].maPoint);
     313         262 :                     const B2DPoint& rPrevA(maPNV[rPNa.mnIP].maPoint);
     314             : 
     315         262 :                     if(rNextA.equal(rPrevA))
     316             :                     {
     317             :                         // deadend on A
     318           0 :                         return;
     319             :                     }
     320             : 
     321         262 :                     const B2DPoint& rNextB(maPNV[rPNb.mnIN].maPoint);
     322         262 :                     const B2DPoint& rPrevB(maPNV[rPNb.mnIP].maPoint);
     323             : 
     324         262 :                     if(rNextB.equal(rPrevB))
     325             :                     {
     326             :                         // deadend on B
     327           0 :                         return;
     328             :                     }
     329             : 
     330         262 :                     if(rPrevA.equal(rPrevB))
     331             :                     {
     332             :                         // common edge in same direction
     333          37 :                         return;
     334             :                     }
     335         225 :                     else if(rPrevA.equal(rNextB))
     336             :                     {
     337             :                         // common edge in opposite direction
     338          29 :                         if(rNextA.equal(rPrevB))
     339             :                         {
     340             :                             // common edge in opposite direction continues
     341           5 :                             return;
     342             :                         }
     343             :                         else
     344             :                         {
     345             :                             // common edge in opposite direction leave
     346          24 :                             impSwitchNext(rPNa, rPNb);
     347             :                         }
     348             :                     }
     349         196 :                     else if(rNextA.equal(rNextB))
     350             :                     {
     351             :                         // common edge in same direction enter
     352             :                         // search leave edge
     353          13 :                         PN* pPNa2 = &maPNV[rPNa.mnIN];
     354          13 :                         PN* pPNb2 = &maPNV[rPNb.mnIN];
     355          13 :                         bool bOnEdge(true);
     356             : 
     357          20 :                         do
     358             :                         {
     359          20 :                             const B2DPoint& rNextA2(maPNV[pPNa2->mnIN].maPoint);
     360          20 :                             const B2DPoint& rNextB2(maPNV[pPNb2->mnIN].maPoint);
     361             : 
     362          20 :                             if(rNextA2.equal(rNextB2))
     363             :                             {
     364           8 :                                 pPNa2 = &maPNV[pPNa2->mnIN];
     365           8 :                                 pPNb2 = &maPNV[pPNb2->mnIN];
     366             :                             }
     367             :                             else
     368             :                             {
     369          12 :                                 bOnEdge = false;
     370             :                             }
     371             :                         }
     372           8 :                         while(bOnEdge && pPNa2 != &rPNa && pPNb2 != &rPNb);
     373             : 
     374          13 :                         if(bOnEdge)
     375             :                         {
     376             :                             // loop over two identical polygon paths
     377           1 :                             return;
     378             :                         }
     379             :                         else
     380             :                         {
     381             :                             // enter at rPNa, rPNb; leave at pPNa2, pPNb2. No common edges
     382             :                             // at enter/leave. Check for crossover.
     383          12 :                             const B2DPoint& aPointE(rPNa.maPoint);
     384          12 :                             const B2DVector aPrevAE(rPrevA - aPointE);
     385          24 :                             const B2DVector aNextAE(rNextA - aPointE);
     386          24 :                             const B2DVector aPrevBE(rPrevB - aPointE);
     387             : 
     388          12 :                             const B2DPoint& aPointL(pPNa2->maPoint);
     389          24 :                             const B2DVector aPrevAL(maPNV[pPNa2->mnIP].maPoint - aPointL);
     390          24 :                             const B2DVector aNextAL(maPNV[pPNa2->mnIN].maPoint - aPointL);
     391          24 :                             const B2DVector aNextBL(maPNV[pPNb2->mnIN].maPoint - aPointL);
     392             : 
     393          12 :                             const bool bEnter(impLeftOfEdges(aPrevAE, aNextAE, aPrevBE));
     394          12 :                             const bool bLeave(impLeftOfEdges(aPrevAL, aNextAL, aNextBL));
     395             : 
     396          12 :                             if(bEnter != bLeave)
     397             :                             {
     398             :                                 // crossover; switch start or end
     399          11 :                                 impSwitchNext(rPNa, rPNb);
     400          12 :                             }
     401             :                         }
     402             :                     }
     403         183 :                     else if(rNextA.equal(rPrevB))
     404             :                     {
     405             :                         // common edge in opposite direction enter
     406           2 :                         impSwitchNext(rPNa, rPNb);
     407             :                     }
     408             :                     else
     409             :                     {
     410             :                         // no common edges, check for crossover
     411         181 :                         const B2DPoint& aPoint(rPNa.maPoint);
     412         181 :                         const B2DVector aPrevA(rPrevA - aPoint);
     413         362 :                         const B2DVector aNextA(rNextA - aPoint);
     414         362 :                         const B2DVector aPrevB(rPrevB - aPoint);
     415         362 :                         const B2DVector aNextB(rNextB - aPoint);
     416             : 
     417         181 :                         const bool bEnter(impLeftOfEdges(aPrevA, aNextA, aPrevB));
     418         181 :                         const bool bLeave(impLeftOfEdges(aPrevA, aNextA, aNextB));
     419             : 
     420         181 :                         if(bEnter != bLeave)
     421             :                         {
     422             :                             // crossover
     423         177 :                             impSwitchNext(rPNa, rPNb);
     424         181 :                         }
     425             :                     }
     426             :                 }
     427             :             }
     428             : 
     429        2847 :             void impSolve()
     430             :             {
     431             :                 // sort by point to identify common nodes easier
     432        2847 :                 ::std::sort(maSNV.begin(), maSNV.end());
     433             : 
     434             :                 // handle common nodes
     435        2847 :                 const sal_uInt32 nNodeCount(maSNV.size());
     436        2847 :                 sal_uInt32 a(0);
     437             : 
     438             :                 // snap unsharp-equal points
     439        2847 :                 if(nNodeCount)
     440             :                 {
     441        2847 :                     basegfx::B2DPoint* pLast(&maSNV[0].mpPN->maPoint);
     442             : 
     443       37586 :                     for(a = 1; a < nNodeCount; a++)
     444             :                     {
     445       34739 :                         basegfx::B2DPoint* pCurrent(&maSNV[a].mpPN->maPoint);
     446             : 
     447       34739 :                         if(pLast->equal(*pCurrent) && (pLast->getX() != pCurrent->getX() || pLast->getY() != pCurrent->getY()))
     448             :                         {
     449         325 :                             const basegfx::B2DPoint aMiddle((*pLast + *pCurrent) * 0.5);
     450             : 
     451         325 :                             if(pLast->getX() != aMiddle.getX() || pLast->getY() != aMiddle.getY())
     452             :                             {
     453         252 :                                 maCorrectionTable.push_back(CorrectionPair(*pLast, aMiddle));
     454         252 :                                 *pLast = aMiddle;
     455             :                             }
     456             : 
     457         325 :                             if(pCurrent->getX() != aMiddle.getX() || pCurrent->getY() != aMiddle.getY())
     458             :                             {
     459         163 :                                 maCorrectionTable.push_back(CorrectionPair(*pCurrent, aMiddle));
     460         163 :                                 *pCurrent = aMiddle;
     461         325 :                             }
     462             :                         }
     463             : 
     464       34739 :                         pLast = pCurrent;
     465             :                     }
     466             :                 }
     467             : 
     468       37586 :                 for(a = 0; a < nNodeCount - 1; a++)
     469             :                 {
     470             :                     // test a before using it, not after. Also use nPointCount instead of aSortNodes.size()
     471       34739 :                     PN& rPNb = *(maSNV[a].mpPN);
     472             : 
     473       35505 :                     for(sal_uInt32 b(a + 1); b < nNodeCount && rPNb.maPoint.equal(maSNV[b].mpPN->maPoint); b++)
     474             :                     {
     475         766 :                         impHandleCommon(rPNb, *maSNV[b].mpPN);
     476             :                     }
     477             :                 }
     478        2847 :             }
     479             : 
     480             :         public:
     481        1929 :             explicit solver(const B2DPolygon& rOriginal)
     482             :             :   maOriginal(B2DPolyPolygon(rOriginal)),
     483             :                 mbIsCurve(false),
     484        1929 :                 mbChanged(false)
     485             :             {
     486        1929 :                 const sal_uInt32 nOriginalCount(rOriginal.count());
     487             : 
     488        1929 :                 if(nOriginalCount)
     489             :                 {
     490        1929 :                     B2DPolygon aGeometry(tools::addPointsAtCutsAndTouches(rOriginal));
     491        1929 :                     aGeometry.removeDoublePoints();
     492        1929 :                     aGeometry = tools::simplifyCurveSegments(aGeometry);
     493        1929 :                     mbIsCurve = aGeometry.areControlPointsUsed();
     494             : 
     495        1929 :                     const sal_uInt32 nPointCount(aGeometry.count());
     496             : 
     497             :                     // If it's not a pezier polygon, at least four points are needed to create
     498             :                     // a self-intersection. If it's a bezier polygon, the minimum point number
     499             :                     // is two, since with a single point You get a curve, but no self-intersection
     500        1929 :                     if(nPointCount > 3 || (nPointCount > 1 && mbIsCurve))
     501             :                     {
     502             :                         // reserve space in point, control and sort vector.
     503        1890 :                         maSNV.reserve(nPointCount);
     504        1890 :                         maPNV.reserve(nPointCount);
     505        1890 :                         maVNV.reserve(mbIsCurve ? nPointCount : 0);
     506             : 
     507             :                         // fill data
     508        1890 :                         impAddPolygon(0, aGeometry);
     509             : 
     510             :                         // solve common nodes
     511        1890 :                         impSolve();
     512        1929 :                     }
     513             :                 }
     514        1929 :             }
     515             : 
     516         957 :             explicit solver(const B2DPolyPolygon& rOriginal)
     517             :             :   maOriginal(rOriginal),
     518             :                 mbIsCurve(false),
     519         957 :                 mbChanged(false)
     520             :             {
     521         957 :                 sal_uInt32 nOriginalCount(maOriginal.count());
     522             : 
     523         957 :                 if(nOriginalCount)
     524             :                 {
     525         957 :                     B2DPolyPolygon aGeometry(tools::addPointsAtCutsAndTouches(maOriginal, true));
     526         957 :                     aGeometry.removeDoublePoints();
     527         957 :                     aGeometry = tools::simplifyCurveSegments(aGeometry);
     528         957 :                     mbIsCurve = aGeometry.areControlPointsUsed();
     529         957 :                     nOriginalCount = aGeometry.count();
     530             : 
     531         957 :                     if(nOriginalCount)
     532             :                     {
     533         957 :                         sal_uInt32 nPointCount(0);
     534         957 :                         sal_uInt32 a(0);
     535             : 
     536             :                         // count points
     537        3508 :                         for(a = 0; a < nOriginalCount; a++)
     538             :                         {
     539        2551 :                             const B2DPolygon aCandidate(aGeometry.getB2DPolygon(a));
     540        2551 :                             const sal_uInt32 nCandCount(aCandidate.count());
     541             : 
     542             :                             // If it's not a bezier curve, at least three points would be needed to have a
     543             :                             // topological relevant (not empty) polygon. Since its not known here if trivial
     544             :                             // edges (dead ends) will be kept or sorted out, add non-bezier polygons with
     545             :                             // more than one point.
     546             :                             // For bezier curves, the minimum for defining an area is also one.
     547        2551 :                             if(nCandCount)
     548             :                             {
     549        2551 :                                 nPointCount += nCandCount;
     550             :                             }
     551        2551 :                         }
     552             : 
     553         957 :                         if(nPointCount)
     554             :                         {
     555             :                             // reserve space in point, control and sort vector.
     556         957 :                             maSNV.reserve(nPointCount);
     557         957 :                             maPNV.reserve(nPointCount);
     558         957 :                             maVNV.reserve(mbIsCurve ? nPointCount : 0);
     559             : 
     560             :                             // fill data
     561         957 :                             sal_uInt32 nInsertIndex(0);
     562             : 
     563        3508 :                             for(a = 0; a < nOriginalCount; a++)
     564             :                             {
     565        2551 :                                 const B2DPolygon aCandidate(aGeometry.getB2DPolygon(a));
     566        2551 :                                 const sal_uInt32 nCandCount(aCandidate.count());
     567             : 
     568             :                                 // use same condition as above, the data vector is
     569             :                                 // pre-allocated
     570        2551 :                                 if(nCandCount)
     571             :                                 {
     572        2551 :                                     impAddPolygon(nInsertIndex, aCandidate);
     573        2551 :                                     nInsertIndex += nCandCount;
     574             :                                 }
     575        2551 :                             }
     576             : 
     577             :                             // solve common nodes
     578         957 :                             impSolve();
     579             :                         }
     580         957 :                     }
     581             :                 }
     582         957 :             }
     583             : 
     584        2886 :             B2DPolyPolygon getB2DPolyPolygon()
     585             :             {
     586        2886 :                 if(mbChanged)
     587             :                 {
     588         335 :                     B2DPolyPolygon aRetval;
     589         335 :                     const sal_uInt32 nCount(maPNV.size());
     590         335 :                     sal_uInt32 nCountdown(nCount);
     591             : 
     592        6549 :                     for(sal_uInt32 a(0); nCountdown && a < nCount; a++)
     593             :                     {
     594        6214 :                         PN& rPN = maPNV[a];
     595             : 
     596        6214 :                         if(SAL_MAX_UINT32 != rPN.mnI)
     597             :                         {
     598             :                             // unused node, start new part polygon
     599        1670 :                             B2DPolygon aNewPart;
     600        1670 :                             PN* pPNCurr = &rPN;
     601             : 
     602        8902 :                             do
     603             :                             {
     604        8902 :                                 const B2DPoint& rPoint = pPNCurr->maPoint;
     605        8902 :                                 aNewPart.append(rPoint);
     606             : 
     607        8902 :                                 if(mbIsCurve)
     608             :                                 {
     609        7211 :                                     const VN& rVNCurr = maVNV[pPNCurr->mnI];
     610             : 
     611        7211 :                                     if(!rVNCurr.maPrev.equalZero())
     612             :                                     {
     613        2321 :                                         aNewPart.setPrevControlPoint(aNewPart.count() - 1, rPoint + rVNCurr.maPrev);
     614             :                                     }
     615             : 
     616        7211 :                                     if(!rVNCurr.maNext.equalZero())
     617             :                                     {
     618        2315 :                                         aNewPart.setNextControlPoint(aNewPart.count() - 1, rPoint + rVNCurr.maNext);
     619             :                                     }
     620             :                                 }
     621             : 
     622        8902 :                                 pPNCurr->mnI = SAL_MAX_UINT32;
     623        8902 :                                 nCountdown--;
     624        8902 :                                 pPNCurr = &(maPNV[pPNCurr->mnIN]);
     625             :                             }
     626        7232 :                             while(pPNCurr != &rPN && SAL_MAX_UINT32 != pPNCurr->mnI);
     627             : 
     628             :                             // close and add
     629        1670 :                             aNewPart.setClosed(true);
     630        1670 :                             aRetval.append(aNewPart);
     631             :                         }
     632             :                     }
     633             : 
     634         335 :                     return aRetval;
     635             :                 }
     636             :                 else
     637             :                 {
     638        2551 :                     const sal_uInt32 nCorrectionSize(maCorrectionTable.size());
     639             : 
     640             :                     // no change, return original
     641        2551 :                     if(!nCorrectionSize)
     642             :                     {
     643        2548 :                         return maOriginal;
     644             :                     }
     645             : 
     646             :                     // apply coordinate corrections to ensure inside/outside correctness after solving
     647           3 :                     const sal_uInt32 nPolygonCount(maOriginal.count());
     648           3 :                     basegfx::B2DPolyPolygon aRetval(maOriginal);
     649             : 
     650           6 :                     for(sal_uInt32 a(0); a < nPolygonCount; a++)
     651             :                     {
     652           3 :                         basegfx::B2DPolygon aTemp(aRetval.getB2DPolygon(a));
     653           3 :                         const sal_uInt32 nPointCount(aTemp.count());
     654           3 :                         bool bChanged(false);
     655             : 
     656          51 :                         for(sal_uInt32 b(0); b < nPointCount; b++)
     657             :                         {
     658          48 :                             const basegfx::B2DPoint aCandidate(aTemp.getB2DPoint(b));
     659             : 
     660          96 :                             for(sal_uInt32 c(0); c < nCorrectionSize; c++)
     661             :                             {
     662          48 :                                 if(maCorrectionTable[c].first.getX() == aCandidate.getX() && maCorrectionTable[c].first.getY() == aCandidate.getY())
     663             :                                 {
     664           0 :                                     aTemp.setB2DPoint(b, maCorrectionTable[c].second);
     665           0 :                                     bChanged = true;
     666             :                                 }
     667             :                             }
     668          48 :                         }
     669             : 
     670           3 :                         if(bChanged)
     671             :                         {
     672           0 :                             aRetval.setB2DPolygon(a, aTemp);
     673             :                         }
     674           3 :                     }
     675             : 
     676           3 :                     return aRetval;
     677             :                 }
     678             :             }
     679             :         };
     680             : 
     681             :     } // end of anonymous namespace
     682             : } // end of namespace basegfx
     683             : 
     684             : namespace basegfx
     685             : {
     686             :     namespace tools
     687             :     {
     688             : 
     689         939 :         B2DPolyPolygon solveCrossovers(const B2DPolyPolygon& rCandidate)
     690             :         {
     691         939 :             if(rCandidate.count() > 0L)
     692             :             {
     693         939 :                 solver aSolver(rCandidate);
     694         939 :                 return aSolver.getB2DPolyPolygon();
     695             :             }
     696             :             else
     697             :             {
     698           0 :                 return rCandidate;
     699             :             }
     700             :         }
     701             : 
     702        1921 :         B2DPolyPolygon solveCrossovers(const B2DPolygon& rCandidate)
     703             :         {
     704        1921 :             solver aSolver(rCandidate);
     705        1921 :             return aSolver.getB2DPolyPolygon();
     706             :         }
     707             : 
     708        3111 :         B2DPolyPolygon stripNeutralPolygons(const B2DPolyPolygon& rCandidate)
     709             :         {
     710        3111 :             B2DPolyPolygon aRetval;
     711             : 
     712        8413 :             for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
     713             :             {
     714        5302 :                 const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
     715             : 
     716        5302 :                 if(B2VectorOrientation::Neutral != tools::getOrientation(aCandidate))
     717             :                 {
     718        4856 :                     aRetval.append(aCandidate);
     719             :                 }
     720        5302 :             }
     721             : 
     722        3111 :             return aRetval;
     723             :         }
     724             : 
     725        2434 :         B2DPolyPolygon createNonzeroConform(const B2DPolyPolygon& rCandidate)
     726             :         {
     727        2434 :             B2DPolyPolygon aCandidate;
     728             : 
     729             :             // remove all self-intersections and intersections
     730        2434 :             if(rCandidate.count() == 1)
     731             :             {
     732        1921 :                 aCandidate = basegfx::tools::solveCrossovers(rCandidate.getB2DPolygon(0));
     733             :             }
     734             :             else
     735             :             {
     736         513 :                 aCandidate = basegfx::tools::solveCrossovers(rCandidate);
     737             :             }
     738             : 
     739             :             // cleanup evtl. neutral polygons
     740        2434 :             aCandidate = basegfx::tools::stripNeutralPolygons(aCandidate);
     741             : 
     742             :             // remove all polygons which have the same orientation as the polygon they are directly contained in
     743        2434 :             const sal_uInt32 nCount(aCandidate.count());
     744             : 
     745        2434 :             if(nCount > 1)
     746             :             {
     747             :                 sal_uInt32 a, b;
     748         531 :                 ::std::vector< StripHelper > aHelpers;
     749         531 :                 aHelpers.resize(nCount);
     750             : 
     751        2458 :                 for(a = 0; a < nCount; a++)
     752             :                 {
     753        1927 :                     const B2DPolygon aCand(aCandidate.getB2DPolygon(a));
     754        1927 :                     StripHelper* pNewHelper = &(aHelpers[a]);
     755        1927 :                     pNewHelper->maRange = tools::getRange(aCand);
     756        1927 :                     pNewHelper->meOrinetation = tools::getOrientation(aCand);
     757             : 
     758             :                     // initialize with own orientation
     759        1927 :                     pNewHelper->mnDepth = (B2VectorOrientation::Negative == pNewHelper->meOrinetation ? -1 : 1);
     760        1927 :                 }
     761             : 
     762        1927 :                 for(a = 0; a < nCount - 1; a++)
     763             :                 {
     764        1396 :                     const B2DPolygon aCandA(aCandidate.getB2DPolygon(a));
     765        1396 :                     StripHelper& rHelperA = aHelpers[a];
     766             : 
     767       15609 :                     for(b = a + 1; b < nCount; b++)
     768             :                     {
     769       14213 :                         const B2DPolygon aCandB(aCandidate.getB2DPolygon(b));
     770       14213 :                         StripHelper& rHelperB = aHelpers[b];
     771       14213 :                         const bool bAInB(rHelperB.maRange.isInside(rHelperA.maRange) && tools::isInside(aCandB, aCandA, true));
     772             : 
     773       14213 :                         if(bAInB)
     774             :                         {
     775             :                             // A is inside B, add orientation of B to A
     776           0 :                             rHelperA.mnDepth += (B2VectorOrientation::Negative == rHelperB.meOrinetation ? -1 : 1);
     777             :                         }
     778             : 
     779       14213 :                         const bool bBInA(rHelperA.maRange.isInside(rHelperB.maRange) && tools::isInside(aCandA, aCandB, true));
     780             : 
     781       14213 :                         if(bBInA)
     782             :                         {
     783             :                             // B is inside A, add orientation of A to B
     784         544 :                             rHelperB.mnDepth += (B2VectorOrientation::Negative == rHelperA.meOrinetation ? -1 : 1);
     785             :                         }
     786       14213 :                     }
     787        1396 :                 }
     788             : 
     789        1062 :                 const B2DPolyPolygon aSource(aCandidate);
     790         531 :                 aCandidate.clear();
     791             : 
     792        2458 :                 for(a = 0L; a < nCount; a++)
     793             :                 {
     794        1927 :                     const StripHelper& rHelper = aHelpers[a];
     795             :                     // for contained unequal oriented polygons sum will be 0
     796             :                     // for contained equal it will be >=2 or <=-2
     797             :                     // for free polygons (not contained) it will be 1 or -1
     798             :                     // -> accept all which are >=-1 && <= 1
     799        1927 :                     bool bAcceptEntry(rHelper.mnDepth >= -1 && rHelper.mnDepth <= 1);
     800             : 
     801        1927 :                     if(bAcceptEntry)
     802             :                     {
     803        1923 :                         aCandidate.append(aSource.getB2DPolygon(a));
     804             :                     }
     805         531 :                 }
     806             :             }
     807             : 
     808        2434 :             return aCandidate;
     809             :         }
     810             : 
     811         148 :         B2DPolyPolygon stripDispensablePolygons(const B2DPolyPolygon& rCandidate, bool bKeepAboveZero)
     812             :         {
     813         148 :             const sal_uInt32 nCount(rCandidate.count());
     814         148 :             B2DPolyPolygon aRetval;
     815             : 
     816         148 :             if(nCount)
     817             :             {
     818         148 :                 if(nCount == 1L)
     819             :                 {
     820           0 :                     if(!bKeepAboveZero && B2VectorOrientation::Positive == tools::getOrientation(rCandidate.getB2DPolygon(0L)))
     821             :                     {
     822           0 :                         aRetval = rCandidate;
     823             :                     }
     824             :                 }
     825             :                 else
     826             :                 {
     827             :                     sal_uInt32 a, b;
     828         148 :                     ::std::vector< StripHelper > aHelpers;
     829         148 :                     aHelpers.resize(nCount);
     830             : 
     831         460 :                     for(a = 0L; a < nCount; a++)
     832             :                     {
     833         312 :                         const B2DPolygon aCandidate(rCandidate.getB2DPolygon(a));
     834         312 :                         StripHelper* pNewHelper = &(aHelpers[a]);
     835         312 :                         pNewHelper->maRange = tools::getRange(aCandidate);
     836         312 :                         pNewHelper->meOrinetation = tools::getOrientation(aCandidate);
     837         312 :                         pNewHelper->mnDepth = (B2VectorOrientation::Negative == pNewHelper->meOrinetation ? -1L : 0L);
     838         312 :                     }
     839             : 
     840         312 :                     for(a = 0L; a < nCount - 1L; a++)
     841             :                     {
     842         164 :                         const B2DPolygon aCandA(rCandidate.getB2DPolygon(a));
     843         164 :                         StripHelper& rHelperA = aHelpers[a];
     844             : 
     845         355 :                         for(b = a + 1L; b < nCount; b++)
     846             :                         {
     847         191 :                             const B2DPolygon aCandB(rCandidate.getB2DPolygon(b));
     848         191 :                             StripHelper& rHelperB = aHelpers[b];
     849         191 :                             const bool bAInB(rHelperB.maRange.isInside(rHelperA.maRange) && tools::isInside(aCandB, aCandA, true));
     850         191 :                             const bool bBInA(rHelperA.maRange.isInside(rHelperB.maRange) && tools::isInside(aCandA, aCandB, true));
     851             : 
     852         191 :                             if(bAInB && bBInA)
     853             :                             {
     854             :                                 // congruent
     855          10 :                                 if(rHelperA.meOrinetation == rHelperB.meOrinetation)
     856             :                                 {
     857             :                                     // two polys or two holes. Lower one of them to get one of them out of the way.
     858             :                                     // Since each will be contained in the other one, both will be increased, too.
     859             :                                     // So, for lowering, increase only one of them
     860           5 :                                     rHelperA.mnDepth++;
     861             :                                 }
     862             :                                 else
     863             :                                 {
     864             :                                     // poly and hole. They neutralize, so get rid of both. Move securely below zero.
     865           0 :                                     rHelperA.mnDepth = -((sal_Int32)nCount);
     866           0 :                                     rHelperB.mnDepth = -((sal_Int32)nCount);
     867             :                                 }
     868             :                             }
     869             :                             else
     870             :                             {
     871         186 :                                 if(bAInB)
     872             :                                 {
     873           9 :                                     if(B2VectorOrientation::Negative == rHelperB.meOrinetation)
     874             :                                     {
     875           0 :                                         rHelperA.mnDepth--;
     876             :                                     }
     877             :                                     else
     878             :                                     {
     879           9 :                                         rHelperA.mnDepth++;
     880             :                                     }
     881             :                                 }
     882         177 :                                 else if(bBInA)
     883             :                                 {
     884          51 :                                     if(B2VectorOrientation::Negative == rHelperA.meOrinetation)
     885             :                                     {
     886           0 :                                         rHelperB.mnDepth--;
     887             :                                     }
     888             :                                     else
     889             :                                     {
     890          51 :                                         rHelperB.mnDepth++;
     891             :                                     }
     892             :                                 }
     893             :                             }
     894         191 :                         }
     895         164 :                     }
     896             : 
     897         460 :                     for(a = 0L; a < nCount; a++)
     898             :                     {
     899         312 :                         const StripHelper& rHelper = aHelpers[a];
     900         312 :                         bool bAcceptEntry(bKeepAboveZero ? 1L <= rHelper.mnDepth : 0L == rHelper.mnDepth);
     901             : 
     902         312 :                         if(bAcceptEntry)
     903             :                         {
     904          97 :                             aRetval.append(rCandidate.getB2DPolygon(a));
     905             :                         }
     906         148 :                     }
     907             :                 }
     908             :             }
     909             : 
     910         148 :             return aRetval;
     911             :         }
     912             : 
     913           8 :         B2DPolyPolygon prepareForPolygonOperation(const B2DPolygon& rCandidate)
     914             :         {
     915           8 :             solver aSolver(rCandidate);
     916          16 :             B2DPolyPolygon aRetval(stripNeutralPolygons(aSolver.getB2DPolyPolygon()));
     917             : 
     918          16 :             return correctOrientations(aRetval);
     919             :         }
     920             : 
     921          18 :         B2DPolyPolygon prepareForPolygonOperation(const B2DPolyPolygon& rCandidate)
     922             :         {
     923          18 :             solver aSolver(rCandidate);
     924          36 :             B2DPolyPolygon aRetval(stripNeutralPolygons(aSolver.getB2DPolyPolygon()));
     925             : 
     926          36 :             return correctOrientations(aRetval);
     927             :         }
     928             : 
     929           1 :         B2DPolyPolygon solvePolygonOperationOr(const B2DPolyPolygon& rCandidateA, const B2DPolyPolygon& rCandidateB)
     930             :         {
     931           1 :             if(!rCandidateA.count())
     932             :             {
     933           0 :                 return rCandidateB;
     934             :             }
     935           1 :             else if(!rCandidateB.count())
     936             :             {
     937           0 :                 return rCandidateA;
     938             :             }
     939             :             else
     940             :             {
     941             :                 // concatenate polygons, solve crossovers and throw away all sub-polygons
     942             :                 // which have a depth other than 0.
     943           1 :                 B2DPolyPolygon aRetval(rCandidateA);
     944             : 
     945           1 :                 aRetval.append(rCandidateB);
     946           1 :                 aRetval = solveCrossovers(aRetval);
     947           1 :                 aRetval = stripNeutralPolygons(aRetval);
     948             : 
     949           1 :                 return stripDispensablePolygons(aRetval, false);
     950             :             }
     951             :         }
     952             : 
     953           2 :         B2DPolyPolygon solvePolygonOperationXor(const B2DPolyPolygon& rCandidateA, const B2DPolyPolygon& rCandidateB)
     954             :         {
     955           2 :             if(!rCandidateA.count())
     956             :             {
     957           0 :                 return rCandidateB;
     958             :             }
     959           2 :             else if(!rCandidateB.count())
     960             :             {
     961           0 :                 return rCandidateA;
     962             :             }
     963             :             else
     964             :             {
     965             :                 // XOR is pretty simple: By definition it is the simple concatenation of
     966             :                 // the single polygons since we imply XOR fill rule. Make it intersection-free
     967             :                 // and correct orientations
     968           2 :                 B2DPolyPolygon aRetval(rCandidateA);
     969             : 
     970           2 :                 aRetval.append(rCandidateB);
     971           2 :                 aRetval = solveCrossovers(aRetval);
     972           2 :                 aRetval = stripNeutralPolygons(aRetval);
     973             : 
     974           2 :                 return correctOrientations(aRetval);
     975             :             }
     976             :         }
     977             : 
     978           4 :         B2DPolyPolygon solvePolygonOperationAnd(const B2DPolyPolygon& rCandidateA, const B2DPolyPolygon& rCandidateB)
     979             :         {
     980           4 :             if(!rCandidateA.count())
     981             :             {
     982           0 :                 return B2DPolyPolygon();
     983             :             }
     984           4 :             else if(!rCandidateB.count())
     985             :             {
     986           0 :                 return B2DPolyPolygon();
     987             :             }
     988             :             else
     989             :             {
     990             :                 // concatenate polygons, solve crossovers and throw away all sub-polygons
     991             :                 // with a depth of < 1. This means to keep all polygons where at least two
     992             :                 // polygons do overlap.
     993           4 :                 B2DPolyPolygon aRetval(rCandidateA);
     994             : 
     995           4 :                 aRetval.append(rCandidateB);
     996           4 :                 aRetval = solveCrossovers(aRetval);
     997           4 :                 aRetval = stripNeutralPolygons(aRetval);
     998             : 
     999           4 :                 return stripDispensablePolygons(aRetval, true);
    1000             :             }
    1001             :         }
    1002             : 
    1003           3 :         B2DPolyPolygon solvePolygonOperationDiff(const B2DPolyPolygon& rCandidateA, const B2DPolyPolygon& rCandidateB)
    1004             :         {
    1005           3 :             if(!rCandidateA.count())
    1006             :             {
    1007           0 :                 return B2DPolyPolygon();
    1008             :             }
    1009           3 :             else if(!rCandidateB.count())
    1010             :             {
    1011           0 :                 return rCandidateA;
    1012             :             }
    1013             :             else
    1014             :             {
    1015             :                 // Make B topologically to holes and append to A
    1016           3 :                 B2DPolyPolygon aRetval(rCandidateB);
    1017             : 
    1018           3 :                 aRetval.flip();
    1019           3 :                 aRetval.append(rCandidateA);
    1020             : 
    1021             :                 // solve crossovers and throw away all sub-polygons which have a
    1022             :                 // depth other than 0.
    1023           3 :                 aRetval = basegfx::tools::solveCrossovers(aRetval);
    1024           3 :                 aRetval = basegfx::tools::stripNeutralPolygons(aRetval);
    1025             : 
    1026           3 :                 return basegfx::tools::stripDispensablePolygons(aRetval, false);
    1027             :             }
    1028             :         }
    1029             : 
    1030           0 :         B2DPolyPolygon mergeToSinglePolyPolygon(const B2DPolyPolygonVector& rInput)
    1031             :         {
    1032           0 :             B2DPolyPolygonVector aInput(rInput);
    1033             : 
    1034             :             // first step: prepareForPolygonOperation and simple merge of non-overlapping
    1035             :             // PolyPolygons for speedup; this is possible for the wanted OR-operation
    1036           0 :             if(!aInput.empty())
    1037             :             {
    1038           0 :                 B2DPolyPolygonVector aResult;
    1039           0 :                 aResult.reserve(aInput.size());
    1040             : 
    1041           0 :                 for(size_t a(0); a < aInput.size(); a++)
    1042             :                 {
    1043           0 :                     const basegfx::B2DPolyPolygon aCandidate(prepareForPolygonOperation(aInput[a]));
    1044             : 
    1045           0 :                     if(!aResult.empty())
    1046             :                     {
    1047           0 :                         const B2DRange aCandidateRange(aCandidate.getB2DRange());
    1048           0 :                         bool bCouldMergeSimple(false);
    1049             : 
    1050           0 :                         for(sal_uInt32 b(0); !bCouldMergeSimple && b < aResult.size(); b++)
    1051             :                         {
    1052           0 :                             basegfx::B2DPolyPolygon aTarget(aResult[b]);
    1053           0 :                             const B2DRange aTargetRange(aTarget.getB2DRange());
    1054             : 
    1055           0 :                             if(!aCandidateRange.overlaps(aTargetRange))
    1056             :                             {
    1057           0 :                                 aTarget.append(aCandidate);
    1058           0 :                                 aResult[b] = aTarget;
    1059           0 :                                 bCouldMergeSimple = true;
    1060             :                             }
    1061           0 :                         }
    1062             : 
    1063           0 :                         if(!bCouldMergeSimple)
    1064             :                         {
    1065           0 :                             aResult.push_back(aCandidate);
    1066             :                         }
    1067             :                     }
    1068             :                     else
    1069             :                     {
    1070           0 :                         aResult.push_back(aCandidate);
    1071             :                     }
    1072           0 :                 }
    1073             : 
    1074           0 :                 aInput = aResult;
    1075             :             }
    1076             : 
    1077             :             // second step: melt pairwise to a single PolyPolygon
    1078           0 :             while(aInput.size() > 1)
    1079             :             {
    1080           0 :                 B2DPolyPolygonVector aResult;
    1081           0 :                 aResult.reserve((aInput.size() / 2) + 1);
    1082             : 
    1083           0 :                 for(size_t a(0); a < aInput.size(); a += 2)
    1084             :                 {
    1085           0 :                     if(a + 1 < aInput.size())
    1086             :                     {
    1087             :                         // a pair for processing
    1088           0 :                         aResult.push_back(solvePolygonOperationOr(aInput[a], aInput[a + 1]));
    1089             :                     }
    1090             :                     else
    1091             :                     {
    1092             :                         // last single PolyPolygon; copy to target to not lose it
    1093           0 :                         aResult.push_back(aInput[a]);
    1094             :                     }
    1095             :                 }
    1096             : 
    1097           0 :                 aInput = aResult;
    1098           0 :             }
    1099             : 
    1100             :             // third step: get result
    1101           0 :             if(1 == aInput.size())
    1102             :             {
    1103           0 :                 return aInput[0];
    1104             :             }
    1105             : 
    1106           0 :             return B2DPolyPolygon();
    1107             :         }
    1108             : 
    1109             :     } // end of namespace tools
    1110             : } // end of namespace basegfx
    1111             : 
    1112             : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */

Generated by: LCOV version 1.11