merge commit for m65

9 files changed, 201 insertions, 13 deletions

diff --git a/basegfx/inc/basegfx/curve/b2dcubicbezier.hxx b/basegfx/inc/basegfx/curve/b2dcubicbezier.hxx
index 4dc2f45568f1..81be451499ea 100644
--- a/basegfx/inc/basegfx/curve/b2dcubicbezier.hxx
+++ b/basegfx/inc/basegfx/curve/b2dcubicbezier.hxx
@@ -203,6 +203,22 @@ namespace basegfx
             sense to use reserve(4) at the vector as preparation.
         */
         void getAllExtremumPositions(::std::vector< double >& rResults) const;
+
+        /** Get optimum-split position on this segment
+
+            This method calculates the positions of all points of the segment
+            that have the maximimum distance to the corresponding line from
+            startpoint-endpoint. This helps to approximate the bezier curve
+            with a minimum number of line segments
+
+            @param fResults
+             Result positions are in the range ]0.0 .. 1.0[
+            Cubic beziers have at most two of these positions
+
+            @return
+            Returns the number of split positions found
+        */
+        int getMaxDistancePositions( double fResults[2]) const;
     };
 } // end of namespace basegfx
 
diff --git a/basegfx/inc/basegfx/polygon/b2dpolygon.hxx b/basegfx/inc/basegfx/polygon/b2dpolygon.hxx
index ee12d55d460b..c0de4b57ced8 100644
--- a/basegfx/inc/basegfx/polygon/b2dpolygon.hxx
+++ b/basegfx/inc/basegfx/polygon/b2dpolygon.hxx
@@ -7,7 +7,6 @@
  * OpenOffice.org - a multi-platform office productivity suite
  *
  * $RCSfile: b2dpolygon.hxx,v $
- * $Revision: 1.14 $
  *
  * This file is part of OpenOffice.org.
  *
@@ -88,7 +87,9 @@ namespace basegfx
 
         /// Coordinate insert/append
         void insert(sal_uInt32 nIndex, const basegfx::B2DPoint& rPoint, sal_uInt32 nCount = 1);
-        void append(const basegfx::B2DPoint& rPoint, sal_uInt32 nCount = 1);
+        void append(const basegfx::B2DPoint& rPoint, sal_uInt32 nCount);
+        void append(const basegfx::B2DPoint& rPoint);
+        void reserve(sal_uInt32 nCount);
 
         /// Basic ControlPoint interface
         basegfx::B2DPoint getPrevControlPoint(sal_uInt32 nIndex) const;
diff --git a/basegfx/inc/basegfx/range/b1drange.hxx b/basegfx/inc/basegfx/range/b1drange.hxx
index efca06d92dfd..366431c3cd50 100644
--- a/basegfx/inc/basegfx/range/b1drange.hxx
+++ b/basegfx/inc/basegfx/range/b1drange.hxx
@@ -7,7 +7,6 @@
  * OpenOffice.org - a multi-platform office productivity suite
  *
  * $RCSfile: b1drange.hxx,v $
- * $Revision: 1.15 $
  *
  * This file is part of OpenOffice.org.
  *
@@ -131,6 +130,11 @@ namespace basegfx
             return maRange.overlaps(rRange.maRange);
         }
 
+        bool overlapsMore(const B1DRange& rRange) const
+        {
+            return maRange.overlapsMore(rRange.maRange);
+        }
+
         void expand(double fValue)
         {
             maRange.expand(fValue);
diff --git a/basegfx/inc/basegfx/range/b2drange.hxx b/basegfx/inc/basegfx/range/b2drange.hxx
index 66892865399f..8a70d4782f47 100644
--- a/basegfx/inc/basegfx/range/b2drange.hxx
+++ b/basegfx/inc/basegfx/range/b2drange.hxx
@@ -7,7 +7,6 @@
  * OpenOffice.org - a multi-platform office productivity suite
  *
  * $RCSfile: b2drange.hxx,v $
- * $Revision: 1.19 $
  *
  * This file is part of OpenOffice.org.
  *
@@ -222,6 +221,14 @@ namespace basegfx
                 );
         }
 
+        bool overlapsMore(const B2DRange& rRange) const
+        {
+            return (
+                maRangeX.overlapsMore(rRange.maRangeX)
+                && maRangeY.overlapsMore(rRange.maRangeY)
+                );
+        }
+
         void expand(const B2DTuple& rTuple)
         {
             maRangeX.expand(rTuple.getX());
diff --git a/basegfx/inc/basegfx/range/basicrange.hxx b/basegfx/inc/basegfx/range/basicrange.hxx
index a7c402c905c8..59d13cf530c0 100644
--- a/basegfx/inc/basegfx/range/basicrange.hxx
+++ b/basegfx/inc/basegfx/range/basicrange.hxx
@@ -7,7 +7,6 @@
  * OpenOffice.org - a multi-platform office productivity suite
  *
  * $RCSfile: basicrange.hxx,v $
- * $Revision: 1.15 $
  *
  * This file is part of OpenOffice.org.
  *
@@ -142,6 +141,14 @@ namespace basegfx
             }
         }
 
+        bool overlapsMore(const BasicRange& rRange) const
+        {
+            if(isEmpty() || rRange.isEmpty())
+                return false;
+            // returns true if the overlap is more than just a touching at the limits
+            return ((rRange.mnMaximum > mnMinimum) && (rRange.mnMinimum < mnMaximum));
+        }
+
         bool operator==( const BasicRange& rRange ) const
         {
             return (mnMinimum == rRange.mnMinimum && mnMaximum == rRange.mnMaximum);
diff --git a/basegfx/source/curve/b2dcubicbezier.cxx b/basegfx/source/curve/b2dcubicbezier.cxx
index e7247a95333b..83c620df7870 100644
--- a/basegfx/source/curve/b2dcubicbezier.cxx
+++ b/basegfx/source/curve/b2dcubicbezier.cxx
@@ -7,7 +7,6 @@
  * OpenOffice.org - a multi-platform office productivity suite
  *
  * $RCSfile: b2dcubicbezier.cxx,v $
- * $Revision: 1.16 $
  *
  * This file is part of OpenOffice.org.
  *
@@ -1045,6 +1044,65 @@ namespace basegfx
             impCheckExtremumResult(fCY / (2 * fBY), rResults);
         }
     }
+
+    int B2DCubicBezier::getMaxDistancePositions( double pResult[2]) const
+    {
+        // the distance from the bezier to a line through start and end
+        // is proportional to (ENDx-STARTx,ENDy-STARTy)*(+BEZIERy(t),-BEZIERx(t))
+        // this distance becomes zero for at least t==0 and t==1
+        // its extrema that are between 0..1 are interesting as split candidates
+        // its derived function has the form dD/dt = fA*t^2 + 2*fB*t + fC
+        const B2DPoint aRelativeEndPoint(maEndPoint-maStartPoint);
+        const double fA = 3 * (maEndPoint.getX() - maControlPointB.getX()) * aRelativeEndPoint.getY()
+                - 3 * (maEndPoint.getY() - maControlPointB.getY()) * aRelativeEndPoint.getX();
+        const double fB = (maControlPointB.getX() - maControlPointA.getX()) * aRelativeEndPoint.getY()
+                - (maControlPointB.getY() - maControlPointA.getY()) * aRelativeEndPoint.getX();
+        const double fC = (maControlPointA.getX() - maStartPoint.getX()) * aRelativeEndPoint.getY()
+                - (maControlPointA.getY() - maStartPoint.getY()) * aRelativeEndPoint.getX();
+
+        // test for degenerated case: non-cubic curve
+        if( fTools::equalZero(fA) )
+        {
+            // test for degenerated case: straight line
+            if( fTools::equalZero(fB) )
+                return 0;
+
+            // degenerated case: quadratic bezier
+            pResult[0] = -fC / (2*fB);
+
+            // test root: ignore it when it is outside the curve
+            int nCount = ((pResult[0] > 0) && (pResult[0] < 1));
+            return nCount;
+        }
+
+        // derivative is polynomial of order 2
+        // check if the polynomial has non-imaginary roots
+        const double fD = fB*fB - fA*fC;
+        if( fD >= 0.0 ) // TODO: is this test needed? geometrically not IMHO
+        {
+            // calculate the first root
+            const double fS = sqrt(fD);
+            const double fQ = fB + ((fB >= 0) ? +fS : -fS);
+            pResult[0] = fQ / fA;
+            // test root: ignore it when it is outside the curve
+            int nCount = ((pResult[0] > 0) && (pResult[0] < 1));
+
+            // ignore multiplicit roots
+            if( !fTools::equalZero(fD) )
+            {
+                 // calculate the second root
+                const double fRoot = fC / fQ;
+                pResult[ nCount ] = fC / fQ;
+                // test root: ignore it when it is outside the curve
+                nCount += ((fRoot > 0) && (fRoot < 1));
+            }
+
+            return nCount;
+        }
+
+        return 0;
+    }
+
 } // end of namespace basegfx
 
 // eof
diff --git a/basegfx/source/polygon/b2dpolygon.cxx b/basegfx/source/polygon/b2dpolygon.cxx
index 467a4b90f516..48d00ddcec7d 100644
--- a/basegfx/source/polygon/b2dpolygon.cxx
+++ b/basegfx/source/polygon/b2dpolygon.cxx
@@ -7,7 +7,6 @@
  * OpenOffice.org - a multi-platform office productivity suite
  *
  * $RCSfile: b2dpolygon.cxx,v $
- * $Revision: 1.22 $
  *
  * This file is part of OpenOffice.org.
  *
@@ -123,6 +122,16 @@ public:
         maVector[nIndex].setCoordinate(rValue);
     }
 
+    void reserve(sal_uInt32 nCount)
+    {
+        maVector.reserve(nCount);
+    }
+
+    void append(const CoordinateData2D& rValue)
+    {
+        maVector.push_back(rValue);
+    }
+
     void insert(sal_uInt32 nIndex, const CoordinateData2D& rValue, sal_uInt32 nCount)
     {
         if(nCount)
@@ -380,6 +389,17 @@ public:
         }
     }
 
+    void append(const ControlVectorPair2D& rValue)
+    {
+        maVector.push_back(rValue);
+
+        if(!rValue.getPrevVector().equalZero())
+            mnUsedVectors += 1;
+
+        if(!rValue.getNextVector().equalZero())
+            mnUsedVectors += 1;
+    }
+
     void insert(sal_uInt32 nIndex, const ControlVectorPair2D& rValue, sal_uInt32 nCount)
     {
         if(nCount)
@@ -741,6 +761,24 @@ public:
         maPoints.setCoordinate(nIndex, rValue);
     }
 
+    void reserve(sal_uInt32 nCount)
+    {
+        maPoints.reserve(nCount);
+    }
+
+    void append(const basegfx::B2DPoint& rPoint)
+    {
+        mpBufferedData.reset(); // TODO: is this needed?
+        const CoordinateData2D aCoordinate(rPoint);
+        maPoints.append(aCoordinate);
+
+        if(mpControlVector)
+        {
+            const ControlVectorPair2D aVectorPair;
+            mpControlVector->append(aVectorPair);
+        }
+    }
+
     void insert(sal_uInt32 nIndex, const basegfx::B2DPoint& rPoint, sal_uInt32 nCount)
     {
         if(nCount)
@@ -1190,6 +1228,11 @@ namespace basegfx
         }
     }
 
+    void B2DPolygon::reserve(sal_uInt32 nCount)
+    {
+        mpPolygon->reserve(nCount);
+    }
+
     void B2DPolygon::insert(sal_uInt32 nIndex, const B2DPoint& rPoint, sal_uInt32 nCount)
     {
         OSL_ENSURE(nIndex <= mpPolygon->count(), "B2DPolygon Insert outside range (!)");
@@ -1208,6 +1251,11 @@ namespace basegfx
         }
     }
 
+    void B2DPolygon::append(const B2DPoint& rPoint)
+    {
+        mpPolygon->append(rPoint);
+    }
+
     B2DPoint B2DPolygon::getPrevControlPoint(sal_uInt32 nIndex) const
     {
         OSL_ENSURE(nIndex < mpPolygon->count(), "B2DPolygon access outside range (!)");
diff --git a/basegfx/source/polygon/b2dpolygoncutandtouch.cxx b/basegfx/source/polygon/b2dpolygoncutandtouch.cxx
index 26016942717d..da6ff8904725 100644
--- a/basegfx/source/polygon/b2dpolygoncutandtouch.cxx
+++ b/basegfx/source/polygon/b2dpolygoncutandtouch.cxx
@@ -7,7 +7,6 @@
  * OpenOffice.org - a multi-platform office productivity suite
  *
  * $RCSfile: b2dpolygoncutandtouch.cxx,v $
- * $Revision: 1.8 $
  *
  * This file is part of OpenOffice.org.
  *
@@ -430,6 +429,7 @@ namespace basegfx
 
             // create subdivided polygons and find cuts between them
             // Keep adaptiveSubdivideByCount due to needed quality
+            aTempPolygonA.reserve(SUBDIVIDE_FOR_CUT_TEST_COUNT + 8);
             aTempPolygonA.append(rCubicA.getStartPoint());
             rCubicA.adaptiveSubdivideByCount(aTempPolygonA, SUBDIVIDE_FOR_CUT_TEST_COUNT);
             aTempPolygonEdge.append(rCurrB);
@@ -470,8 +470,10 @@ namespace basegfx
 
             // create subdivided polygons and find cuts between them
             // Keep adaptiveSubdivideByCount due to needed quality
+            aTempPolygonA.reserve(SUBDIVIDE_FOR_CUT_TEST_COUNT + 8);
             aTempPolygonA.append(rCubicA.getStartPoint());
             rCubicA.adaptiveSubdivideByCount(aTempPolygonA, SUBDIVIDE_FOR_CUT_TEST_COUNT);
+            aTempPolygonB.reserve(SUBDIVIDE_FOR_CUT_TEST_COUNT + 8);
             aTempPolygonB.append(rCubicB.getStartPoint());
             rCubicB.adaptiveSubdivideByCount(aTempPolygonB, SUBDIVIDE_FOR_CUT_TEST_COUNT);
 
@@ -497,6 +499,13 @@ namespace basegfx
             const B2DCubicBezier& rCubicA,
             sal_uInt32 nInd, temporaryPointVector& rTempPoints)
         {
+            // avoid expensive part of this method if possible
+            // TODO: use hasAnyExtremum() method instead when it becomes available
+            double fDummy;
+            const bool bHasAnyExtremum = rCubicA.getMinimumExtremumPosition( fDummy );
+            if( !bHasAnyExtremum )
+                return;
+
             // find all self-intersections on the given bezier segment. Add an entry to the tempPoints
             // for each self intersection point with the cut value describing the relative position on given
             // bezier segment.
@@ -505,6 +514,7 @@ namespace basegfx
 
             // create subdivided polygon and find cuts on it
             // Keep adaptiveSubdivideByCount due to needed quality
+            aTempPolygon.reserve(SUBDIVIDE_FOR_CUT_TEST_COUNT + 8);
             aTempPolygon.append(rCubicA.getStartPoint());
             rCubicA.adaptiveSubdivideByCount(aTempPolygon, SUBDIVIDE_FOR_CUT_TEST_COUNT);
             findCuts(aTempPolygon, aTempPointVector);
@@ -557,7 +567,14 @@ namespace basegfx
                                 const bool bEdgeBIsCurve(aCubicB.isBezier());
                                 const B2DRange aRangeB(aCubicB.getRange());
 
-                                if(aRangeA.overlaps(aRangeB))
+                                // only overlapping segments need to be tested
+                                // consecutive segments touch of course
+                                bool bOverlap = false;
+                                if( b > a+1)
+                                    bOverlap = aRangeA.overlaps(aRangeB);
+                                else
+                                    bOverlap = aRangeA.overlapsMore(aRangeB);
+                                if( bOverlap)
                                 {
                                     if(bEdgeAIsCurve && bEdgeBIsCurve)
                                     {
@@ -599,7 +616,13 @@ namespace basegfx
                                 const B2DPoint aNextB(rCandidate.getB2DPoint(b + 1L == nPointCount ? 0L : b + 1L));
                                 const B2DRange aRangeB(aCurrB, aNextB);
 
-                                if(aRangeA.overlaps(aRangeB))
+                                // consecutive segments touch of course
+                                bool bOverlap = false;
+                                if( b > a+1)
+                                    bOverlap = aRangeA.overlaps(aRangeB);
+                                else
+                                    bOverlap = aRangeA.overlapsMore(aRangeB);
+                                if( bOverlap)
                                 {
                                     findEdgeCutsTwoEdges(aCurrA, aNextA, aCurrB, aNextB, a, b, rTempPoints, rTempPoints);
                                 }
@@ -688,6 +711,7 @@ namespace basegfx
 
             // create subdivided polygon and find cuts on it
             // Keep adaptiveSubdivideByCount due to needed quality
+            aTempPolygon.reserve(SUBDIVIDE_FOR_CUT_TEST_COUNT + 8);
             aTempPolygon.append(rCubicA.getStartPoint());
             rCubicA.adaptiveSubdivideByCount(aTempPolygon, SUBDIVIDE_FOR_CUT_TEST_COUNT);
             findTouches(aTempPolygon, rPointPolygon, aTempPointVector);
@@ -796,7 +820,13 @@ namespace basegfx
                                 const bool bEdgeBIsCurve(aCubicB.isBezier());
                                 const B2DRange aRangeB(aCubicB.getRange());
 
-                                if(aRangeA.overlaps(aRangeB))
+                                // consecutive segments touch of course
+                                bool bOverlap = false;
+                                if( b > a+1)
+                                    bOverlap = aRangeA.overlaps(aRangeB);
+                                else
+                                    bOverlap = aRangeA.overlapsMore(aRangeB);
+                                if( bOverlap)
                                 {
                                     if(bEdgeAIsCurve && bEdgeBIsCurve)
                                     {
@@ -838,7 +868,13 @@ namespace basegfx
                                 const B2DPoint aNextB(rCandidateB.getB2DPoint(b + 1L == nPointCountB ? 0L : b + 1L));
                                 const B2DRange aRangeB(aCurrB, aNextB);
 
-                                if(aRangeA.overlaps(aRangeB))
+                                // consecutive segments touch of course
+                                bool bOverlap = false;
+                                if( b > a+1)
+                                    bOverlap = aRangeA.overlaps(aRangeB);
+                                else
+                                    bOverlap = aRangeA.overlapsMore(aRangeB);
+                                if( bOverlap)
                                 {
                                     // test for simple edge-edge cuts
                                     findEdgeCutsTwoEdges(aCurrA, aNextA, aCurrB, aNextB, a, b, rTempPointsA, rTempPointsB);
diff --git a/basegfx/source/polygon/b2dpolygontools.cxx b/basegfx/source/polygon/b2dpolygontools.cxx
index c1e5dc80d8c4..7485387c6cb9 100644
--- a/basegfx/source/polygon/b2dpolygontools.cxx
+++ b/basegfx/source/polygon/b2dpolygontools.cxx
@@ -7,7 +7,6 @@
  * OpenOffice.org - a multi-platform office productivity suite
  *
  * $RCSfile: b2dpolygontools.cxx,v $
- * $Revision: 1.29.4.1 $
  *
  * This file is part of OpenOffice.org.
  *
@@ -192,6 +191,9 @@ namespace basegfx
                     B2DCubicBezier aBezier;
                     aBezier.setStartPoint(rCandidate.getB2DPoint(0));
 
+                    // perf: try to avoid too many realloctions by guessing the result's pointcount
+                    aRetval.reserve(nPointCount*4);
+
                     // add start point (always)
                     aRetval.append(aBezier.getStartPoint());
 
@@ -272,6 +274,9 @@ namespace basegfx
                     B2DCubicBezier aBezier;
                     aBezier.setStartPoint(rCandidate.getB2DPoint(0));
 
+                    // perf: try to avoid too many realloctions by guessing the result's pointcount
+                    aRetval.reserve(nPointCount*4);
+
                     // add start point (always)
                     aRetval.append(aBezier.getStartPoint());
 
@@ -342,6 +347,9 @@ namespace basegfx
                     B2DCubicBezier aBezier;
                     aBezier.setStartPoint(rCandidate.getB2DPoint(0));
 
+                    // perf: try to avoid too many realloctions by guessing the result's pointcount
+                    aRetval.reserve(nPointCount*4);
+
                     // add start point (always)
                     aRetval.append(aBezier.getStartPoint());
 
@@ -3269,6 +3277,9 @@ namespace basegfx
                 B2DCubicBezier aBezier;
                 aBezier.setStartPoint(rCandidate.getB2DPoint(0));
 
+                // try to avoid costly reallocations
+                aRetval.reserve( nEdgeCount+1);
+
                 // add start point
                 aRetval.append(aBezier.getStartPoint());