aw078: resync to DEV300m68for integration

4 files changed, 161 insertions, 8 deletions

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 da3fa202c2a4..d62462b8c097 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.
  *
@@ -194,6 +193,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());
 
@@ -274,6 +276,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());
 
@@ -344,6 +349,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());
 
@@ -3234,6 +3242,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());