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

          Line data    Source code
       1             : /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
       2             : /*
       3             :  * This file is part of the LibreOffice project.
       4             :  *
       5             :  * This Source Code Form is subject to the terms of the Mozilla Public
       6             :  * License, v. 2.0. If a copy of the MPL was not distributed with this
       7             :  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
       8             :  *
       9             :  * This file incorporates work covered by the following license notice:
      10             :  *
      11             :  *   Licensed to the Apache Software Foundation (ASF) under one or more
      12             :  *   contributor license agreements. See the NOTICE file distributed
      13             :  *   with this work for additional information regarding copyright
      14             :  *   ownership. The ASF licenses this file to you under the Apache
      15             :  *   License, Version 2.0 (the "License"); you may not use this file
      16             :  *   except in compliance with the License. You may obtain a copy of
      17             :  *   the License at http://www.apache.org/licenses/LICENSE-2.0 .
      18             :  */
      19             : 
      20             : #include <basegfx/curve/b2dcubicbezier.hxx>
      21             : #include <basegfx/vector/b2dvector.hxx>
      22             : #include <basegfx/polygon/b2dpolygon.hxx>
      23             : #include <basegfx/numeric/ftools.hxx>
      24             : 
      25             : #include <limits>
      26             : 
      27             : // #i37443#
      28             : #define FACTOR_FOR_UNSHARPEN    (1.6)
      29             : #ifdef DBG_UTIL
      30             : static double fMultFactUnsharpen = FACTOR_FOR_UNSHARPEN;
      31             : #endif
      32             : 
      33             : 
      34             : 
      35             : namespace basegfx
      36             : {
      37             :     namespace
      38             :     {
      39           0 :         void ImpSubDivAngle(
      40             :             const B2DPoint& rfPA,           // start point
      41             :             const B2DPoint& rfEA,           // edge on A
      42             :             const B2DPoint& rfEB,           // edge on B
      43             :             const B2DPoint& rfPB,           // end point
      44             :             B2DPolygon& rTarget,            // target polygon
      45             :             double fAngleBound,             // angle bound in [0.0 .. 2PI]
      46             :             bool bAllowUnsharpen,           // #i37443# allow the criteria to get unsharp in recursions
      47             :             sal_uInt16 nMaxRecursionDepth)  // endless loop protection
      48             :         {
      49           0 :             if(nMaxRecursionDepth)
      50             :             {
      51             :                 // do angle test
      52           0 :                 B2DVector aLeft(rfEA - rfPA);
      53           0 :                 B2DVector aRight(rfEB - rfPB);
      54             : 
      55             :                 // #i72104#
      56           0 :                 if(aLeft.equalZero())
      57             :                 {
      58           0 :                     aLeft = rfEB - rfPA;
      59             :                 }
      60             : 
      61           0 :                 if(aRight.equalZero())
      62             :                 {
      63           0 :                     aRight = rfEA - rfPB;
      64             :                 }
      65             : 
      66           0 :                 const double fCurrentAngle(aLeft.angle(aRight));
      67             : 
      68           0 :                 if(fabs(fCurrentAngle) > (F_PI - fAngleBound))
      69             :                 {
      70             :                     // end recursion
      71           0 :                     nMaxRecursionDepth = 0;
      72             :                 }
      73             :                 else
      74             :                 {
      75           0 :                     if(bAllowUnsharpen)
      76             :                     {
      77             :                         // #i37443# unsharpen criteria
      78             : #ifdef DBG_UTIL
      79             :                         fAngleBound *= fMultFactUnsharpen;
      80             : #else
      81           0 :                         fAngleBound *= FACTOR_FOR_UNSHARPEN;
      82             : #endif
      83             :                     }
      84           0 :                 }
      85             :             }
      86             : 
      87           0 :             if(nMaxRecursionDepth)
      88             :             {
      89             :                 // divide at 0.5
      90           0 :                 const B2DPoint aS1L(average(rfPA, rfEA));
      91           0 :                 const B2DPoint aS1C(average(rfEA, rfEB));
      92           0 :                 const B2DPoint aS1R(average(rfEB, rfPB));
      93           0 :                 const B2DPoint aS2L(average(aS1L, aS1C));
      94           0 :                 const B2DPoint aS2R(average(aS1C, aS1R));
      95           0 :                 const B2DPoint aS3C(average(aS2L, aS2R));
      96             : 
      97             :                 // left recursion
      98           0 :                 ImpSubDivAngle(rfPA, aS1L, aS2L, aS3C, rTarget, fAngleBound, bAllowUnsharpen, nMaxRecursionDepth - 1);
      99             : 
     100             :                 // right recursion
     101           0 :                 ImpSubDivAngle(aS3C, aS2R, aS1R, rfPB, rTarget, fAngleBound, bAllowUnsharpen, nMaxRecursionDepth - 1);
     102             :             }
     103             :             else
     104             :             {
     105           0 :                 rTarget.append(rfPB);
     106             :             }
     107           0 :         }
     108             : 
     109           0 :         void ImpSubDivAngleStart(
     110             :             const B2DPoint& rfPA,           // start point
     111             :             const B2DPoint& rfEA,           // edge on A
     112             :             const B2DPoint& rfEB,           // edge on B
     113             :             const B2DPoint& rfPB,           // end point
     114             :             B2DPolygon& rTarget,            // target polygon
     115             :             const double& rfAngleBound,     // angle bound in [0.0 .. 2PI]
     116             :             bool bAllowUnsharpen)           // #i37443# allow the criteria to get unsharp in recursions
     117             :         {
     118           0 :             sal_uInt16 nMaxRecursionDepth(8);
     119           0 :             const B2DVector aLeft(rfEA - rfPA);
     120           0 :             const B2DVector aRight(rfEB - rfPB);
     121           0 :             bool bLeftEqualZero(aLeft.equalZero());
     122           0 :             bool bRightEqualZero(aRight.equalZero());
     123           0 :             bool bAllParallel(false);
     124             : 
     125           0 :             if(bLeftEqualZero && bRightEqualZero)
     126             :             {
     127           0 :                 nMaxRecursionDepth = 0;
     128             :             }
     129             :             else
     130             :             {
     131           0 :                 const B2DVector aBase(rfPB - rfPA);
     132           0 :                 const bool bBaseEqualZero(aBase.equalZero()); // #i72104#
     133             : 
     134           0 :                 if(!bBaseEqualZero)
     135             :                 {
     136           0 :                     const bool bLeftParallel(bLeftEqualZero ? true : areParallel(aLeft, aBase));
     137           0 :                     const bool bRightParallel(bRightEqualZero ? true : areParallel(aRight, aBase));
     138             : 
     139           0 :                     if(bLeftParallel && bRightParallel)
     140             :                     {
     141           0 :                         bAllParallel = true;
     142             : 
     143           0 :                         if(!bLeftEqualZero)
     144             :                         {
     145             :                             double fFactor;
     146             : 
     147           0 :                             if(fabs(aBase.getX()) > fabs(aBase.getY()))
     148             :                             {
     149           0 :                                 fFactor = aLeft.getX() / aBase.getX();
     150             :                             }
     151             :                             else
     152             :                             {
     153           0 :                                 fFactor = aLeft.getY() / aBase.getY();
     154             :                             }
     155             : 
     156           0 :                             if(fFactor >= 0.0 && fFactor <= 1.0)
     157             :                             {
     158           0 :                                 bLeftEqualZero = true;
     159             :                             }
     160             :                         }
     161             : 
     162           0 :                         if(!bRightEqualZero)
     163             :                         {
     164             :                             double fFactor;
     165             : 
     166           0 :                             if(fabs(aBase.getX()) > fabs(aBase.getY()))
     167             :                             {
     168           0 :                                 fFactor = aRight.getX() / -aBase.getX();
     169             :                             }
     170             :                             else
     171             :                             {
     172           0 :                                 fFactor = aRight.getY() / -aBase.getY();
     173             :                             }
     174             : 
     175           0 :                             if(fFactor >= 0.0 && fFactor <= 1.0)
     176             :                             {
     177           0 :                                 bRightEqualZero = true;
     178             :                             }
     179             :                         }
     180             : 
     181           0 :                         if(bLeftEqualZero && bRightEqualZero)
     182             :                         {
     183           0 :                             nMaxRecursionDepth = 0;
     184             :                         }
     185             :                     }
     186           0 :                 }
     187             :             }
     188             : 
     189           0 :             if(nMaxRecursionDepth)
     190             :             {
     191             :                 // divide at 0.5 ad test both edges for angle criteria
     192           0 :                 const B2DPoint aS1L(average(rfPA, rfEA));
     193           0 :                 const B2DPoint aS1C(average(rfEA, rfEB));
     194           0 :                 const B2DPoint aS1R(average(rfEB, rfPB));
     195           0 :                 const B2DPoint aS2L(average(aS1L, aS1C));
     196           0 :                 const B2DPoint aS2R(average(aS1C, aS1R));
     197           0 :                 const B2DPoint aS3C(average(aS2L, aS2R));
     198             : 
     199             :                 // test left
     200           0 :                 bool bAngleIsSmallerLeft(bAllParallel && bLeftEqualZero);
     201           0 :                 if(!bAngleIsSmallerLeft)
     202             :                 {
     203           0 :                     const B2DVector aLeftLeft(bLeftEqualZero ? aS2L - aS1L : aS1L - rfPA); // #i72104#
     204           0 :                     const B2DVector aRightLeft(aS2L - aS3C);
     205           0 :                     const double fCurrentAngleLeft(aLeftLeft.angle(aRightLeft));
     206           0 :                     bAngleIsSmallerLeft = (fabs(fCurrentAngleLeft) > (F_PI - rfAngleBound));
     207             :                 }
     208             : 
     209             :                 // test right
     210           0 :                 bool bAngleIsSmallerRight(bAllParallel && bRightEqualZero);
     211           0 :                 if(!bAngleIsSmallerRight)
     212             :                 {
     213           0 :                     const B2DVector aLeftRight(aS2R - aS3C);
     214           0 :                     const B2DVector aRightRight(bRightEqualZero ? aS2R - aS1R : aS1R - rfPB); // #i72104#
     215           0 :                     const double fCurrentAngleRight(aLeftRight.angle(aRightRight));
     216           0 :                     bAngleIsSmallerRight = (fabs(fCurrentAngleRight) > (F_PI - rfAngleBound));
     217             :                 }
     218             : 
     219           0 :                 if(bAngleIsSmallerLeft && bAngleIsSmallerRight)
     220             :                 {
     221             :                     // no recursion necessary at all
     222           0 :                     nMaxRecursionDepth = 0;
     223             :                 }
     224             :                 else
     225             :                 {
     226             :                     // left
     227           0 :                     if(bAngleIsSmallerLeft)
     228             :                     {
     229           0 :                         rTarget.append(aS3C);
     230             :                     }
     231             :                     else
     232             :                     {
     233           0 :                         ImpSubDivAngle(rfPA, aS1L, aS2L, aS3C, rTarget, rfAngleBound, bAllowUnsharpen, nMaxRecursionDepth);
     234             :                     }
     235             : 
     236             :                     // right
     237           0 :                     if(bAngleIsSmallerRight)
     238             :                     {
     239           0 :                         rTarget.append(rfPB);
     240             :                     }
     241             :                     else
     242             :                     {
     243           0 :                         ImpSubDivAngle(aS3C, aS2R, aS1R, rfPB, rTarget, rfAngleBound, bAllowUnsharpen, nMaxRecursionDepth);
     244             :                     }
     245           0 :                 }
     246             :             }
     247             : 
     248           0 :             if(!nMaxRecursionDepth)
     249             :             {
     250           0 :                 rTarget.append(rfPB);
     251           0 :             }
     252           0 :         }
     253             : 
     254           0 :         void ImpSubDivDistance(
     255             :             const B2DPoint& rfPA,           // start point
     256             :             const B2DPoint& rfEA,           // edge on A
     257             :             const B2DPoint& rfEB,           // edge on B
     258             :             const B2DPoint& rfPB,           // end point
     259             :             B2DPolygon& rTarget,            // target polygon
     260             :             double fDistanceBound2,         // quadratic distance criteria
     261             :             double fLastDistanceError2,     // the last quadratic distance error
     262             :             sal_uInt16 nMaxRecursionDepth)  // endless loop protection
     263             :         {
     264           0 :             if(nMaxRecursionDepth)
     265             :             {
     266             :                 // decide if another recursion is needed. If not, set
     267             :                 // nMaxRecursionDepth to zero
     268             : 
     269             :                 // Perform bezier flatness test (lecture notes from R. Schaback,
     270             :                 // Mathematics of Computer-Aided Design, Uni Goettingen, 2000)
     271             : 
     272             :                 // ||P(t) - L(t)|| <= max     ||b_j - b_0 - j/n(b_n - b_0)||
     273             :                 //                    0<=j<=n
     274             : 
     275             :                 // What is calculated here is an upper bound to the distance from
     276             :                 // a line through b_0 and b_3 (rfPA and P4 in our notation) and the
     277             :                 // curve. We can drop 0 and n from the running indices, since the
     278             :                 // argument of max becomes zero for those cases.
     279           0 :                 const double fJ1x(rfEA.getX() - rfPA.getX() - 1.0/3.0*(rfPB.getX() - rfPA.getX()));
     280           0 :                 const double fJ1y(rfEA.getY() - rfPA.getY() - 1.0/3.0*(rfPB.getY() - rfPA.getY()));
     281           0 :                 const double fJ2x(rfEB.getX() - rfPA.getX() - 2.0/3.0*(rfPB.getX() - rfPA.getX()));
     282           0 :                 const double fJ2y(rfEB.getY() - rfPA.getY() - 2.0/3.0*(rfPB.getY() - rfPA.getY()));
     283           0 :                 const double fDistanceError2(::std::max(fJ1x*fJ1x + fJ1y*fJ1y, fJ2x*fJ2x + fJ2y*fJ2y));
     284             : 
     285             :                 // stop if error measure does not improve anymore. This is a
     286             :                 // safety guard against floating point inaccuracies.
     287             :                 // stop if distance from line is guaranteed to be bounded by d
     288           0 :                 const bool bFurtherDivision(fLastDistanceError2 > fDistanceError2 && fDistanceError2 >= fDistanceBound2);
     289             : 
     290           0 :                 if(bFurtherDivision)
     291             :                 {
     292             :                     // remember last error value
     293           0 :                     fLastDistanceError2 = fDistanceError2;
     294             :                 }
     295             :                 else
     296             :                 {
     297             :                     // stop recustion
     298           0 :                     nMaxRecursionDepth = 0;
     299             :                 }
     300             :             }
     301             : 
     302           0 :             if(nMaxRecursionDepth)
     303             :             {
     304             :                 // divide at 0.5
     305           0 :                 const B2DPoint aS1L(average(rfPA, rfEA));
     306           0 :                 const B2DPoint aS1C(average(rfEA, rfEB));
     307           0 :                 const B2DPoint aS1R(average(rfEB, rfPB));
     308           0 :                 const B2DPoint aS2L(average(aS1L, aS1C));
     309           0 :                 const B2DPoint aS2R(average(aS1C, aS1R));
     310           0 :                 const B2DPoint aS3C(average(aS2L, aS2R));
     311             : 
     312             :                 // left recursion
     313           0 :                 ImpSubDivDistance(rfPA, aS1L, aS2L, aS3C, rTarget, fDistanceBound2, fLastDistanceError2, nMaxRecursionDepth - 1);
     314             : 
     315             :                 // right recursion
     316           0 :                 ImpSubDivDistance(aS3C, aS2R, aS1R, rfPB, rTarget, fDistanceBound2, fLastDistanceError2, nMaxRecursionDepth - 1);
     317             :             }
     318             :             else
     319             :             {
     320           0 :                 rTarget.append(rfPB);
     321             :             }
     322           0 :         }
     323             :     } // end of anonymous namespace
     324             : } // end of namespace basegfx
     325             : 
     326             : 
     327             : 
     328             : namespace basegfx
     329             : {
     330           0 :     B2DCubicBezier::B2DCubicBezier(const B2DCubicBezier& rBezier)
     331             :     :   maStartPoint(rBezier.maStartPoint),
     332             :         maEndPoint(rBezier.maEndPoint),
     333             :         maControlPointA(rBezier.maControlPointA),
     334           0 :         maControlPointB(rBezier.maControlPointB)
     335             :     {
     336           0 :     }
     337             : 
     338           0 :     B2DCubicBezier::B2DCubicBezier()
     339             :     {
     340           0 :     }
     341             : 
     342           0 :     B2DCubicBezier::B2DCubicBezier(const B2DPoint& rStart, const B2DPoint& rControlPointA, const B2DPoint& rControlPointB, const B2DPoint& rEnd)
     343             :     :   maStartPoint(rStart),
     344             :         maEndPoint(rEnd),
     345             :         maControlPointA(rControlPointA),
     346           0 :         maControlPointB(rControlPointB)
     347             :     {
     348           0 :     }
     349             : 
     350           0 :     B2DCubicBezier::~B2DCubicBezier()
     351             :     {
     352           0 :     }
     353             : 
     354             :     // assignment operator
     355           0 :     B2DCubicBezier& B2DCubicBezier::operator=(const B2DCubicBezier& rBezier)
     356             :     {
     357           0 :         maStartPoint = rBezier.maStartPoint;
     358           0 :         maEndPoint = rBezier.maEndPoint;
     359           0 :         maControlPointA = rBezier.maControlPointA;
     360           0 :         maControlPointB = rBezier.maControlPointB;
     361             : 
     362           0 :         return *this;
     363             :     }
     364             : 
     365             :     // compare operators
     366           0 :     bool B2DCubicBezier::operator==(const B2DCubicBezier& rBezier) const
     367             :     {
     368             :         return (
     369           0 :             maStartPoint == rBezier.maStartPoint
     370           0 :             && maEndPoint == rBezier.maEndPoint
     371           0 :             && maControlPointA == rBezier.maControlPointA
     372           0 :             && maControlPointB == rBezier.maControlPointB
     373           0 :         );
     374             :     }
     375             : 
     376           0 :     bool B2DCubicBezier::operator!=(const B2DCubicBezier& rBezier) const
     377             :     {
     378             :         return (
     379           0 :             maStartPoint != rBezier.maStartPoint
     380           0 :             || maEndPoint != rBezier.maEndPoint
     381           0 :             || maControlPointA != rBezier.maControlPointA
     382           0 :             || maControlPointB != rBezier.maControlPointB
     383           0 :         );
     384             :     }
     385             : 
     386           0 :     bool B2DCubicBezier::equal(const B2DCubicBezier& rBezier) const
     387             :     {
     388             :         return (
     389           0 :             maStartPoint.equal(rBezier.maStartPoint)
     390           0 :             && maEndPoint.equal(rBezier.maEndPoint)
     391           0 :             && maControlPointA.equal(rBezier.maControlPointA)
     392           0 :             && maControlPointB.equal(rBezier.maControlPointB)
     393           0 :         );
     394             :     }
     395             : 
     396             :     // test if vectors are used
     397           0 :     bool B2DCubicBezier::isBezier() const
     398             :     {
     399           0 :         if(maControlPointA != maStartPoint || maControlPointB != maEndPoint)
     400             :         {
     401           0 :             return true;
     402             :         }
     403             : 
     404           0 :         return false;
     405             :     }
     406             : 
     407           0 :     void B2DCubicBezier::testAndSolveTrivialBezier()
     408             :     {
     409           0 :         if(maControlPointA != maStartPoint || maControlPointB != maEndPoint)
     410             :         {
     411           0 :             const B2DVector aEdge(maEndPoint - maStartPoint);
     412             : 
     413             :             // controls parallel to edge can be trivial. No edge -> not parallel -> control can
     414             :             // still not be trivial (e.g. ballon loop)
     415           0 :             if(!aEdge.equalZero())
     416             :             {
     417             :                 // get control vectors
     418           0 :                 const B2DVector aVecA(maControlPointA - maStartPoint);
     419           0 :                 const B2DVector aVecB(maControlPointB - maEndPoint);
     420             : 
     421             :                 // check if trivial per se
     422           0 :                 bool bAIsTrivial(aVecA.equalZero());
     423           0 :                 bool bBIsTrivial(aVecB.equalZero());
     424             : 
     425             :                 // #i102241# prepare inverse edge length to normalize cross values;
     426             :                 // else the small compare value used in fTools::equalZero
     427             :                 // will be length dependent and this detection will work as less
     428             :                 // precise as longer the edge is. In principle, the length of the control
     429             :                 // vector would need to be used too, but to be trivial it is assumed to
     430             :                 // be of roughly equal length to the edge, so edge length can be used
     431             :                 // for both. Only needed when one of both is not trivial per se.
     432           0 :                 const double fInverseEdgeLength(bAIsTrivial && bBIsTrivial
     433             :                     ? 1.0
     434           0 :                     : 1.0 / aEdge.getLength());
     435             : 
     436             :                 // if A is not zero, check if it could be
     437           0 :                 if(!bAIsTrivial)
     438             :                 {
     439             :                     // #i102241# parallel to edge? Check aVecA, aEdge. Use cross() which does what
     440             :                     // we need here with the precision we need
     441           0 :                     const double fCross(aVecA.cross(aEdge) * fInverseEdgeLength);
     442             : 
     443           0 :                     if(fTools::equalZero(fCross))
     444             :                     {
     445             :                         // get scale to edge. Use bigger distance for numeric quality
     446           0 :                         const double fScale(fabs(aEdge.getX()) > fabs(aEdge.getY())
     447           0 :                             ? aVecA.getX() / aEdge.getX()
     448           0 :                             : aVecA.getY() / aEdge.getY());
     449             : 
     450             :                         // relative end point of vector in edge range?
     451           0 :                         if(fTools::moreOrEqual(fScale, 0.0) && fTools::lessOrEqual(fScale, 1.0))
     452             :                         {
     453           0 :                             bAIsTrivial = true;
     454             :                         }
     455             :                     }
     456             :                 }
     457             : 
     458             :                 // if B is not zero, check if it could be, but only if A is already trivial;
     459             :                 // else solve to trivial will not be possible for whole edge
     460           0 :                 if(bAIsTrivial && !bBIsTrivial)
     461             :                 {
     462             :                     // parallel to edge? Check aVecB, aEdge
     463           0 :                     const double fCross(aVecB.cross(aEdge) * fInverseEdgeLength);
     464             : 
     465           0 :                     if(fTools::equalZero(fCross))
     466             :                     {
     467             :                         // get scale to edge. Use bigger distance for numeric quality
     468           0 :                         const double fScale(fabs(aEdge.getX()) > fabs(aEdge.getY())
     469           0 :                             ? aVecB.getX() / aEdge.getX()
     470           0 :                             : aVecB.getY() / aEdge.getY());
     471             : 
     472             :                         // end point of vector in edge range? Caution: controlB is directed AGAINST edge
     473           0 :                         if(fTools::lessOrEqual(fScale, 0.0) && fTools::moreOrEqual(fScale, -1.0))
     474             :                         {
     475           0 :                             bBIsTrivial = true;
     476             :                         }
     477             :                     }
     478             :                 }
     479             : 
     480             :                 // if both are/can be reduced, do it.
     481             :                 // Not possible if only one is/can be reduced (!)
     482           0 :                 if(bAIsTrivial && bBIsTrivial)
     483             :                 {
     484           0 :                     maControlPointA = maStartPoint;
     485           0 :                     maControlPointB = maEndPoint;
     486           0 :                 }
     487           0 :             }
     488             :         }
     489           0 :     }
     490             : 
     491             :     namespace {
     492           0 :         double impGetLength(const B2DCubicBezier& rEdge, double fDeviation, sal_uInt32 nRecursionWatch)
     493             :         {
     494           0 :             const double fEdgeLength(rEdge.getEdgeLength());
     495           0 :             const double fControlPolygonLength(rEdge.getControlPolygonLength());
     496           0 :             const double fCurrentDeviation(fTools::equalZero(fControlPolygonLength) ? 0.0 : 1.0 - (fEdgeLength / fControlPolygonLength));
     497             : 
     498           0 :             if(!nRecursionWatch || fTools:: lessOrEqual(fCurrentDeviation, fDeviation))
     499             :             {
     500           0 :                 return (fEdgeLength + fControlPolygonLength) * 0.5;
     501             :             }
     502             :             else
     503             :             {
     504           0 :                 B2DCubicBezier aLeft, aRight;
     505           0 :                 const double fNewDeviation(fDeviation * 0.5);
     506           0 :                 const sal_uInt32 nNewRecursionWatch(nRecursionWatch - 1);
     507             : 
     508           0 :                 rEdge.split(0.5, &aLeft, &aRight);
     509             : 
     510           0 :                 return impGetLength(aLeft, fNewDeviation, nNewRecursionWatch)
     511           0 :                     + impGetLength(aRight, fNewDeviation, nNewRecursionWatch);
     512             :             }
     513             :         }
     514             :     }
     515             : 
     516           0 :     double B2DCubicBezier::getLength(double fDeviation) const
     517             :     {
     518           0 :         if(isBezier())
     519             :         {
     520           0 :             if(fDeviation < 0.00000001)
     521             :             {
     522           0 :                 fDeviation = 0.00000001;
     523             :             }
     524             : 
     525           0 :             return impGetLength(*this, fDeviation, 6);
     526             :         }
     527             :         else
     528             :         {
     529           0 :             return B2DVector(getEndPoint() - getStartPoint()).getLength();
     530             :         }
     531             :     }
     532             : 
     533           0 :     double B2DCubicBezier::getEdgeLength() const
     534             :     {
     535           0 :         const B2DVector aEdge(maEndPoint - maStartPoint);
     536           0 :         return aEdge.getLength();
     537             :     }
     538             : 
     539           0 :     double B2DCubicBezier::getControlPolygonLength() const
     540             :     {
     541           0 :         const B2DVector aVectorA(maControlPointA - maStartPoint);
     542           0 :         const B2DVector aVectorB(maEndPoint - maControlPointB);
     543             : 
     544           0 :         if(!aVectorA.equalZero() || !aVectorB.equalZero())
     545             :         {
     546           0 :             const B2DVector aTop(maControlPointB - maControlPointA);
     547           0 :             return (aVectorA.getLength() + aVectorB.getLength() + aTop.getLength());
     548             :         }
     549             :         else
     550             :         {
     551           0 :             return getEdgeLength();
     552           0 :         }
     553             :     }
     554             : 
     555           0 :     void B2DCubicBezier::adaptiveSubdivideByAngle(B2DPolygon& rTarget, double fAngleBound, bool bAllowUnsharpen) const
     556             :     {
     557           0 :         if(isBezier())
     558             :         {
     559             :             // use support method #i37443# and allow unsharpen the criteria
     560           0 :             ImpSubDivAngleStart(maStartPoint, maControlPointA, maControlPointB, maEndPoint, rTarget, fAngleBound * F_PI180, bAllowUnsharpen);
     561             :         }
     562             :         else
     563             :         {
     564           0 :             rTarget.append(getEndPoint());
     565             :         }
     566           0 :     }
     567             : 
     568           0 :     B2DVector B2DCubicBezier::getTangent(double t) const
     569             :     {
     570           0 :         if(fTools::lessOrEqual(t, 0.0))
     571             :         {
     572             :             // tangent in start point
     573           0 :             B2DVector aTangent(getControlPointA() - getStartPoint());
     574             : 
     575           0 :             if(!aTangent.equalZero())
     576             :             {
     577           0 :                 return aTangent;
     578             :             }
     579             : 
     580             :             // start point and control vector are the same, fallback
     581             :             // to implicit start vector to control point B
     582           0 :             aTangent = (getControlPointB() - getStartPoint()) * 0.3;
     583             : 
     584           0 :             if(!aTangent.equalZero())
     585             :             {
     586           0 :                 return aTangent;
     587             :             }
     588             : 
     589             :             // not a bezier at all, return edge vector
     590           0 :             return (getEndPoint() - getStartPoint()) * 0.3;
     591             :         }
     592           0 :         else if(fTools::moreOrEqual(t, 1.0))
     593             :         {
     594             :             // tangent in end point
     595           0 :             B2DVector aTangent(getEndPoint() - getControlPointB());
     596             : 
     597           0 :             if(!aTangent.equalZero())
     598             :             {
     599           0 :                 return aTangent;
     600             :             }
     601             : 
     602             :             // end point and control vector are the same, fallback
     603             :             // to implicit start vector from control point A
     604           0 :             aTangent = (getEndPoint() - getControlPointA()) * 0.3;
     605             : 
     606           0 :             if(!aTangent.equalZero())
     607             :             {
     608           0 :                 return aTangent;
     609             :             }
     610             : 
     611             :             // not a bezier at all, return edge vector
     612           0 :             return (getEndPoint() - getStartPoint()) * 0.3;
     613             :         }
     614             :         else
     615             :         {
     616             :             // t is in ]0.0 .. 1.0[. Split and extract
     617           0 :             B2DCubicBezier aRight;
     618           0 :             split(t, 0, &aRight);
     619             : 
     620           0 :             return aRight.getControlPointA() - aRight.getStartPoint();
     621             :         }
     622             :     }
     623             : 
     624             :     // #i37443# adaptive subdivide by nCount subdivisions
     625           0 :     void B2DCubicBezier::adaptiveSubdivideByCount(B2DPolygon& rTarget, sal_uInt32 nCount) const
     626             :     {
     627           0 :         const double fLenFact(1.0 / static_cast< double >(nCount + 1));
     628             : 
     629           0 :         for(sal_uInt32 a(1); a <= nCount; a++)
     630             :         {
     631           0 :             const double fPos(static_cast< double >(a) * fLenFact);
     632           0 :             rTarget.append(interpolatePoint(fPos));
     633             :         }
     634             : 
     635           0 :         rTarget.append(getEndPoint());
     636           0 :     }
     637             : 
     638             :     // adaptive subdivide by distance
     639           0 :     void B2DCubicBezier::adaptiveSubdivideByDistance(B2DPolygon& rTarget, double fDistanceBound) const
     640             :     {
     641           0 :         if(isBezier())
     642             :         {
     643             :             ImpSubDivDistance(maStartPoint, maControlPointA, maControlPointB, maEndPoint, rTarget,
     644           0 :                 fDistanceBound * fDistanceBound, ::std::numeric_limits<double>::max(), 30);
     645             :         }
     646             :         else
     647             :         {
     648           0 :             rTarget.append(getEndPoint());
     649             :         }
     650           0 :     }
     651             : 
     652           0 :     B2DPoint B2DCubicBezier::interpolatePoint(double t) const
     653             :     {
     654             :         OSL_ENSURE(t >= 0.0 && t <= 1.0, "B2DCubicBezier::interpolatePoint: Access out of range (!)");
     655             : 
     656           0 :         if(isBezier())
     657             :         {
     658           0 :             const B2DPoint aS1L(interpolate(maStartPoint, maControlPointA, t));
     659           0 :             const B2DPoint aS1C(interpolate(maControlPointA, maControlPointB, t));
     660           0 :             const B2DPoint aS1R(interpolate(maControlPointB, maEndPoint, t));
     661           0 :             const B2DPoint aS2L(interpolate(aS1L, aS1C, t));
     662           0 :             const B2DPoint aS2R(interpolate(aS1C, aS1R, t));
     663             : 
     664           0 :             return interpolate(aS2L, aS2R, t);
     665             :         }
     666             :         else
     667             :         {
     668           0 :             return interpolate(maStartPoint, maEndPoint, t);
     669             :         }
     670             :     }
     671             : 
     672           0 :     double B2DCubicBezier::getSmallestDistancePointToBezierSegment(const B2DPoint& rTestPoint, double& rCut) const
     673             :     {
     674           0 :         const sal_uInt32 nInitialDivisions(3L);
     675           0 :         B2DPolygon aInitialPolygon;
     676             : 
     677             :         // as start make a fix division, creates nInitialDivisions + 2L points
     678           0 :         aInitialPolygon.append(getStartPoint());
     679           0 :         adaptiveSubdivideByCount(aInitialPolygon, nInitialDivisions);
     680             : 
     681             :         // now look for the closest point
     682           0 :         const sal_uInt32 nPointCount(aInitialPolygon.count());
     683           0 :         B2DVector aVector(rTestPoint - aInitialPolygon.getB2DPoint(0L));
     684           0 :         double fQuadDist(aVector.getX() * aVector.getX() + aVector.getY() * aVector.getY());
     685             :         double fNewQuadDist;
     686           0 :         sal_uInt32 nSmallestIndex(0L);
     687             : 
     688           0 :         for(sal_uInt32 a(1L); a < nPointCount; a++)
     689             :         {
     690           0 :             aVector = B2DVector(rTestPoint - aInitialPolygon.getB2DPoint(a));
     691           0 :             fNewQuadDist = aVector.getX() * aVector.getX() + aVector.getY() * aVector.getY();
     692             : 
     693           0 :             if(fNewQuadDist < fQuadDist)
     694             :             {
     695           0 :                 fQuadDist = fNewQuadDist;
     696           0 :                 nSmallestIndex = a;
     697             :             }
     698             :         }
     699             : 
     700             :         // look right and left for even smaller distances
     701           0 :         double fStepValue(1.0 / (double)((nPointCount - 1L) * 2L)); // half the edge step width
     702           0 :         double fPosition((double)nSmallestIndex / (double)(nPointCount - 1L));
     703           0 :         bool bDone(false);
     704             : 
     705           0 :         while(!bDone)
     706             :         {
     707           0 :             if(!bDone)
     708             :             {
     709             :                 // test left
     710           0 :                 double fPosLeft(fPosition - fStepValue);
     711             : 
     712           0 :                 if(fPosLeft < 0.0)
     713             :                 {
     714           0 :                     fPosLeft = 0.0;
     715           0 :                     aVector = B2DVector(rTestPoint - maStartPoint);
     716             :                 }
     717             :                 else
     718             :                 {
     719           0 :                     aVector = B2DVector(rTestPoint - interpolatePoint(fPosLeft));
     720             :                 }
     721             : 
     722           0 :                 fNewQuadDist = aVector.getX() * aVector.getX() + aVector.getY() * aVector.getY();
     723             : 
     724           0 :                 if(fTools::less(fNewQuadDist, fQuadDist))
     725             :                 {
     726           0 :                     fQuadDist = fNewQuadDist;
     727           0 :                     fPosition = fPosLeft;
     728             :                 }
     729             :                 else
     730             :                 {
     731             :                     // test right
     732           0 :                     double fPosRight(fPosition + fStepValue);
     733             : 
     734           0 :                     if(fPosRight > 1.0)
     735             :                     {
     736           0 :                         fPosRight = 1.0;
     737           0 :                         aVector = B2DVector(rTestPoint - maEndPoint);
     738             :                     }
     739             :                     else
     740             :                     {
     741           0 :                         aVector = B2DVector(rTestPoint - interpolatePoint(fPosRight));
     742             :                     }
     743             : 
     744           0 :                     fNewQuadDist = aVector.getX() * aVector.getX() + aVector.getY() * aVector.getY();
     745             : 
     746           0 :                     if(fTools::less(fNewQuadDist, fQuadDist))
     747             :                     {
     748           0 :                         fQuadDist = fNewQuadDist;
     749           0 :                         fPosition = fPosRight;
     750             :                     }
     751             :                     else
     752             :                     {
     753             :                         // not less left or right, done
     754           0 :                         bDone = true;
     755             :                     }
     756             :                 }
     757             :             }
     758             : 
     759           0 :             if(0.0 == fPosition || 1.0 == fPosition)
     760             :             {
     761             :                 // if we are completely left or right, we are done
     762           0 :                 bDone = true;
     763             :             }
     764             : 
     765           0 :             if(!bDone)
     766             :             {
     767             :                 // prepare next step value
     768           0 :                 fStepValue /= 2.0;
     769             :             }
     770             :         }
     771             : 
     772           0 :         rCut = fPosition;
     773           0 :         return sqrt(fQuadDist);
     774             :     }
     775             : 
     776           0 :     void B2DCubicBezier::split(double t, B2DCubicBezier* pBezierA, B2DCubicBezier* pBezierB) const
     777             :     {
     778             :         OSL_ENSURE(t >= 0.0 && t <= 1.0, "B2DCubicBezier::split: Access out of range (!)");
     779             : 
     780           0 :         if(!pBezierA && !pBezierB)
     781             :         {
     782           0 :             return;
     783             :         }
     784             : 
     785           0 :         if(isBezier())
     786             :         {
     787           0 :             const B2DPoint aS1L(interpolate(maStartPoint, maControlPointA, t));
     788           0 :             const B2DPoint aS1C(interpolate(maControlPointA, maControlPointB, t));
     789           0 :             const B2DPoint aS1R(interpolate(maControlPointB, maEndPoint, t));
     790           0 :             const B2DPoint aS2L(interpolate(aS1L, aS1C, t));
     791           0 :             const B2DPoint aS2R(interpolate(aS1C, aS1R, t));
     792           0 :             const B2DPoint aS3C(interpolate(aS2L, aS2R, t));
     793             : 
     794           0 :             if(pBezierA)
     795             :             {
     796           0 :                 pBezierA->setStartPoint(maStartPoint);
     797           0 :                 pBezierA->setEndPoint(aS3C);
     798           0 :                 pBezierA->setControlPointA(aS1L);
     799           0 :                 pBezierA->setControlPointB(aS2L);
     800             :             }
     801             : 
     802           0 :             if(pBezierB)
     803             :             {
     804           0 :                 pBezierB->setStartPoint(aS3C);
     805           0 :                 pBezierB->setEndPoint(maEndPoint);
     806           0 :                 pBezierB->setControlPointA(aS2R);
     807           0 :                 pBezierB->setControlPointB(aS1R);
     808           0 :             }
     809             :         }
     810             :         else
     811             :         {
     812           0 :             const B2DPoint aSplit(interpolate(maStartPoint, maEndPoint, t));
     813             : 
     814           0 :             if(pBezierA)
     815             :             {
     816           0 :                 pBezierA->setStartPoint(maStartPoint);
     817           0 :                 pBezierA->setEndPoint(aSplit);
     818           0 :                 pBezierA->setControlPointA(maStartPoint);
     819           0 :                 pBezierA->setControlPointB(aSplit);
     820             :             }
     821             : 
     822           0 :             if(pBezierB)
     823             :             {
     824           0 :                 pBezierB->setStartPoint(aSplit);
     825           0 :                 pBezierB->setEndPoint(maEndPoint);
     826           0 :                 pBezierB->setControlPointA(aSplit);
     827           0 :                 pBezierB->setControlPointB(maEndPoint);
     828           0 :             }
     829             :         }
     830             :     }
     831             : 
     832           0 :     B2DCubicBezier B2DCubicBezier::snippet(double fStart, double fEnd) const
     833             :     {
     834           0 :         B2DCubicBezier aRetval;
     835             : 
     836           0 :         if(fTools::more(fStart, 1.0))
     837             :         {
     838           0 :             fStart = 1.0;
     839             :         }
     840           0 :         else if(fTools::less(fStart, 0.0))
     841             :         {
     842           0 :             fStart = 0.0;
     843             :         }
     844             : 
     845           0 :         if(fTools::more(fEnd, 1.0))
     846             :         {
     847           0 :             fEnd = 1.0;
     848             :         }
     849           0 :         else if(fTools::less(fEnd, 0.0))
     850             :         {
     851           0 :             fEnd = 0.0;
     852             :         }
     853             : 
     854           0 :         if(fEnd <= fStart)
     855             :         {
     856             :             // empty or NULL, create single point at center
     857           0 :             const double fSplit((fEnd + fStart) * 0.5);
     858           0 :             const B2DPoint aPoint(interpolate(getStartPoint(), getEndPoint(), fSplit));
     859           0 :             aRetval.setStartPoint(aPoint);
     860           0 :             aRetval.setEndPoint(aPoint);
     861           0 :             aRetval.setControlPointA(aPoint);
     862           0 :             aRetval.setControlPointB(aPoint);
     863             :         }
     864             :         else
     865             :         {
     866           0 :             if(isBezier())
     867             :             {
     868             :                 // copy bezier; cut off right, then cut off left. Do not forget to
     869             :                 // adapt cut value when both cuts happen
     870           0 :                 const bool bEndIsOne(fTools::equal(fEnd, 1.0));
     871           0 :                 const bool bStartIsZero(fTools::equalZero(fStart));
     872           0 :                 aRetval = *this;
     873             : 
     874           0 :                 if(!bEndIsOne)
     875             :                 {
     876           0 :                     aRetval.split(fEnd, &aRetval, 0);
     877             : 
     878           0 :                     if(!bStartIsZero)
     879             :                     {
     880           0 :                         fStart /= fEnd;
     881             :                     }
     882             :                 }
     883             : 
     884           0 :                 if(!bStartIsZero)
     885             :                 {
     886           0 :                     aRetval.split(fStart, 0, &aRetval);
     887             :                 }
     888             :             }
     889             :             else
     890             :             {
     891             :                 // no bezier, create simple edge
     892           0 :                 const B2DPoint aPointA(interpolate(getStartPoint(), getEndPoint(), fStart));
     893           0 :                 const B2DPoint aPointB(interpolate(getStartPoint(), getEndPoint(), fEnd));
     894           0 :                 aRetval.setStartPoint(aPointA);
     895           0 :                 aRetval.setEndPoint(aPointB);
     896           0 :                 aRetval.setControlPointA(aPointA);
     897           0 :                 aRetval.setControlPointB(aPointB);
     898             :             }
     899             :         }
     900             : 
     901           0 :         return aRetval;
     902             :     }
     903             : 
     904           0 :     B2DRange B2DCubicBezier::getRange() const
     905             :     {
     906           0 :         B2DRange aRetval(maStartPoint, maEndPoint);
     907             : 
     908           0 :         aRetval.expand(maControlPointA);
     909           0 :         aRetval.expand(maControlPointB);
     910             : 
     911           0 :         return aRetval;
     912             :     }
     913             : 
     914           0 :     bool B2DCubicBezier::getMinimumExtremumPosition(double& rfResult) const
     915             :     {
     916           0 :         ::std::vector< double > aAllResults;
     917             : 
     918           0 :         aAllResults.reserve(4);
     919           0 :         getAllExtremumPositions(aAllResults);
     920             : 
     921           0 :         const sal_uInt32 nCount(aAllResults.size());
     922             : 
     923           0 :         if(!nCount)
     924             :         {
     925           0 :             return false;
     926             :         }
     927           0 :         else if(1 == nCount)
     928             :         {
     929           0 :             rfResult = aAllResults[0];
     930           0 :             return true;
     931             :         }
     932             :         else
     933             :         {
     934           0 :             rfResult = *(::std::min_element(aAllResults.begin(), aAllResults.end()));
     935           0 :             return true;
     936           0 :         }
     937             :     }
     938             : 
     939             :     namespace
     940             :     {
     941           0 :         inline void impCheckExtremumResult(double fCandidate, ::std::vector< double >& rResult)
     942             :         {
     943             :             // check for range ]0.0 .. 1.0[ with excluding 1.0 and 0.0 clearly
     944             :             // by using the equalZero test, NOT ::more or ::less which will use the
     945             :             // ApproxEqual() which is too exact here
     946           0 :             if(fCandidate > 0.0 && !fTools::equalZero(fCandidate))
     947             :             {
     948           0 :                 if(fCandidate < 1.0 && !fTools::equalZero(fCandidate - 1.0))
     949             :                 {
     950           0 :                     rResult.push_back(fCandidate);
     951             :                 }
     952             :             }
     953           0 :         }
     954             :     }
     955             : 
     956           0 :     void B2DCubicBezier::getAllExtremumPositions(::std::vector< double >& rResults) const
     957             :     {
     958           0 :         rResults.clear();
     959             : 
     960             :         // calculate the x-extrema parameters by zeroing first x-derivative
     961             :         // of the cubic bezier's parametric formula, which results in a
     962             :         // quadratic equation: dBezier/dt = t*t*fAX - 2*t*fBX + fCX
     963           0 :         const B2DPoint aControlDiff( maControlPointA - maControlPointB );
     964           0 :         double fCX = maControlPointA.getX() - maStartPoint.getX();
     965           0 :         const double fBX = fCX + aControlDiff.getX();
     966           0 :         const double fAX = 3 * aControlDiff.getX() + (maEndPoint.getX() - maStartPoint.getX());
     967             : 
     968           0 :         if(fTools::equalZero(fCX))
     969             :         {
     970             :             // detect fCX equal zero and truncate to real zero value in that case
     971           0 :             fCX = 0.0;
     972             :         }
     973             : 
     974           0 :         if( !fTools::equalZero(fAX) )
     975             :         {
     976             :             // derivative is polynomial of order 2 => use binomial formula
     977           0 :             const double fD = fBX*fBX - fAX*fCX;
     978           0 :             if( fD >= 0.0 )
     979             :             {
     980           0 :                 const double fS = sqrt(fD);
     981             :                 // calculate both roots (avoiding a numerically unstable subtraction)
     982           0 :                 const double fQ = fBX + ((fBX >= 0) ? +fS : -fS);
     983           0 :                 impCheckExtremumResult(fQ / fAX, rResults);
     984           0 :                 if( !fTools::equalZero(fS) ) // ignore root multiplicity
     985           0 :                     impCheckExtremumResult(fCX / fQ, rResults);
     986             :             }
     987             :         }
     988           0 :         else if( !fTools::equalZero(fBX) )
     989             :         {
     990             :             // derivative is polynomial of order 1 => one extrema
     991           0 :             impCheckExtremumResult(fCX / (2 * fBX), rResults);
     992             :         }
     993             : 
     994             :         // calculate the y-extrema parameters by zeroing first y-derivative
     995           0 :         double fCY = maControlPointA.getY() - maStartPoint.getY();
     996           0 :         const double fBY = fCY + aControlDiff.getY();
     997           0 :         const double fAY = 3 * aControlDiff.getY() + (maEndPoint.getY() - maStartPoint.getY());
     998             : 
     999           0 :         if(fTools::equalZero(fCY))
    1000             :         {
    1001             :             // detect fCY equal zero and truncate to real zero value in that case
    1002           0 :             fCY = 0.0;
    1003             :         }
    1004             : 
    1005           0 :         if( !fTools::equalZero(fAY) )
    1006             :         {
    1007             :             // derivative is polynomial of order 2 => use binomial formula
    1008           0 :             const double fD = fBY*fBY - fAY*fCY;
    1009           0 :             if( fD >= 0.0 )
    1010             :             {
    1011           0 :                 const double fS = sqrt(fD);
    1012             :                 // calculate both roots (avoiding a numerically unstable subtraction)
    1013           0 :                 const double fQ = fBY + ((fBY >= 0) ? +fS : -fS);
    1014           0 :                 impCheckExtremumResult(fQ / fAY, rResults);
    1015           0 :                 if( !fTools::equalZero(fS) ) // ignore root multiplicity
    1016           0 :                     impCheckExtremumResult(fCY / fQ, rResults);
    1017             :             }
    1018             :         }
    1019           0 :         else if( !fTools::equalZero(fBY) )
    1020             :         {
    1021             :             // derivative is polynomial of order 1 => one extrema
    1022           0 :             impCheckExtremumResult(fCY / (2 * fBY), rResults);
    1023           0 :         }
    1024           0 :     }
    1025             : 
    1026             : } // end of namespace basegfx
    1027             : 
    1028             : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */

Generated by: LCOV version 1.10