xref: /trunk/main/basegfx/source/curve/b2dcubicbezier.cxx (revision cdf0e10c)

/*************************************************************************
 *
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * Copyright 2000, 2010 Oracle and/or its affiliates.
 *
 * OpenOffice.org - a multi-platform office productivity suite
 *
 * This file is part of OpenOffice.org.
 *
 * OpenOffice.org is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License version 3
 * only, as published by the Free Software Foundation.
 *
 * OpenOffice.org is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License version 3 for more details
 * (a copy is included in the LICENSE file that accompanied this code).
 *
 * You should have received a copy of the GNU Lesser General Public License
 * version 3 along with OpenOffice.org.  If not, see
 * <http://www.openoffice.org/license.html>
 * for a copy of the LGPLv3 License.
 *
 ************************************************************************/

// MARKER(update_precomp.py): autogen include statement, do not remove
#include "precompiled_basegfx.hxx"
#include <basegfx/curve/b2dcubicbezier.hxx>
#include <basegfx/vector/b2dvector.hxx>
#include <basegfx/polygon/b2dpolygon.hxx>
#include <basegfx/numeric/ftools.hxx>

#include <limits>

// #i37443#
#define FACTOR_FOR_UNSHARPEN	(1.6)
#ifdef DBG_UTIL
static double fMultFactUnsharpen = FACTOR_FOR_UNSHARPEN;
#endif

//////////////////////////////////////////////////////////////////////////////

namespace basegfx
{
	namespace
	{
		void ImpSubDivAngle(
			const B2DPoint& rfPA,			// start point
			const B2DPoint& rfEA,			// edge on A
			const B2DPoint& rfEB,			// edge on B
			const B2DPoint& rfPB,			// end point
			B2DPolygon& rTarget,			// target polygon
			double fAngleBound,				// angle bound in [0.0 .. 2PI]
			bool bAllowUnsharpen,			// #i37443# allow the criteria to get unsharp in recursions
			sal_uInt16 nMaxRecursionDepth)	// endless loop protection
		{
			if(nMaxRecursionDepth)
			{
				// do angle test
				B2DVector aLeft(rfEA - rfPA);
				B2DVector aRight(rfEB - rfPB);

				// #i72104#
				if(aLeft.equalZero())
				{
					aLeft = rfEB - rfPA;
				}

				if(aRight.equalZero())
				{
					aRight = rfEA - rfPB;
				}

				const double fCurrentAngle(aLeft.angle(aRight));

				if(fabs(fCurrentAngle) > (F_PI - fAngleBound))
				{
					// end recursion
					nMaxRecursionDepth = 0;
				}
				else
				{
					if(bAllowUnsharpen)
					{
						// #i37443# unsharpen criteria
#ifdef DBG_UTIL
						fAngleBound *= fMultFactUnsharpen;
#else
						fAngleBound *= FACTOR_FOR_UNSHARPEN;
#endif
					}
				}
			}

			if(nMaxRecursionDepth)
			{
				// divide at 0.5
				const B2DPoint aS1L(average(rfPA, rfEA));
				const B2DPoint aS1C(average(rfEA, rfEB));
				const B2DPoint aS1R(average(rfEB, rfPB));
				const B2DPoint aS2L(average(aS1L, aS1C));
				const B2DPoint aS2R(average(aS1C, aS1R));
				const B2DPoint aS3C(average(aS2L, aS2R));

				// left recursion
				ImpSubDivAngle(rfPA, aS1L, aS2L, aS3C, rTarget, fAngleBound, bAllowUnsharpen, nMaxRecursionDepth - 1);

				// right recursion
				ImpSubDivAngle(aS3C, aS2R, aS1R, rfPB, rTarget, fAngleBound, bAllowUnsharpen, nMaxRecursionDepth - 1);
			}
			else
			{
				rTarget.append(rfPB);
			}
		}

		void ImpSubDivAngleStart(
			const B2DPoint& rfPA,			// start point
			const B2DPoint& rfEA,			// edge on A
			const B2DPoint& rfEB,			// edge on B
			const B2DPoint& rfPB,			// end point
			B2DPolygon& rTarget,			// target polygon
			const double& rfAngleBound,		// angle bound in [0.0 .. 2PI]
			bool bAllowUnsharpen)			// #i37443# allow the criteria to get unsharp in recursions
		{
			sal_uInt16 nMaxRecursionDepth(8);
			const B2DVector aLeft(rfEA - rfPA);
			const B2DVector aRight(rfEB - rfPB);
			bool bLeftEqualZero(aLeft.equalZero());
			bool bRightEqualZero(aRight.equalZero());
			bool bAllParallel(false);

			if(bLeftEqualZero && bRightEqualZero)
			{
				nMaxRecursionDepth = 0;
			}
			else
			{
				const B2DVector aBase(rfPB - rfPA);
				const bool bBaseEqualZero(aBase.equalZero()); // #i72104#

				if(!bBaseEqualZero)
				{
					const bool bLeftParallel(bLeftEqualZero ? true : areParallel(aLeft, aBase));
					const bool bRightParallel(bRightEqualZero ? true : areParallel(aRight, aBase));

					if(bLeftParallel && bRightParallel)
					{
						bAllParallel = true;

						if(!bLeftEqualZero)
						{
							double fFactor;

							if(fabs(aBase.getX()) > fabs(aBase.getY()))
							{
								fFactor = aLeft.getX() / aBase.getX();
							}
							else
							{
								fFactor = aLeft.getY() / aBase.getY();
							}

							if(fFactor >= 0.0 && fFactor <= 1.0)
							{
								bLeftEqualZero = true;
							}
						}

						if(!bRightEqualZero)
						{
							double fFactor;

							if(fabs(aBase.getX()) > fabs(aBase.getY()))
							{
								fFactor = aRight.getX() / -aBase.getX();
							}
							else
							{
								fFactor = aRight.getY() / -aBase.getY();
							}

							if(fFactor >= 0.0 && fFactor <= 1.0)
							{
								bRightEqualZero = true;
							}
						}

						if(bLeftEqualZero && bRightEqualZero)
						{
							nMaxRecursionDepth = 0;
						}
					}
				}
			}

			if(nMaxRecursionDepth)
			{
				// divide at 0.5 ad test both edges for angle criteria
				const B2DPoint aS1L(average(rfPA, rfEA));
				const B2DPoint aS1C(average(rfEA, rfEB));
				const B2DPoint aS1R(average(rfEB, rfPB));
				const B2DPoint aS2L(average(aS1L, aS1C));
				const B2DPoint aS2R(average(aS1C, aS1R));
				const B2DPoint aS3C(average(aS2L, aS2R));

				// test left
				bool bAngleIsSmallerLeft(bAllParallel && bLeftEqualZero);
				if(!bAngleIsSmallerLeft)
				{
					const B2DVector aLeftLeft(bLeftEqualZero ? aS2L - aS1L : aS1L - rfPA); // #i72104#
					const B2DVector aRightLeft(aS2L - aS3C);
					const double fCurrentAngleLeft(aLeftLeft.angle(aRightLeft));
					bAngleIsSmallerLeft = (fabs(fCurrentAngleLeft) > (F_PI - rfAngleBound));
				}

				// test right
				bool bAngleIsSmallerRight(bAllParallel && bRightEqualZero);
				if(!bAngleIsSmallerRight)
				{
					const B2DVector aLeftRight(aS2R - aS3C);
					const B2DVector aRightRight(bRightEqualZero ? aS2R - aS1R : aS1R - rfPB); // #i72104#
					const double fCurrentAngleRight(aLeftRight.angle(aRightRight));
					bAngleIsSmallerRight = (fabs(fCurrentAngleRight) > (F_PI - rfAngleBound));
				}

				if(bAngleIsSmallerLeft && bAngleIsSmallerRight)
				{
					// no recursion necessary at all
					nMaxRecursionDepth = 0;
				}
				else
				{
					// left
					if(bAngleIsSmallerLeft)
					{
						rTarget.append(aS3C);
					}
					else
					{
						ImpSubDivAngle(rfPA, aS1L, aS2L, aS3C, rTarget, rfAngleBound, bAllowUnsharpen, nMaxRecursionDepth);
					}

					// right
					if(bAngleIsSmallerRight)
					{
						rTarget.append(rfPB);
					}
					else
					{
						ImpSubDivAngle(aS3C, aS2R, aS1R, rfPB, rTarget, rfAngleBound, bAllowUnsharpen, nMaxRecursionDepth);
					}
				}
			}

			if(!nMaxRecursionDepth)
			{
				rTarget.append(rfPB);
			}
		}

		void ImpSubDivDistance(
			const B2DPoint& rfPA,			// start point
			const B2DPoint& rfEA,			// edge on A
			const B2DPoint& rfEB,			// edge on B
			const B2DPoint& rfPB,			// end point
			B2DPolygon& rTarget,			// target polygon
			double fDistanceBound2,			// quadratic distance criteria
			double fLastDistanceError2,		// the last quadratic distance error
			sal_uInt16 nMaxRecursionDepth)	// endless loop protection
		{
			if(nMaxRecursionDepth)
			{
				// decide if another recursion is needed. If not, set
				// nMaxRecursionDepth to zero

				// Perform bezier flatness test (lecture notes from R. Schaback,
				// Mathematics of Computer-Aided Design, Uni Goettingen, 2000)
				//
				// ||P(t) - L(t)|| <= max     ||b_j - b_0 - j/n(b_n - b_0)||
				//                    0<=j<=n
				//
				// What is calculated here is an upper bound to the distance from
				// a line through b_0 and b_3 (rfPA and P4 in our notation) and the
				// curve. We can drop 0 and n from the running indices, since the
				// argument of max becomes zero for those cases.
				const double fJ1x(rfEA.getX() - rfPA.getX() - 1.0/3.0*(rfPB.getX() - rfPA.getX()));
				const double fJ1y(rfEA.getY() - rfPA.getY() - 1.0/3.0*(rfPB.getY() - rfPA.getY()));
				const double fJ2x(rfEB.getX() - rfPA.getX() - 2.0/3.0*(rfPB.getX() - rfPA.getX()));
				const double fJ2y(rfEB.getY() - rfPA.getY() - 2.0/3.0*(rfPB.getY() - rfPA.getY()));
				const double fDistanceError2(::std::max(fJ1x*fJ1x + fJ1y*fJ1y, fJ2x*fJ2x + fJ2y*fJ2y));

				// stop if error measure does not improve anymore. This is a
				// safety guard against floating point inaccuracies.
				// stop if distance from line is guaranteed to be bounded by d
				const bool bFurtherDivision(fLastDistanceError2 > fDistanceError2 && fDistanceError2 >= fDistanceBound2);

				if(bFurtherDivision)
				{
					// remember last error value
					fLastDistanceError2 = fDistanceError2;
				}
				else
				{
					// stop recustion
					nMaxRecursionDepth = 0;
				}
			}

			if(nMaxRecursionDepth)
			{
				// divide at 0.5
				const B2DPoint aS1L(average(rfPA, rfEA));
				const B2DPoint aS1C(average(rfEA, rfEB));
				const B2DPoint aS1R(average(rfEB, rfPB));
				const B2DPoint aS2L(average(aS1L, aS1C));
				const B2DPoint aS2R(average(aS1C, aS1R));
				const B2DPoint aS3C(average(aS2L, aS2R));

				// left recursion
				ImpSubDivDistance(rfPA, aS1L, aS2L, aS3C, rTarget, fDistanceBound2, fLastDistanceError2, nMaxRecursionDepth - 1);

				// right recursion
				ImpSubDivDistance(aS3C, aS2R, aS1R, rfPB, rTarget, fDistanceBound2, fLastDistanceError2, nMaxRecursionDepth - 1);
			}
			else
			{
				rTarget.append(rfPB);
			}
		}
	} // end of anonymous namespace
} // end of namespace basegfx

//////////////////////////////////////////////////////////////////////////////

namespace basegfx
{
	B2DCubicBezier::B2DCubicBezier(const B2DCubicBezier& rBezier)
	:	maStartPoint(rBezier.maStartPoint),
		maEndPoint(rBezier.maEndPoint),
		maControlPointA(rBezier.maControlPointA),
		maControlPointB(rBezier.maControlPointB)
	{
	}

	B2DCubicBezier::B2DCubicBezier()
	{
	}

	B2DCubicBezier::B2DCubicBezier(const B2DPoint& rStart, const B2DPoint& rEnd)
	:	maStartPoint(rStart),
		maEndPoint(rEnd),
		maControlPointA(rStart),
		maControlPointB(rEnd)
	{
	}

	B2DCubicBezier::B2DCubicBezier(const B2DPoint& rStart, const B2DPoint& rControlPointA, const B2DPoint& rControlPointB, const B2DPoint& rEnd)
	:	maStartPoint(rStart),
		maEndPoint(rEnd),
		maControlPointA(rControlPointA),
		maControlPointB(rControlPointB)
	{
	}

	B2DCubicBezier::~B2DCubicBezier()
	{
	}

	// assignment operator
	B2DCubicBezier& B2DCubicBezier::operator=(const B2DCubicBezier& rBezier)
	{
		maStartPoint = rBezier.maStartPoint;
		maEndPoint = rBezier.maEndPoint;
		maControlPointA = rBezier.maControlPointA;
		maControlPointB = rBezier.maControlPointB;

		return *this;
	}

	// compare operators
	bool B2DCubicBezier::operator==(const B2DCubicBezier& rBezier) const
	{
		return (
			maStartPoint == rBezier.maStartPoint
			&& maEndPoint == rBezier.maEndPoint
			&& maControlPointA == rBezier.maControlPointA
			&& maControlPointB == rBezier.maControlPointB
		);
	}

	bool B2DCubicBezier::operator!=(const B2DCubicBezier& rBezier) const
	{
		return (
			maStartPoint != rBezier.maStartPoint
			|| maEndPoint != rBezier.maEndPoint
			|| maControlPointA != rBezier.maControlPointA
			|| maControlPointB != rBezier.maControlPointB
		);
	}

    bool B2DCubicBezier::equal(const B2DCubicBezier& rBezier) const
    {
		return (
			maStartPoint.equal(rBezier.maStartPoint)
			&& maEndPoint.equal(rBezier.maEndPoint)
			&& maControlPointA.equal(rBezier.maControlPointA)
			&& maControlPointB.equal(rBezier.maControlPointB)
		);
    }

	// test if vectors are used
	bool B2DCubicBezier::isBezier() const
	{
		if(maControlPointA != maStartPoint || maControlPointB != maEndPoint)
		{
			return true;
		}

		return false;
	}

	void B2DCubicBezier::testAndSolveTrivialBezier()
	{
		if(maControlPointA != maStartPoint || maControlPointB != maEndPoint)
		{
			const B2DVector aEdge(maEndPoint - maStartPoint);

			// controls parallel to edge can be trivial. No edge -> not parallel -> control can
            // still not be trivial (e.g. ballon loop)
			if(!aEdge.equalZero())
			{
                // get control vectors
				const B2DVector aVecA(maControlPointA - maStartPoint);
				const B2DVector aVecB(maControlPointB - maEndPoint);

                // check if trivial per se
                bool bAIsTrivial(aVecA.equalZero());
                bool bBIsTrivial(aVecB.equalZero());

                // #i102241# prepare inverse edge length to normalize cross values;
                // else the small compare value used in fTools::equalZero
                // will be length dependent and this detection will work as less
                // precise as longer the edge is. In principle, the length of the control
				// vector would need to be used too, but to be trivial it is assumed to
				// be of roughly equal length to the edge, so edge length can be used
				// for both. Only needed when one of both is not trivial per se.
                const double fInverseEdgeLength(bAIsTrivial && bBIsTrivial
					? 1.0
					: 1.0 / aEdge.getLength());

				// if A is not zero, check if it could be
				if(!bAIsTrivial)
				{
					// #i102241# parallel to edge? Check aVecA, aEdge. Use cross() which does what
					// we need here with the precision we need
					const double fCross(aVecA.cross(aEdge) * fInverseEdgeLength);

					if(fTools::equalZero(fCross))
					{
						// get scale to edge. Use bigger distance for numeric quality
						const double fScale(fabs(aEdge.getX()) > fabs(aEdge.getY())
							? aVecA.getX() / aEdge.getX()
							: aVecA.getY() / aEdge.getY());

						// relative end point of vector in edge range?
						if(fTools::moreOrEqual(fScale, 0.0) && fTools::lessOrEqual(fScale, 1.0))
						{
							bAIsTrivial = true;
						}
					}
				}

                // if B is not zero, check if it could be, but only if A is already trivial;
                // else solve to trivial will not be possible for whole edge
				if(bAIsTrivial && !bBIsTrivial)
				{
					// parallel to edge? Check aVecB, aEdge
					const double fCross(aVecB.cross(aEdge) * fInverseEdgeLength);

					if(fTools::equalZero(fCross))
					{
						// get scale to edge. Use bigger distance for numeric quality
						const double fScale(fabs(aEdge.getX()) > fabs(aEdge.getY())
							? aVecB.getX() / aEdge.getX()
							: aVecB.getY() / aEdge.getY());

						// end point of vector in edge range? Caution: controlB is directed AGAINST edge
						if(fTools::lessOrEqual(fScale, 0.0) && fTools::moreOrEqual(fScale, -1.0))
						{
							bBIsTrivial = true;
						}
					}
				}

                // if both are/can be reduced, do it.
				// Not possible if only one is/can be reduced (!)
				if(bAIsTrivial && bBIsTrivial)
				{
					maControlPointA = maStartPoint;
					maControlPointB = maEndPoint;
				}
			}
		}
	}

    namespace {
        double impGetLength(const B2DCubicBezier& rEdge, double fDeviation, sal_uInt32 nRecursionWatch)
        {
            const double fEdgeLength(rEdge.getEdgeLength());
            const double fControlPolygonLength(rEdge.getControlPolygonLength());
            const double fCurrentDeviation(fTools::equalZero(fControlPolygonLength) ? 0.0 : 1.0 - (fEdgeLength / fControlPolygonLength));

            if(!nRecursionWatch || fTools:: lessOrEqual(fCurrentDeviation, fDeviation))
            {
                return (fEdgeLength + fControlPolygonLength) * 0.5;
            }
            else
            {
                B2DCubicBezier aLeft, aRight;
                const double fNewDeviation(fDeviation * 0.5);
                const sal_uInt32 nNewRecursionWatch(nRecursionWatch - 1);

                rEdge.split(0.5, &aLeft, &aRight);

                return impGetLength(aLeft, fNewDeviation, nNewRecursionWatch)
                    + impGetLength(aRight, fNewDeviation, nNewRecursionWatch);
            }
        }
    }

	double B2DCubicBezier::getLength(double fDeviation) const
    {
        if(isBezier())
        {
            if(fDeviation < 0.00000001)
            {
                fDeviation = 0.00000001;
            }

            return impGetLength(*this, fDeviation, 6);
        }
        else
        {
            return B2DVector(getEndPoint() - getStartPoint()).getLength();
        }
    }

	double B2DCubicBezier::getEdgeLength() const
	{
		const B2DVector aEdge(maEndPoint - maStartPoint);
		return aEdge.getLength();
	}

	double B2DCubicBezier::getControlPolygonLength() const
	{
		const B2DVector aVectorA(maControlPointA - maStartPoint);
		const B2DVector aVectorB(maEndPoint - maControlPointB);

		if(!aVectorA.equalZero() || !aVectorB.equalZero())
		{
			const B2DVector aTop(maControlPointB - maControlPointA);
			return (aVectorA.getLength() + aVectorB.getLength() + aTop.getLength());
		}
		else
		{
			return getEdgeLength();
		}
	}

	void B2DCubicBezier::adaptiveSubdivideByAngle(B2DPolygon& rTarget, double fAngleBound, bool bAllowUnsharpen) const
	{
		if(isBezier())
		{
			// use support method #i37443# and allow unsharpen the criteria
			ImpSubDivAngleStart(maStartPoint, maControlPointA, maControlPointB, maEndPoint, rTarget, fAngleBound * F_PI180, bAllowUnsharpen);
		}
		else
		{
			rTarget.append(getEndPoint());
		}
	}

    B2DVector B2DCubicBezier::getTangent(double t) const
    {
        if(fTools::lessOrEqual(t, 0.0))
        {
            // tangent in start point
            B2DVector aTangent(getControlPointA() - getStartPoint());

            if(!aTangent.equalZero())
            {
                return aTangent;
            }

            // start point and control vector are the same, fallback
            // to implicit start vector to control point B
            aTangent = (getControlPointB() - getStartPoint()) * 0.3;

            if(!aTangent.equalZero())
            {
                return aTangent;
            }

            // not a bezier at all, return edge vector
            return (getEndPoint() - getStartPoint()) * 0.3;
        }
        else if(fTools::moreOrEqual(t, 1.0))
        {
            // tangent in end point
            B2DVector aTangent(getEndPoint() - getControlPointB());

            if(!aTangent.equalZero())
            {
                return aTangent;
            }

            // end point and control vector are the same, fallback
            // to implicit start vector from control point A
            aTangent = (getEndPoint() - getControlPointA()) * 0.3;

            if(!aTangent.equalZero())
            {
                return aTangent;
            }

            // not a bezier at all, return edge vector
            return (getEndPoint() - getStartPoint()) * 0.3;
        }
        else
        {
            // t is in ]0.0 .. 1.0[. Split and extract
            B2DCubicBezier aRight;
            split(t, 0, &aRight);

            return aRight.getControlPointA() - aRight.getStartPoint();
        }
    }

	// #i37443# adaptive subdivide by nCount subdivisions
	void B2DCubicBezier::adaptiveSubdivideByCount(B2DPolygon& rTarget, sal_uInt32 nCount) const
	{
		const double fLenFact(1.0 / static_cast< double >(nCount + 1));

		for(sal_uInt32 a(1); a <= nCount; a++)
		{
			const double fPos(static_cast< double >(a) * fLenFact);
			rTarget.append(interpolatePoint(fPos));
		}

		rTarget.append(getEndPoint());
	}

	// adaptive subdivide by distance
	void B2DCubicBezier::adaptiveSubdivideByDistance(B2DPolygon& rTarget, double fDistanceBound) const
	{
		if(isBezier())
		{
			ImpSubDivDistance(maStartPoint, maControlPointA, maControlPointB, maEndPoint, rTarget,
				fDistanceBound * fDistanceBound, ::std::numeric_limits<double>::max(), 30);
		}
		else
		{
			rTarget.append(getEndPoint());
		}
	}

	B2DPoint B2DCubicBezier::interpolatePoint(double t) const
	{
		OSL_ENSURE(t >= 0.0 && t <= 1.0, "B2DCubicBezier::interpolatePoint: Access out of range (!)");

		if(isBezier())
		{
			const B2DPoint aS1L(interpolate(maStartPoint, maControlPointA, t));
			const B2DPoint aS1C(interpolate(maControlPointA, maControlPointB, t));
			const B2DPoint aS1R(interpolate(maControlPointB, maEndPoint, t));
			const B2DPoint aS2L(interpolate(aS1L, aS1C, t));
			const B2DPoint aS2R(interpolate(aS1C, aS1R, t));

			return interpolate(aS2L, aS2R, t);
		}
		else
		{
			return interpolate(maStartPoint, maEndPoint, t);
		}
	}

	double B2DCubicBezier::getSmallestDistancePointToBezierSegment(const B2DPoint& rTestPoint, double& rCut) const
	{
		const sal_uInt32 nInitialDivisions(3L);
		B2DPolygon aInitialPolygon;

		// as start make a fix division, creates nInitialDivisions + 2L points
		aInitialPolygon.append(getStartPoint());
		adaptiveSubdivideByCount(aInitialPolygon, nInitialDivisions);

		// now look for the closest point
		const sal_uInt32 nPointCount(aInitialPolygon.count());
		B2DVector aVector(rTestPoint - aInitialPolygon.getB2DPoint(0L));
		double fQuadDist(aVector.getX() * aVector.getX() + aVector.getY() * aVector.getY());
		double fNewQuadDist;
		sal_uInt32 nSmallestIndex(0L);

		for(sal_uInt32 a(1L); a < nPointCount; a++)
		{
			aVector = B2DVector(rTestPoint - aInitialPolygon.getB2DPoint(a));
			fNewQuadDist = aVector.getX() * aVector.getX() + aVector.getY() * aVector.getY();

			if(fNewQuadDist < fQuadDist)
			{
				fQuadDist = fNewQuadDist;
				nSmallestIndex = a;
			}
		}

		// look right and left for even smaller distances
		double fStepValue(1.0 / (double)((nPointCount - 1L) * 2L)); // half the edge step width
		double fPosition((double)nSmallestIndex / (double)(nPointCount - 1L));
		bool bDone(false);

		while(!bDone)
		{
			if(!bDone)
			{
				// test left
				double fPosLeft(fPosition - fStepValue);

				if(fPosLeft < 0.0)
				{
					fPosLeft = 0.0;
					aVector = B2DVector(rTestPoint - maStartPoint);
				}
				else
				{
					aVector = B2DVector(rTestPoint - interpolatePoint(fPosLeft));
				}

				fNewQuadDist = aVector.getX() * aVector.getX() + aVector.getY() * aVector.getY();

				if(fTools::less(fNewQuadDist, fQuadDist))
				{
					fQuadDist = fNewQuadDist;
					fPosition = fPosLeft;
				}
				else
				{
					// test right
					double fPosRight(fPosition + fStepValue);

					if(fPosRight > 1.0)
					{
						fPosRight = 1.0;
						aVector = B2DVector(rTestPoint - maEndPoint);
					}
					else
					{
						aVector = B2DVector(rTestPoint - interpolatePoint(fPosRight));
					}

					fNewQuadDist = aVector.getX() * aVector.getX() + aVector.getY() * aVector.getY();

					if(fTools::less(fNewQuadDist, fQuadDist))
					{
						fQuadDist = fNewQuadDist;
						fPosition = fPosRight;
					}
					else
					{
						// not less left or right, done
						bDone = true;
					}
				}
			}

			if(0.0 == fPosition || 1.0 == fPosition)
			{
				// if we are completely left or right, we are done
				bDone = true;
			}

			if(!bDone)
			{
				// prepare next step value
				fStepValue /= 2.0;
			}
		}

		rCut = fPosition;
		return sqrt(fQuadDist);
	}

	void B2DCubicBezier::split(double t, B2DCubicBezier* pBezierA, B2DCubicBezier* pBezierB) const
	{
		OSL_ENSURE(t >= 0.0 && t <= 1.0, "B2DCubicBezier::split: Access out of range (!)");

		if(!pBezierA && !pBezierB)
		{
			return;
		}

		if(isBezier())
		{
			const B2DPoint aS1L(interpolate(maStartPoint, maControlPointA, t));
			const B2DPoint aS1C(interpolate(maControlPointA, maControlPointB, t));
			const B2DPoint aS1R(interpolate(maControlPointB, maEndPoint, t));
			const B2DPoint aS2L(interpolate(aS1L, aS1C, t));
			const B2DPoint aS2R(interpolate(aS1C, aS1R, t));
			const B2DPoint aS3C(interpolate(aS2L, aS2R, t));

			if(pBezierA)
			{
				pBezierA->setStartPoint(maStartPoint);
				pBezierA->setEndPoint(aS3C);
				pBezierA->setControlPointA(aS1L);
				pBezierA->setControlPointB(aS2L);
			}

			if(pBezierB)
			{
				pBezierB->setStartPoint(aS3C);
				pBezierB->setEndPoint(maEndPoint);
				pBezierB->setControlPointA(aS2R);
				pBezierB->setControlPointB(aS1R);
			}
		}
		else
		{
			const B2DPoint aSplit(interpolate(maStartPoint, maEndPoint, t));

			if(pBezierA)
			{
				pBezierA->setStartPoint(maStartPoint);
				pBezierA->setEndPoint(aSplit);
				pBezierA->setControlPointA(maStartPoint);
				pBezierA->setControlPointB(aSplit);
			}

			if(pBezierB)
			{
				pBezierB->setStartPoint(aSplit);
				pBezierB->setEndPoint(maEndPoint);
				pBezierB->setControlPointA(aSplit);
				pBezierB->setControlPointB(maEndPoint);
			}
		}
	}

	B2DCubicBezier B2DCubicBezier::snippet(double fStart, double fEnd) const
	{
		B2DCubicBezier aRetval;

		if(fTools::more(fStart, 1.0))
		{
			fStart = 1.0;
		}
		else if(fTools::less(fStart, 0.0))
		{
			fStart = 0.0;
		}

		if(fTools::more(fEnd, 1.0))
		{
			fEnd = 1.0;
		}
		else if(fTools::less(fEnd, 0.0))
		{
			fEnd = 0.0;
		}

		if(fEnd <= fStart)
		{
			// empty or NULL, create single point at center
			const double fSplit((fEnd + fStart) * 0.5);
			const B2DPoint aPoint(interpolate(getStartPoint(), getEndPoint(), fSplit));
			aRetval.setStartPoint(aPoint);
			aRetval.setEndPoint(aPoint);
			aRetval.setControlPointA(aPoint);
			aRetval.setControlPointB(aPoint);
		}
		else
		{
			if(isBezier())
			{
				// copy bezier; cut off right, then cut off left. Do not forget to
				// adapt cut value when both cuts happen
				const bool bEndIsOne(fTools::equal(fEnd, 1.0));
				const bool bStartIsZero(fTools::equalZero(fStart));
				aRetval = *this;

				if(!bEndIsOne)
				{
					aRetval.split(fEnd, &aRetval, 0);

					if(!bStartIsZero)
					{
						fStart /= fEnd;
					}
				}

				if(!bStartIsZero)
				{
					aRetval.split(fStart, 0, &aRetval);
				}
			}
			else
			{
				// no bezier, create simple edge
				const B2DPoint aPointA(interpolate(getStartPoint(), getEndPoint(), fStart));
				const B2DPoint aPointB(interpolate(getStartPoint(), getEndPoint(), fEnd));
				aRetval.setStartPoint(aPointA);
				aRetval.setEndPoint(aPointB);
				aRetval.setControlPointA(aPointA);
				aRetval.setControlPointB(aPointB);
			}
		}

		return aRetval;
	}

	B2DRange B2DCubicBezier::getRange() const
	{
		B2DRange aRetval(maStartPoint, maEndPoint);

		aRetval.expand(maControlPointA);
		aRetval.expand(maControlPointB);

		return aRetval;
	}

	bool B2DCubicBezier::getMinimumExtremumPosition(double& rfResult) const
	{
		::std::vector< double > aAllResults;

		aAllResults.reserve(4);
		getAllExtremumPositions(aAllResults);

		const sal_uInt32 nCount(aAllResults.size());

		if(!nCount)
		{
			return false;
		}
		else if(1 == nCount)
		{
			rfResult = aAllResults[0];
			return true;
		}
		else
		{
			rfResult = *(::std::min_element(aAllResults.begin(), aAllResults.end()));
			return true;
		}
	}

	namespace
	{
		inline void impCheckExtremumResult(double fCandidate, ::std::vector< double >& rResult)
		{
            // check for range ]0.0 .. 1.0[ with excluding 1.0 and 0.0 clearly
            // by using the equalZero test, NOT ::more or ::less which will use the
            // ApproxEqual() which is too exact here
            if(fCandidate > 0.0 && !fTools::equalZero(fCandidate))
            {
                if(fCandidate < 1.0 && !fTools::equalZero(fCandidate - 1.0))
                {
    				rResult.push_back(fCandidate);
                }
			}
		}
	}

	void B2DCubicBezier::getAllExtremumPositions(::std::vector< double >& rResults) const
	{
		rResults.clear();

		// calculate the x-extrema parameters by zeroing first x-derivative
		// of the cubic bezier's parametric formula, which results in a
		// quadratic equation: dBezier/dt = t*t*fAX - 2*t*fBX + fCX
		const B2DPoint aControlDiff( maControlPointA - maControlPointB );
		double fCX = maControlPointA.getX() - maStartPoint.getX();
		const double fBX = fCX + aControlDiff.getX();
		const double fAX = 3 * aControlDiff.getX() + (maEndPoint.getX() - maStartPoint.getX());

		if(fTools::equalZero(fCX))
		{
			// detect fCX equal zero and truncate to real zero value in that case
			fCX = 0.0;
		}

		if( !fTools::equalZero(fAX) )
		{
			// derivative is polynomial of order 2 => use binomial formula
			const double fD = fBX*fBX - fAX*fCX;
			if( fD >= 0.0 )
			{
				const double fS = sqrt(fD);
				// calculate both roots (avoiding a numerically unstable subtraction)
				const double fQ = fBX + ((fBX >= 0) ? +fS : -fS);
				impCheckExtremumResult(fQ / fAX, rResults);
				if( !fTools::equalZero(fS) ) // ignore root multiplicity
					impCheckExtremumResult(fCX / fQ, rResults);
			}
		}
		else if( !fTools::equalZero(fBX) )
		{
			// derivative is polynomial of order 1 => one extrema
			impCheckExtremumResult(fCX / (2 * fBX), rResults);
		}

		// calculate the y-extrema parameters by zeroing first y-derivative
		double fCY = maControlPointA.getY() - maStartPoint.getY();
		const double fBY = fCY + aControlDiff.getY();
		const double fAY = 3 * aControlDiff.getY() + (maEndPoint.getY() - maStartPoint.getY());

		if(fTools::equalZero(fCY))
		{
			// detect fCY equal zero and truncate to real zero value in that case
			fCY = 0.0;
		}

		if( !fTools::equalZero(fAY) )
		{
			// derivative is polynomial of order 2 => use binomial formula
			const double fD = fBY*fBY - fAY*fCY;
			if( fD >= 0.0 )
			{
				const double fS = sqrt(fD);
				// calculate both roots (avoiding a numerically unstable subtraction)
				const double fQ = fBY + ((fBY >= 0) ? +fS : -fS);
				impCheckExtremumResult(fQ / fAY, rResults);
				if( !fTools::equalZero(fS) ) // ignore root multiplicity
					impCheckExtremumResult(fCY / fQ, rResults);
			}
		}
		else if( !fTools::equalZero(fBY) )
		{
			// derivative is polynomial of order 1 => one extrema
			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)-STARTy,-BEZIERx(t)-STARTx)
		// 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 * (maControlPointA.getX() - maControlPointB.getX()) + aRelativeEndPoint.getX()) * aRelativeEndPoint.getY()
				- (3 * (maControlPointA.getY() - maControlPointB.getY()) + aRelativeEndPoint.getY()) * aRelativeEndPoint.getX();
		const double fB = (maControlPointB.getX() - 2 * maControlPointA.getX() + maStartPoint.getX()) * aRelativeEndPoint.getY()
				- (maControlPointB.getY() - 2 * maControlPointA.getY() + maStartPoint.getY()) * aRelativeEndPoint.getX();
		const double fC = (maControlPointA.getX() - maStartPoint.getX()) * aRelativeEndPoint.getY()
				- (maControlPointA.getY() - maStartPoint.getY()) * aRelativeEndPoint.getX();

		// test for degenerated case: order<2
		if( fTools::equalZero(fA) )
		{
			// test for degenerated case: order==0
			if( fTools::equalZero(fB) )
				return 0;

			// solving the order==1 polynomial is trivial
			pResult[0] = -fC / (2*fB);

			// test root and 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 first root (avoiding a numerically unstable subtraction)
			const double fS = sqrt(fD);
			const double fQ = -(fB + ((fB >= 0) ? +fS : -fS));
			pResult[0] = fQ / fA;
			// ignore root when it is outside the curve
			static const double fEps = 1e-9;
			int nCount = ((pResult[0] > fEps) && (pResult[0] < fEps));

			// ignore root multiplicity
			if( !fTools::equalZero(fD) )
			{
 				// calculate the other root
				const double fRoot = fC / fQ;
				// ignore root when it is outside the curve
				if( (fRoot > fEps) && (fRoot < 1.0-fEps) )
					pResult[ nCount++ ] = fRoot;
			}

			return nCount;
		}

		return 0;
	}

} // end of namespace basegfx

// eof