diff options
Diffstat (limited to 'basegfx/source/polygon/b2dpolygontools.cxx')
-rw-r--r-- | basegfx/source/polygon/b2dpolygontools.cxx | 3594 |
1 files changed, 3594 insertions, 0 deletions
diff --git a/basegfx/source/polygon/b2dpolygontools.cxx b/basegfx/source/polygon/b2dpolygontools.cxx new file mode 100644 index 000000000000..28e5bb1f430d --- /dev/null +++ b/basegfx/source/polygon/b2dpolygontools.cxx @@ -0,0 +1,3594 @@ +/************************************************************************* + * + * 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/numeric/ftools.hxx> +#include <basegfx/polygon/b2dpolygontools.hxx> +#include <osl/diagnose.h> +#include <rtl/math.hxx> +#include <basegfx/polygon/b2dpolygon.hxx> +#include <basegfx/polygon/b2dpolypolygon.hxx> +#include <basegfx/range/b2drange.hxx> +#include <basegfx/curve/b2dcubicbezier.hxx> +#include <basegfx/polygon/b2dpolypolygoncutter.hxx> +#include <basegfx/point/b3dpoint.hxx> +#include <basegfx/matrix/b3dhommatrix.hxx> +#include <basegfx/matrix/b2dhommatrix.hxx> +#include <basegfx/curve/b2dbeziertools.hxx> +#include <basegfx/matrix/b2dhommatrixtools.hxx> +#include <osl/mutex.hxx> + +#include <numeric> +#include <limits> + +// #i37443# +#define ANGLE_BOUND_START_VALUE (2.25) +#define ANGLE_BOUND_MINIMUM_VALUE (0.1) +#define COUNT_SUBDIVIDE_DEFAULT (4L) +#ifdef DBG_UTIL +static double fAngleBoundStartValue = ANGLE_BOUND_START_VALUE; +#endif +#define STEPSPERQUARTER (3) + +////////////////////////////////////////////////////////////////////////////// + +namespace basegfx +{ + namespace tools + { + void openWithGeometryChange(B2DPolygon& rCandidate) + { + if(rCandidate.isClosed()) + { + if(rCandidate.count()) + { + rCandidate.append(rCandidate.getB2DPoint(0)); + + if(rCandidate.areControlPointsUsed() && rCandidate.isPrevControlPointUsed(0)) + { + rCandidate.setPrevControlPoint(rCandidate.count() - 1, rCandidate.getPrevControlPoint(0)); + rCandidate.resetPrevControlPoint(0); + } + } + + rCandidate.setClosed(false); + } + } + + void closeWithGeometryChange(B2DPolygon& rCandidate) + { + if(!rCandidate.isClosed()) + { + while(rCandidate.count() > 1 && rCandidate.getB2DPoint(0) == rCandidate.getB2DPoint(rCandidate.count() - 1)) + { + if(rCandidate.areControlPointsUsed() && rCandidate.isPrevControlPointUsed(rCandidate.count() - 1)) + { + rCandidate.setPrevControlPoint(0, rCandidate.getPrevControlPoint(rCandidate.count() - 1)); + } + + rCandidate.remove(rCandidate.count() - 1); + } + + rCandidate.setClosed(true); + } + } + + void checkClosed(B2DPolygon& rCandidate) + { + // #i80172# Removed unnecessary assertion + // OSL_ENSURE(!rCandidate.isClosed(), "checkClosed: already closed (!)"); + + if(rCandidate.count() > 1 && rCandidate.getB2DPoint(0) == rCandidate.getB2DPoint(rCandidate.count() - 1)) + { + closeWithGeometryChange(rCandidate); + } + } + + // Get successor and predecessor indices. Returning the same index means there + // is none. Same for successor. + sal_uInt32 getIndexOfPredecessor(sal_uInt32 nIndex, const B2DPolygon& rCandidate) + { + OSL_ENSURE(nIndex < rCandidate.count(), "getIndexOfPredecessor: Access to polygon out of range (!)"); + + if(nIndex) + { + return nIndex - 1L; + } + else if(rCandidate.count()) + { + return rCandidate.count() - 1L; + } + else + { + return nIndex; + } + } + + sal_uInt32 getIndexOfSuccessor(sal_uInt32 nIndex, const B2DPolygon& rCandidate) + { + OSL_ENSURE(nIndex < rCandidate.count(), "getIndexOfPredecessor: Access to polygon out of range (!)"); + + if(nIndex + 1L < rCandidate.count()) + { + return nIndex + 1L; + } + else if(nIndex + 1L == rCandidate.count()) + { + return 0L; + } + else + { + return nIndex; + } + } + + B2VectorOrientation getOrientation(const B2DPolygon& rCandidate) + { + B2VectorOrientation eRetval(ORIENTATION_NEUTRAL); + + if(rCandidate.count() > 2L || rCandidate.areControlPointsUsed()) + { + const double fSignedArea(getSignedArea(rCandidate)); + + if(fTools::equalZero(fSignedArea)) + { + // ORIENTATION_NEUTRAL, already set + } + if(fSignedArea > 0.0) + { + eRetval = ORIENTATION_POSITIVE; + } + else if(fSignedArea < 0.0) + { + eRetval = ORIENTATION_NEGATIVE; + } + } + + return eRetval; + } + + B2VectorContinuity getContinuityInPoint(const B2DPolygon& rCandidate, sal_uInt32 nIndex) + { + return rCandidate.getContinuityInPoint(nIndex); + } + + B2DPolygon adaptiveSubdivideByDistance(const B2DPolygon& rCandidate, double fDistanceBound) + { + if(rCandidate.areControlPointsUsed()) + { + const sal_uInt32 nPointCount(rCandidate.count()); + B2DPolygon aRetval; + + if(nPointCount) + { + // prepare edge-oriented loop + const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1); + 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()); + + for(sal_uInt32 a(0L); a < nEdgeCount; a++) + { + // get next and control points + const sal_uInt32 nNextIndex((a + 1) % nPointCount); + aBezier.setEndPoint(rCandidate.getB2DPoint(nNextIndex)); + aBezier.setControlPointA(rCandidate.getNextControlPoint(a)); + aBezier.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex)); + aBezier.testAndSolveTrivialBezier(); + + if(aBezier.isBezier()) + { + // add curved edge and generate DistanceBound + double fBound(0.0); + + if(0.0 == fDistanceBound) + { + // If not set, use B2DCubicBezier functionality to guess a rough value + const double fRoughLength((aBezier.getEdgeLength() + aBezier.getControlPolygonLength()) / 2.0); + + // take 1/100th of the rough curve length + fBound = fRoughLength * 0.01; + } + else + { + // use given bound value + fBound = fDistanceBound; + } + + // make sure bound value is not too small. The base units are 1/100th mm, thus + // just make sure it's not smaller then 1/100th of that + if(fBound < 0.01) + { + fBound = 0.01; + } + + // call adaptive subdivide which adds edges to aRetval accordingly + aBezier.adaptiveSubdivideByDistance(aRetval, fBound); + } + else + { + // add non-curved edge + aRetval.append(aBezier.getEndPoint()); + } + + // prepare next step + aBezier.setStartPoint(aBezier.getEndPoint()); + } + + if(rCandidate.isClosed()) + { + // set closed flag and correct last point (which is added double now). + closeWithGeometryChange(aRetval); + } + } + + return aRetval; + } + else + { + return rCandidate; + } + } + + B2DPolygon adaptiveSubdivideByAngle(const B2DPolygon& rCandidate, double fAngleBound) + { + if(rCandidate.areControlPointsUsed()) + { + const sal_uInt32 nPointCount(rCandidate.count()); + B2DPolygon aRetval; + + if(nPointCount) + { + // prepare edge-oriented loop + const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1); + 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()); + + // #i37443# prepare convenient AngleBound if none was given + if(0.0 == fAngleBound) + { +#ifdef DBG_UTIL + fAngleBound = fAngleBoundStartValue; +#else + fAngleBound = ANGLE_BOUND_START_VALUE; +#endif + } + else if(fTools::less(fAngleBound, ANGLE_BOUND_MINIMUM_VALUE)) + { + fAngleBound = 0.1; + } + + for(sal_uInt32 a(0L); a < nEdgeCount; a++) + { + // get next and control points + const sal_uInt32 nNextIndex((a + 1) % nPointCount); + aBezier.setEndPoint(rCandidate.getB2DPoint(nNextIndex)); + aBezier.setControlPointA(rCandidate.getNextControlPoint(a)); + aBezier.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex)); + aBezier.testAndSolveTrivialBezier(); + + if(aBezier.isBezier()) + { + // call adaptive subdivide + aBezier.adaptiveSubdivideByAngle(aRetval, fAngleBound, true); + } + else + { + // add non-curved edge + aRetval.append(aBezier.getEndPoint()); + } + + // prepare next step + aBezier.setStartPoint(aBezier.getEndPoint()); + } + + if(rCandidate.isClosed()) + { + // set closed flag and correct last point (which is added double now). + closeWithGeometryChange(aRetval); + } + } + + return aRetval; + } + else + { + return rCandidate; + } + } + + B2DPolygon adaptiveSubdivideByCount(const B2DPolygon& rCandidate, sal_uInt32 nCount) + { + if(rCandidate.areControlPointsUsed()) + { + const sal_uInt32 nPointCount(rCandidate.count()); + B2DPolygon aRetval; + + if(nPointCount) + { + // prepare edge-oriented loop + const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1); + 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()); + + // #i37443# prepare convenient count if none was given + if(0L == nCount) + { + nCount = COUNT_SUBDIVIDE_DEFAULT; + } + + for(sal_uInt32 a(0L); a < nEdgeCount; a++) + { + // get next and control points + const sal_uInt32 nNextIndex((a + 1) % nPointCount); + aBezier.setEndPoint(rCandidate.getB2DPoint(nNextIndex)); + aBezier.setControlPointA(rCandidate.getNextControlPoint(a)); + aBezier.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex)); + aBezier.testAndSolveTrivialBezier(); + + if(aBezier.isBezier()) + { + // call adaptive subdivide + aBezier.adaptiveSubdivideByCount(aRetval, nCount); + } + else + { + // add non-curved edge + aRetval.append(aBezier.getEndPoint()); + } + + // prepare next step + aBezier.setStartPoint(aBezier.getEndPoint()); + } + + if(rCandidate.isClosed()) + { + // set closed flag and correct last point (which is added double now). + closeWithGeometryChange(aRetval); + } + } + + return aRetval; + } + else + { + return rCandidate; + } + } + + bool isInside(const B2DPolygon& rCandidate, const B2DPoint& rPoint, bool bWithBorder) + { + const B2DPolygon aCandidate(rCandidate.areControlPointsUsed() ? rCandidate.getDefaultAdaptiveSubdivision() : rCandidate); + + if(bWithBorder && isPointOnPolygon(aCandidate, rPoint, true)) + { + return true; + } + else + { + bool bRetval(false); + const sal_uInt32 nPointCount(aCandidate.count()); + + if(nPointCount) + { + B2DPoint aCurrentPoint(aCandidate.getB2DPoint(nPointCount - 1L)); + + for(sal_uInt32 a(0L); a < nPointCount; a++) + { + const B2DPoint aPreviousPoint(aCurrentPoint); + aCurrentPoint = aCandidate.getB2DPoint(a); + + // cross-over in Y? + const bool bCompYA(fTools::more(aPreviousPoint.getY(), rPoint.getY())); + const bool bCompYB(fTools::more(aCurrentPoint.getY(), rPoint.getY())); + + if(bCompYA != bCompYB) + { + // cross-over in X? + const bool bCompXA(fTools::more(aPreviousPoint.getX(), rPoint.getX())); + const bool bCompXB(fTools::more(aCurrentPoint.getX(), rPoint.getX())); + + if(bCompXA == bCompXB) + { + if(bCompXA) + { + bRetval = !bRetval; + } + } + else + { + const double fCompare( + aCurrentPoint.getX() - (aCurrentPoint.getY() - rPoint.getY()) * + (aPreviousPoint.getX() - aCurrentPoint.getX()) / + (aPreviousPoint.getY() - aCurrentPoint.getY())); + + if(fTools::more(fCompare, rPoint.getX())) + { + bRetval = !bRetval; + } + } + } + } + } + + return bRetval; + } + } + + bool isInside(const B2DPolygon& rCandidate, const B2DPolygon& rPolygon, bool bWithBorder) + { + const B2DPolygon aCandidate(rCandidate.areControlPointsUsed() ? rCandidate.getDefaultAdaptiveSubdivision() : rCandidate); + const B2DPolygon aPolygon(rPolygon.areControlPointsUsed() ? rPolygon.getDefaultAdaptiveSubdivision() : rPolygon); + const sal_uInt32 nPointCount(aPolygon.count()); + + for(sal_uInt32 a(0L); a < nPointCount; a++) + { + const B2DPoint aTestPoint(aPolygon.getB2DPoint(a)); + + if(!isInside(aCandidate, aTestPoint, bWithBorder)) + { + return false; + } + } + + return true; + } + + B2DRange getRangeWithControlPoints(const B2DPolygon& rCandidate) + { + const sal_uInt32 nPointCount(rCandidate.count()); + B2DRange aRetval; + + if(nPointCount) + { + const bool bControlPointsUsed(rCandidate.areControlPointsUsed()); + + for(sal_uInt32 a(0); a < nPointCount; a++) + { + aRetval.expand(rCandidate.getB2DPoint(a)); + + if(bControlPointsUsed) + { + aRetval.expand(rCandidate.getNextControlPoint(a)); + aRetval.expand(rCandidate.getPrevControlPoint(a)); + } + } + } + + return aRetval; + } + + B2DRange getRange(const B2DPolygon& rCandidate) + { + // changed to use internally buffered version at B2DPolygon + return rCandidate.getB2DRange(); + } + + double getSignedArea(const B2DPolygon& rCandidate) + { + const B2DPolygon aCandidate(rCandidate.areControlPointsUsed() ? rCandidate.getDefaultAdaptiveSubdivision() : rCandidate); + double fRetval(0.0); + const sal_uInt32 nPointCount(aCandidate.count()); + + if(nPointCount > 2) + { + for(sal_uInt32 a(0L); a < nPointCount; a++) + { + const B2DPoint aPreviousPoint(aCandidate.getB2DPoint((!a) ? nPointCount - 1L : a - 1L)); + const B2DPoint aCurrentPoint(aCandidate.getB2DPoint(a)); + + fRetval += aPreviousPoint.getX() * aCurrentPoint.getY(); + fRetval -= aPreviousPoint.getY() * aCurrentPoint.getX(); + } + + fRetval /= 2.0; + + // correct to zero if small enough. Also test the quadratic + // of the result since the precision is near quadratic due to + // the algorithm + if(fTools::equalZero(fRetval) || fTools::equalZero(fRetval * fRetval)) + { + fRetval = 0.0; + } + } + + return fRetval; + } + + double getArea(const B2DPolygon& rCandidate) + { + double fRetval(0.0); + + if(rCandidate.count() > 2 || rCandidate.areControlPointsUsed()) + { + fRetval = getSignedArea(rCandidate); + const double fZero(0.0); + + if(fTools::less(fRetval, fZero)) + { + fRetval = -fRetval; + } + } + + return fRetval; + } + + double getEdgeLength(const B2DPolygon& rCandidate, sal_uInt32 nIndex) + { + const sal_uInt32 nPointCount(rCandidate.count()); + OSL_ENSURE(nIndex < nPointCount, "getEdgeLength: Access to polygon out of range (!)"); + double fRetval(0.0); + + if(nPointCount) + { + const sal_uInt32 nNextIndex((nIndex + 1) % nPointCount); + + if(rCandidate.areControlPointsUsed()) + { + B2DCubicBezier aEdge; + + aEdge.setStartPoint(rCandidate.getB2DPoint(nIndex)); + aEdge.setControlPointA(rCandidate.getNextControlPoint(nIndex)); + aEdge.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex)); + aEdge.setEndPoint(rCandidate.getB2DPoint(nNextIndex)); + + fRetval = aEdge.getLength(); + } + else + { + const B2DPoint aCurrent(rCandidate.getB2DPoint(nIndex)); + const B2DPoint aNext(rCandidate.getB2DPoint(nNextIndex)); + + fRetval = B2DVector(aNext - aCurrent).getLength(); + } + } + + return fRetval; + } + + double getLength(const B2DPolygon& rCandidate) + { + double fRetval(0.0); + const sal_uInt32 nPointCount(rCandidate.count()); + + if(nPointCount) + { + const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1L); + + if(rCandidate.areControlPointsUsed()) + { + B2DCubicBezier aEdge; + aEdge.setStartPoint(rCandidate.getB2DPoint(0)); + + for(sal_uInt32 a(0); a < nEdgeCount; a++) + { + const sal_uInt32 nNextIndex((a + 1) % nPointCount); + aEdge.setControlPointA(rCandidate.getNextControlPoint(a)); + aEdge.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex)); + aEdge.setEndPoint(rCandidate.getB2DPoint(nNextIndex)); + + fRetval += aEdge.getLength(); + aEdge.setStartPoint(aEdge.getEndPoint()); + } + } + else + { + B2DPoint aCurrent(rCandidate.getB2DPoint(0)); + + for(sal_uInt32 a(0); a < nEdgeCount; a++) + { + const sal_uInt32 nNextIndex((a + 1) % nPointCount); + const B2DPoint aNext(rCandidate.getB2DPoint(nNextIndex)); + + fRetval += B2DVector(aNext - aCurrent).getLength(); + aCurrent = aNext; + } + } + } + + return fRetval; + } + + B2DPoint getPositionAbsolute(const B2DPolygon& rCandidate, double fDistance, double fLength) + { + B2DPoint aRetval; + const sal_uInt32 nPointCount(rCandidate.count()); + + if( 1L == nPointCount ) + { + // only one point (i.e. no edge) - simply take that point + aRetval = rCandidate.getB2DPoint(0); + } + else if(nPointCount > 1L) + { + const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1); + sal_uInt32 nIndex(0L); + bool bIndexDone(false); + + // get length if not given + if(fTools::equalZero(fLength)) + { + fLength = getLength(rCandidate); + } + + if(fTools::less(fDistance, 0.0)) + { + // handle fDistance < 0.0 + if(rCandidate.isClosed()) + { + // if fDistance < 0.0 increment with multiple of fLength + sal_uInt32 nCount(sal_uInt32(-fDistance / fLength)); + fDistance += double(nCount + 1L) * fLength; + } + else + { + // crop to polygon start + fDistance = 0.0; + bIndexDone = true; + } + } + else if(fTools::moreOrEqual(fDistance, fLength)) + { + // handle fDistance >= fLength + if(rCandidate.isClosed()) + { + // if fDistance >= fLength decrement with multiple of fLength + sal_uInt32 nCount(sal_uInt32(fDistance / fLength)); + fDistance -= (double)(nCount) * fLength; + } + else + { + // crop to polygon end + fDistance = 0.0; + nIndex = nEdgeCount; + bIndexDone = true; + } + } + + // look for correct index. fDistance is now [0.0 .. fLength[ + double fEdgeLength(getEdgeLength(rCandidate, nIndex)); + + while(!bIndexDone) + { + // edge found must be on the half-open range + // [0,fEdgeLength). + // Note that in theory, we cannot move beyond + // the last polygon point, since fDistance>=fLength + // is checked above. Unfortunately, with floating- + // point calculations, this case might happen. + // Handled by nIndex check below + if(nIndex < nEdgeCount && fTools::moreOrEqual(fDistance, fEdgeLength)) + { + // go to next edge + fDistance -= fEdgeLength; + fEdgeLength = getEdgeLength(rCandidate, ++nIndex); + } + else + { + // it's on this edge, stop + bIndexDone = true; + } + } + + // get the point using nIndex + aRetval = rCandidate.getB2DPoint(nIndex); + + // if fDistance != 0.0, move that length on the edge. The edge + // length is in fEdgeLength. + if(!fTools::equalZero(fDistance)) + { + if(fTools::moreOrEqual(fDistance, fEdgeLength)) + { + // end point of choosen edge + const sal_uInt32 nNextIndex((nIndex + 1) % nPointCount); + aRetval = rCandidate.getB2DPoint(nNextIndex); + } + else if(fTools::equalZero(fDistance)) + { + // start point of choosen edge + aRetval = aRetval; + } + else + { + // inside edge + const sal_uInt32 nNextIndex((nIndex + 1) % nPointCount); + const B2DPoint aNextPoint(rCandidate.getB2DPoint(nNextIndex)); + bool bDone(false); + + // add calculated average value to the return value + if(rCandidate.areControlPointsUsed()) + { + // get as bezier segment + const B2DCubicBezier aBezierSegment( + aRetval, rCandidate.getNextControlPoint(nIndex), + rCandidate.getPrevControlPoint(nNextIndex), aNextPoint); + + if(aBezierSegment.isBezier()) + { + // use B2DCubicBezierHelper to bridge the non-linear gap between + // length and bezier distances + const B2DCubicBezierHelper aBezierSegmentHelper(aBezierSegment); + const double fBezierDistance(aBezierSegmentHelper.distanceToRelative(fDistance)); + + aRetval = aBezierSegment.interpolatePoint(fBezierDistance); + bDone = true; + } + } + + if(!bDone) + { + const double fRelativeInEdge(fDistance / fEdgeLength); + aRetval = interpolate(aRetval, aNextPoint, fRelativeInEdge); + } + } + } + } + + return aRetval; + } + + B2DPoint getPositionRelative(const B2DPolygon& rCandidate, double fDistance, double fLength) + { + // get length if not given + if(fTools::equalZero(fLength)) + { + fLength = getLength(rCandidate); + } + + // multiply fDistance with real length to get absolute position and + // use getPositionAbsolute + return getPositionAbsolute(rCandidate, fDistance * fLength, fLength); + } + + B2DPolygon getSnippetAbsolute(const B2DPolygon& rCandidate, double fFrom, double fTo, double fLength) + { + const sal_uInt32 nPointCount(rCandidate.count()); + + if(nPointCount) + { + // get length if not given + if(fTools::equalZero(fLength)) + { + fLength = getLength(rCandidate); + } + + // test and correct fFrom + if(fTools::less(fFrom, 0.0)) + { + fFrom = 0.0; + } + + // test and correct fTo + if(fTools::more(fTo, fLength)) + { + fTo = fLength; + } + + // test and correct relationship of fFrom, fTo + if(fTools::more(fFrom, fTo)) + { + fFrom = fTo = (fFrom + fTo) / 2.0; + } + + if(fTools::equalZero(fFrom) && fTools::equal(fTo, fLength)) + { + // no change, result is the whole polygon + return rCandidate; + } + else + { + B2DPolygon aRetval; + const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1); + double fPositionOfStart(0.0); + bool bStartDone(false); + bool bEndDone(false); + + for(sal_uInt32 a(0L); !(bStartDone && bEndDone) && a < nEdgeCount; a++) + { + const double fEdgeLength(getEdgeLength(rCandidate, a)); + + if(!bStartDone) + { + if(fTools::equalZero(fFrom)) + { + aRetval.append(rCandidate.getB2DPoint(a)); + + if(rCandidate.areControlPointsUsed()) + { + aRetval.setNextControlPoint(aRetval.count() - 1, rCandidate.getNextControlPoint(a)); + } + + bStartDone = true; + } + else if(fTools::moreOrEqual(fFrom, fPositionOfStart) && fTools::less(fFrom, fPositionOfStart + fEdgeLength)) + { + // calculate and add start point + if(fTools::equalZero(fEdgeLength)) + { + aRetval.append(rCandidate.getB2DPoint(a)); + + if(rCandidate.areControlPointsUsed()) + { + aRetval.setNextControlPoint(aRetval.count() - 1, rCandidate.getNextControlPoint(a)); + } + } + else + { + const sal_uInt32 nNextIndex((a + 1) % nPointCount); + const B2DPoint aStart(rCandidate.getB2DPoint(a)); + const B2DPoint aEnd(rCandidate.getB2DPoint(nNextIndex)); + bool bDone(false); + + if(rCandidate.areControlPointsUsed()) + { + const B2DCubicBezier aBezierSegment( + aStart, rCandidate.getNextControlPoint(a), + rCandidate.getPrevControlPoint(nNextIndex), aEnd); + + if(aBezierSegment.isBezier()) + { + // use B2DCubicBezierHelper to bridge the non-linear gap between + // length and bezier distances + const B2DCubicBezierHelper aBezierSegmentHelper(aBezierSegment); + const double fBezierDistance(aBezierSegmentHelper.distanceToRelative(fFrom - fPositionOfStart)); + B2DCubicBezier aRight; + + aBezierSegment.split(fBezierDistance, 0, &aRight); + aRetval.append(aRight.getStartPoint()); + aRetval.setNextControlPoint(aRetval.count() - 1, aRight.getControlPointA()); + bDone = true; + } + } + + if(!bDone) + { + const double fRelValue((fFrom - fPositionOfStart) / fEdgeLength); + aRetval.append(interpolate(aStart, aEnd, fRelValue)); + } + } + + bStartDone = true; + + // if same point, end is done, too. + if(fFrom == fTo) + { + bEndDone = true; + } + } + } + + if(!bEndDone && fTools::moreOrEqual(fTo, fPositionOfStart) && fTools::less(fTo, fPositionOfStart + fEdgeLength)) + { + // calculate and add end point + if(fTools::equalZero(fEdgeLength)) + { + const sal_uInt32 nNextIndex((a + 1) % nPointCount); + aRetval.append(rCandidate.getB2DPoint(nNextIndex)); + + if(rCandidate.areControlPointsUsed()) + { + aRetval.setPrevControlPoint(aRetval.count() - 1, rCandidate.getPrevControlPoint(nNextIndex)); + } + } + else + { + const sal_uInt32 nNextIndex((a + 1) % nPointCount); + const B2DPoint aStart(rCandidate.getB2DPoint(a)); + const B2DPoint aEnd(rCandidate.getB2DPoint(nNextIndex)); + bool bDone(false); + + if(rCandidate.areControlPointsUsed()) + { + const B2DCubicBezier aBezierSegment( + aStart, rCandidate.getNextControlPoint(a), + rCandidate.getPrevControlPoint(nNextIndex), aEnd); + + if(aBezierSegment.isBezier()) + { + // use B2DCubicBezierHelper to bridge the non-linear gap between + // length and bezier distances + const B2DCubicBezierHelper aBezierSegmentHelper(aBezierSegment); + const double fBezierDistance(aBezierSegmentHelper.distanceToRelative(fTo - fPositionOfStart)); + B2DCubicBezier aLeft; + + aBezierSegment.split(fBezierDistance, &aLeft, 0); + aRetval.append(aLeft.getEndPoint()); + aRetval.setPrevControlPoint(aRetval.count() - 1, aLeft.getControlPointB()); + bDone = true; + } + } + + if(!bDone) + { + const double fRelValue((fTo - fPositionOfStart) / fEdgeLength); + aRetval.append(interpolate(aStart, aEnd, fRelValue)); + } + } + + bEndDone = true; + } + + if(!bEndDone) + { + if(bStartDone) + { + // add segments end point + const sal_uInt32 nNextIndex((a + 1) % nPointCount); + aRetval.append(rCandidate.getB2DPoint(nNextIndex)); + + if(rCandidate.areControlPointsUsed()) + { + aRetval.setPrevControlPoint(aRetval.count() - 1, rCandidate.getPrevControlPoint(nNextIndex)); + aRetval.setNextControlPoint(aRetval.count() - 1, rCandidate.getNextControlPoint(nNextIndex)); + } + } + + // increment fPositionOfStart + fPositionOfStart += fEdgeLength; + } + } + return aRetval; + } + } + else + { + return rCandidate; + } + } + + B2DPolygon getSnippetRelative(const B2DPolygon& rCandidate, double fFrom, double fTo, double fLength) + { + // get length if not given + if(fTools::equalZero(fLength)) + { + fLength = getLength(rCandidate); + } + + // multiply distances with real length to get absolute position and + // use getSnippetAbsolute + return getSnippetAbsolute(rCandidate, fFrom * fLength, fTo * fLength, fLength); + } + + CutFlagValue findCut( + const B2DPolygon& rCandidate, + sal_uInt32 nIndex1, sal_uInt32 nIndex2, + CutFlagValue aCutFlags, + double* pCut1, double* pCut2) + { + CutFlagValue aRetval(CUTFLAG_NONE); + const sal_uInt32 nPointCount(rCandidate.count()); + + if(nIndex1 < nPointCount && nIndex2 < nPointCount && nIndex1 != nIndex2) + { + sal_uInt32 nEnd1(getIndexOfSuccessor(nIndex1, rCandidate)); + sal_uInt32 nEnd2(getIndexOfSuccessor(nIndex2, rCandidate)); + + const B2DPoint aStart1(rCandidate.getB2DPoint(nIndex1)); + const B2DPoint aEnd1(rCandidate.getB2DPoint(nEnd1)); + const B2DVector aVector1(aEnd1 - aStart1); + + const B2DPoint aStart2(rCandidate.getB2DPoint(nIndex2)); + const B2DPoint aEnd2(rCandidate.getB2DPoint(nEnd2)); + const B2DVector aVector2(aEnd2 - aStart2); + + aRetval = findCut( + aStart1, aVector1, aStart2, aVector2, + aCutFlags, pCut1, pCut2); + } + + return aRetval; + } + + CutFlagValue findCut( + const B2DPolygon& rCandidate1, sal_uInt32 nIndex1, + const B2DPolygon& rCandidate2, sal_uInt32 nIndex2, + CutFlagValue aCutFlags, + double* pCut1, double* pCut2) + { + CutFlagValue aRetval(CUTFLAG_NONE); + const sal_uInt32 nPointCount1(rCandidate1.count()); + const sal_uInt32 nPointCount2(rCandidate2.count()); + + if(nIndex1 < nPointCount1 && nIndex2 < nPointCount2) + { + sal_uInt32 nEnd1(getIndexOfSuccessor(nIndex1, rCandidate1)); + sal_uInt32 nEnd2(getIndexOfSuccessor(nIndex2, rCandidate2)); + + const B2DPoint aStart1(rCandidate1.getB2DPoint(nIndex1)); + const B2DPoint aEnd1(rCandidate1.getB2DPoint(nEnd1)); + const B2DVector aVector1(aEnd1 - aStart1); + + const B2DPoint aStart2(rCandidate2.getB2DPoint(nIndex2)); + const B2DPoint aEnd2(rCandidate2.getB2DPoint(nEnd2)); + const B2DVector aVector2(aEnd2 - aStart2); + + aRetval = findCut( + aStart1, aVector1, aStart2, aVector2, + aCutFlags, pCut1, pCut2); + } + + return aRetval; + } + + CutFlagValue findCut( + const B2DPoint& rEdge1Start, const B2DVector& rEdge1Delta, + const B2DPoint& rEdge2Start, const B2DVector& rEdge2Delta, + CutFlagValue aCutFlags, + double* pCut1, double* pCut2) + { + CutFlagValue aRetval(CUTFLAG_NONE); + double fCut1(0.0); + double fCut2(0.0); + bool bFinished(!((bool)(aCutFlags & CUTFLAG_ALL))); + + // test for same points? + if(!bFinished + && (aCutFlags & (CUTFLAG_START1|CUTFLAG_END1)) + && (aCutFlags & (CUTFLAG_START2|CUTFLAG_END2))) + { + // same startpoint? + if(!bFinished && (aCutFlags & (CUTFLAG_START1|CUTFLAG_START2)) == (CUTFLAG_START1|CUTFLAG_START2)) + { + if(rEdge1Start.equal(rEdge2Start)) + { + bFinished = true; + aRetval = (CUTFLAG_START1|CUTFLAG_START2); + } + } + + // same endpoint? + if(!bFinished && (aCutFlags & (CUTFLAG_END1|CUTFLAG_END2)) == (CUTFLAG_END1|CUTFLAG_END2)) + { + const B2DPoint aEnd1(rEdge1Start + rEdge1Delta); + const B2DPoint aEnd2(rEdge2Start + rEdge2Delta); + + if(aEnd1.equal(aEnd2)) + { + bFinished = true; + aRetval = (CUTFLAG_END1|CUTFLAG_END2); + fCut1 = fCut2 = 1.0; + } + } + + // startpoint1 == endpoint2? + if(!bFinished && (aCutFlags & (CUTFLAG_START1|CUTFLAG_END2)) == (CUTFLAG_START1|CUTFLAG_END2)) + { + const B2DPoint aEnd2(rEdge2Start + rEdge2Delta); + + if(rEdge1Start.equal(aEnd2)) + { + bFinished = true; + aRetval = (CUTFLAG_START1|CUTFLAG_END2); + fCut1 = 0.0; + fCut2 = 1.0; + } + } + + // startpoint2 == endpoint1? + if(!bFinished&& (aCutFlags & (CUTFLAG_START2|CUTFLAG_END1)) == (CUTFLAG_START2|CUTFLAG_END1)) + { + const B2DPoint aEnd1(rEdge1Start + rEdge1Delta); + + if(rEdge2Start.equal(aEnd1)) + { + bFinished = true; + aRetval = (CUTFLAG_START2|CUTFLAG_END1); + fCut1 = 1.0; + fCut2 = 0.0; + } + } + } + + if(!bFinished && (aCutFlags & CUTFLAG_LINE)) + { + if(!bFinished && (aCutFlags & CUTFLAG_START1)) + { + // start1 on line 2 ? + if(isPointOnEdge(rEdge1Start, rEdge2Start, rEdge2Delta, &fCut2)) + { + bFinished = true; + aRetval = (CUTFLAG_LINE|CUTFLAG_START1); + } + } + + if(!bFinished && (aCutFlags & CUTFLAG_START2)) + { + // start2 on line 1 ? + if(isPointOnEdge(rEdge2Start, rEdge1Start, rEdge1Delta, &fCut1)) + { + bFinished = true; + aRetval = (CUTFLAG_LINE|CUTFLAG_START2); + } + } + + if(!bFinished && (aCutFlags & CUTFLAG_END1)) + { + // end1 on line 2 ? + const B2DPoint aEnd1(rEdge1Start + rEdge1Delta); + + if(isPointOnEdge(aEnd1, rEdge2Start, rEdge2Delta, &fCut2)) + { + bFinished = true; + aRetval = (CUTFLAG_LINE|CUTFLAG_END1); + } + } + + if(!bFinished && (aCutFlags & CUTFLAG_END2)) + { + // end2 on line 1 ? + const B2DPoint aEnd2(rEdge2Start + rEdge2Delta); + + if(isPointOnEdge(aEnd2, rEdge1Start, rEdge1Delta, &fCut1)) + { + bFinished = true; + aRetval = (CUTFLAG_LINE|CUTFLAG_END2); + } + } + + if(!bFinished) + { + // cut in line1, line2 ? + fCut1 = (rEdge1Delta.getX() * rEdge2Delta.getY()) - (rEdge1Delta.getY() * rEdge2Delta.getX()); + + if(!fTools::equalZero(fCut1)) + { + fCut1 = (rEdge2Delta.getY() * (rEdge2Start.getX() - rEdge1Start.getX()) + + rEdge2Delta.getX() * (rEdge1Start.getY() - rEdge2Start.getY())) / fCut1; + + const double fZero(0.0); + const double fOne(1.0); + + // inside parameter range edge1 AND fCut2 is calcable + if(fTools::more(fCut1, fZero) && fTools::less(fCut1, fOne) + && (!fTools::equalZero(rEdge2Delta.getX()) || !fTools::equalZero(rEdge2Delta.getY()))) + { + // take the mopre precise calculation of the two possible + if(fabs(rEdge2Delta.getX()) > fabs(rEdge2Delta.getY())) + { + fCut2 = (rEdge1Start.getX() + fCut1 + * rEdge1Delta.getX() - rEdge2Start.getX()) / rEdge2Delta.getX(); + } + else + { + fCut2 = (rEdge1Start.getY() + fCut1 + * rEdge1Delta.getY() - rEdge2Start.getY()) / rEdge2Delta.getY(); + } + + // inside parameter range edge2, too + if(fTools::more(fCut2, fZero) && fTools::less(fCut2, fOne)) + { + bFinished = true; + aRetval = CUTFLAG_LINE; + } + } + } + } + } + + // copy values if wanted + if(pCut1) + { + *pCut1 = fCut1; + } + + if(pCut2) + { + *pCut2 = fCut2; + } + + return aRetval; + } + + bool isPointOnEdge( + const B2DPoint& rPoint, + const B2DPoint& rEdgeStart, + const B2DVector& rEdgeDelta, + double* pCut) + { + bool bDeltaXIsZero(fTools::equalZero(rEdgeDelta.getX())); + bool bDeltaYIsZero(fTools::equalZero(rEdgeDelta.getY())); + const double fZero(0.0); + const double fOne(1.0); + + if(bDeltaXIsZero && bDeltaYIsZero) + { + // no line, just a point + return false; + } + else if(bDeltaXIsZero) + { + // vertical line + if(fTools::equal(rPoint.getX(), rEdgeStart.getX())) + { + double fValue = (rPoint.getY() - rEdgeStart.getY()) / rEdgeDelta.getY(); + + if(fTools::more(fValue, fZero) && fTools::less(fValue, fOne)) + { + if(pCut) + { + *pCut = fValue; + } + + return true; + } + } + } + else if(bDeltaYIsZero) + { + // horizontal line + if(fTools::equal(rPoint.getY(), rEdgeStart.getY())) + { + double fValue = (rPoint.getX() - rEdgeStart.getX()) / rEdgeDelta.getX(); + + if(fTools::more(fValue, fZero) && fTools::less(fValue, fOne)) + { + if(pCut) + { + *pCut = fValue; + } + + return true; + } + } + } + else + { + // any angle line + double fTOne = (rPoint.getX() - rEdgeStart.getX()) / rEdgeDelta.getX(); + double fTTwo = (rPoint.getY() - rEdgeStart.getY()) / rEdgeDelta.getY(); + + if(fTools::equal(fTOne, fTTwo)) + { + // same parameter representation, point is on line. Take + // middle value for better results + double fValue = (fTOne + fTTwo) / 2.0; + + if(fTools::more(fValue, fZero) && fTools::less(fValue, fOne)) + { + // point is inside line bounds, too + if(pCut) + { + *pCut = fValue; + } + + return true; + } + } + } + + return false; + } + + void applyLineDashing(const B2DPolygon& rCandidate, const ::std::vector<double>& rDotDashArray, B2DPolyPolygon* pLineTarget, B2DPolyPolygon* pGapTarget, double fDotDashLength) + { + const sal_uInt32 nPointCount(rCandidate.count()); + const sal_uInt32 nDotDashCount(rDotDashArray.size()); + + if(fTools::lessOrEqual(fDotDashLength, 0.0)) + { + fDotDashLength = ::std::accumulate(rDotDashArray.begin(), rDotDashArray.end(), 0.0); + } + + if(fTools::more(fDotDashLength, 0.0) && (pLineTarget || pGapTarget) && nPointCount) + { + // clear targets + if(pLineTarget) + { + pLineTarget->clear(); + } + + if(pGapTarget) + { + pGapTarget->clear(); + } + + // prepare current edge's start + B2DCubicBezier aCurrentEdge; + const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1); + aCurrentEdge.setStartPoint(rCandidate.getB2DPoint(0)); + + // prepare DotDashArray iteration and the line/gap switching bool + sal_uInt32 nDotDashIndex(0); + bool bIsLine(true); + double fDotDashMovingLength(rDotDashArray[0]); + B2DPolygon aSnippet; + + // iterate over all edges + for(sal_uInt32 a(0); a < nEdgeCount; a++) + { + // update current edge (fill in C1, C2 and end point) + double fLastDotDashMovingLength(0.0); + const sal_uInt32 nNextIndex((a + 1) % nPointCount); + aCurrentEdge.setControlPointA(rCandidate.getNextControlPoint(a)); + aCurrentEdge.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex)); + aCurrentEdge.setEndPoint(rCandidate.getB2DPoint(nNextIndex)); + + // check if we have a trivial bezier segment -> possible fallback to edge + aCurrentEdge.testAndSolveTrivialBezier(); + + if(aCurrentEdge.isBezier()) + { + // bezier segment + const B2DCubicBezierHelper aCubicBezierHelper(aCurrentEdge); + const double fEdgeLength(aCubicBezierHelper.getLength()); + + if(!fTools::equalZero(fEdgeLength)) + { + while(fTools::less(fDotDashMovingLength, fEdgeLength)) + { + // new split is inside edge, create and append snippet [fLastDotDashMovingLength, fDotDashMovingLength] + const bool bHandleLine(bIsLine && pLineTarget); + const bool bHandleGap(!bIsLine && pGapTarget); + + if(bHandleLine || bHandleGap) + { + const double fBezierSplitStart(aCubicBezierHelper.distanceToRelative(fLastDotDashMovingLength)); + const double fBezierSplitEnd(aCubicBezierHelper.distanceToRelative(fDotDashMovingLength)); + B2DCubicBezier aBezierSnippet(aCurrentEdge.snippet(fBezierSplitStart, fBezierSplitEnd)); + + if(!aSnippet.count()) + { + aSnippet.append(aBezierSnippet.getStartPoint()); + } + + aSnippet.appendBezierSegment(aBezierSnippet.getControlPointA(), aBezierSnippet.getControlPointB(), aBezierSnippet.getEndPoint()); + + if(bHandleLine) + { + pLineTarget->append(aSnippet); + } + else + { + pGapTarget->append(aSnippet); + } + + aSnippet.clear(); + } + + // prepare next DotDashArray step and flip line/gap flag + fLastDotDashMovingLength = fDotDashMovingLength; + fDotDashMovingLength += rDotDashArray[(++nDotDashIndex) % nDotDashCount]; + bIsLine = !bIsLine; + } + + // append closing snippet [fLastDotDashMovingLength, fEdgeLength] + const bool bHandleLine(bIsLine && pLineTarget); + const bool bHandleGap(!bIsLine && pGapTarget); + + if(bHandleLine || bHandleGap) + { + B2DCubicBezier aRight; + const double fBezierSplit(aCubicBezierHelper.distanceToRelative(fLastDotDashMovingLength)); + + aCurrentEdge.split(fBezierSplit, 0, &aRight); + + if(!aSnippet.count()) + { + aSnippet.append(aRight.getStartPoint()); + } + + aSnippet.appendBezierSegment(aRight.getControlPointA(), aRight.getControlPointB(), aRight.getEndPoint()); + } + + // prepare move to next edge + fDotDashMovingLength -= fEdgeLength; + } + } + else + { + // simple edge + const double fEdgeLength(aCurrentEdge.getEdgeLength()); + + if(!fTools::equalZero(fEdgeLength)) + { + while(fTools::less(fDotDashMovingLength, fEdgeLength)) + { + // new split is inside edge, create and append snippet [fLastDotDashMovingLength, fDotDashMovingLength] + const bool bHandleLine(bIsLine && pLineTarget); + const bool bHandleGap(!bIsLine && pGapTarget); + + if(bHandleLine || bHandleGap) + { + if(!aSnippet.count()) + { + aSnippet.append(interpolate(aCurrentEdge.getStartPoint(), aCurrentEdge.getEndPoint(), fLastDotDashMovingLength / fEdgeLength)); + } + + aSnippet.append(interpolate(aCurrentEdge.getStartPoint(), aCurrentEdge.getEndPoint(), fDotDashMovingLength / fEdgeLength)); + + if(bHandleLine) + { + pLineTarget->append(aSnippet); + } + else + { + pGapTarget->append(aSnippet); + } + + aSnippet.clear(); + } + + // prepare next DotDashArray step and flip line/gap flag + fLastDotDashMovingLength = fDotDashMovingLength; + fDotDashMovingLength += rDotDashArray[(++nDotDashIndex) % nDotDashCount]; + bIsLine = !bIsLine; + } + + // append snippet [fLastDotDashMovingLength, fEdgeLength] + const bool bHandleLine(bIsLine && pLineTarget); + const bool bHandleGap(!bIsLine && pGapTarget); + + if(bHandleLine || bHandleGap) + { + if(!aSnippet.count()) + { + aSnippet.append(interpolate(aCurrentEdge.getStartPoint(), aCurrentEdge.getEndPoint(), fLastDotDashMovingLength / fEdgeLength)); + } + + aSnippet.append(aCurrentEdge.getEndPoint()); + } + + // prepare move to next edge + fDotDashMovingLength -= fEdgeLength; + } + } + + // prepare next edge step (end point gets new start point) + aCurrentEdge.setStartPoint(aCurrentEdge.getEndPoint()); + } + + // append last intermediate results (if exists) + if(aSnippet.count()) + { + if(bIsLine && pLineTarget) + { + pLineTarget->append(aSnippet); + } + else if(!bIsLine && pGapTarget) + { + pGapTarget->append(aSnippet); + } + } + + // check if start and end polygon may be merged + if(pLineTarget) + { + const sal_uInt32 nCount(pLineTarget->count()); + + if(nCount > 1) + { + // these polygons were created above, there exists none with less than two points, + // thus dircet point access below is allowed + const B2DPolygon aFirst(pLineTarget->getB2DPolygon(0)); + B2DPolygon aLast(pLineTarget->getB2DPolygon(nCount - 1)); + + if(aFirst.getB2DPoint(0).equal(aLast.getB2DPoint(aLast.count() - 1))) + { + // start of first and end of last are the same -> merge them + aLast.append(aFirst); + aLast.removeDoublePoints(); + pLineTarget->setB2DPolygon(0, aLast); + pLineTarget->remove(nCount - 1); + } + } + } + + if(pGapTarget) + { + const sal_uInt32 nCount(pGapTarget->count()); + + if(nCount > 1) + { + // these polygons were created above, there exists none with less than two points, + // thus dircet point access below is allowed + const B2DPolygon aFirst(pGapTarget->getB2DPolygon(0)); + B2DPolygon aLast(pGapTarget->getB2DPolygon(nCount - 1)); + + if(aFirst.getB2DPoint(0).equal(aLast.getB2DPoint(aLast.count() - 1))) + { + // start of first and end of last are the same -> merge them + aLast.append(aFirst); + aLast.removeDoublePoints(); + pGapTarget->setB2DPolygon(0, aLast); + pGapTarget->remove(nCount - 1); + } + } + } + } + else + { + // parameters make no sense, just add source to targets + if(pLineTarget) + { + pLineTarget->append(rCandidate); + } + + if(pGapTarget) + { + pGapTarget->append(rCandidate); + } + } + } + + // test if point is inside epsilon-range around an edge defined + // by the two given points. Can be used for HitTesting. The epsilon-range + // is defined to be the rectangle centered to the given edge, using height + // 2 x fDistance, and the circle around both points with radius fDistance. + bool isInEpsilonRange(const B2DPoint& rEdgeStart, const B2DPoint& rEdgeEnd, const B2DPoint& rTestPosition, double fDistance) + { + // build edge vector + const B2DVector aEdge(rEdgeEnd - rEdgeStart); + bool bDoDistanceTestStart(false); + bool bDoDistanceTestEnd(false); + + if(aEdge.equalZero()) + { + // no edge, just a point. Do one of the distance tests. + bDoDistanceTestStart = true; + } + else + { + // edge has a length. Create perpendicular vector. + const B2DVector aPerpend(getPerpendicular(aEdge)); + double fCut( + (aPerpend.getY() * (rTestPosition.getX() - rEdgeStart.getX()) + + aPerpend.getX() * (rEdgeStart.getY() - rTestPosition.getY())) / + (aEdge.getX() * aEdge.getX() + aEdge.getY() * aEdge.getY())); + const double fZero(0.0); + const double fOne(1.0); + + if(fTools::less(fCut, fZero)) + { + // left of rEdgeStart + bDoDistanceTestStart = true; + } + else if(fTools::more(fCut, fOne)) + { + // right of rEdgeEnd + bDoDistanceTestEnd = true; + } + else + { + // inside line [0.0 .. 1.0] + const B2DPoint aCutPoint(interpolate(rEdgeStart, rEdgeEnd, fCut)); + const B2DVector aDelta(rTestPosition - aCutPoint); + const double fDistanceSquare(aDelta.scalar(aDelta)); + + if(fDistanceSquare <= fDistance * fDistance) + { + return true; + } + else + { + return false; + } + } + } + + if(bDoDistanceTestStart) + { + const B2DVector aDelta(rTestPosition - rEdgeStart); + const double fDistanceSquare(aDelta.scalar(aDelta)); + + if(fDistanceSquare <= fDistance * fDistance) + { + return true; + } + } + else if(bDoDistanceTestEnd) + { + const B2DVector aDelta(rTestPosition - rEdgeEnd); + const double fDistanceSquare(aDelta.scalar(aDelta)); + + if(fDistanceSquare <= fDistance * fDistance) + { + return true; + } + } + + return false; + } + + // test if point is inside epsilon-range around the given Polygon. Can be used + // for HitTesting. The epsilon-range is defined to be the tube around the polygon + // with distance fDistance and rounded edges (start and end point). + bool isInEpsilonRange(const B2DPolygon& rCandidate, const B2DPoint& rTestPosition, double fDistance) + { + // force to non-bezier polygon + const B2DPolygon aCandidate(rCandidate.getDefaultAdaptiveSubdivision()); + const sal_uInt32 nPointCount(aCandidate.count()); + + if(nPointCount) + { + const sal_uInt32 nEdgeCount(aCandidate.isClosed() ? nPointCount : nPointCount - 1L); + B2DPoint aCurrent(aCandidate.getB2DPoint(0)); + + if(nEdgeCount) + { + // edges + for(sal_uInt32 a(0); a < nEdgeCount; a++) + { + const sal_uInt32 nNextIndex((a + 1) % nPointCount); + const B2DPoint aNext(aCandidate.getB2DPoint(nNextIndex)); + + if(isInEpsilonRange(aCurrent, aNext, rTestPosition, fDistance)) + { + return true; + } + + // prepare next step + aCurrent = aNext; + } + } + else + { + // no edges, but points -> not closed. Check single point. Just + // use isInEpsilonRange with twice the same point, it handles those well + if(isInEpsilonRange(aCurrent, aCurrent, rTestPosition, fDistance)) + { + return true; + } + } + } + + return false; + } + + B2DPolygon createPolygonFromRect( const B2DRectangle& rRect, double fRadius ) + { + const double fZero(0.0); + const double fOne(1.0); + + if(fTools::lessOrEqual(fRadius, fZero)) + { + // no radius, use rectangle + return createPolygonFromRect( rRect ); + } + else if(fTools::moreOrEqual(fRadius, fOne)) + { + // full radius, use ellipse + const B2DPoint aCenter(rRect.getCenter()); + const double fRadiusX(rRect.getWidth() / 2.0); + const double fRadiusY(rRect.getHeight() / 2.0); + + return createPolygonFromEllipse( aCenter, fRadiusX, fRadiusY ); + } + else + { + // create rectangle with two radii between ]0.0 .. 1.0[ + return createPolygonFromRect( rRect, fRadius, fRadius ); + } + } + + B2DPolygon createPolygonFromRect( const B2DRectangle& rRect, double fRadiusX, double fRadiusY ) + { + const double fZero(0.0); + const double fOne(1.0); + + // crop to useful values + if(fTools::less(fRadiusX, fZero)) + { + fRadiusX = fZero; + } + else if(fTools::more(fRadiusX, fOne)) + { + fRadiusX = fOne; + } + + if(fTools::less(fRadiusY, fZero)) + { + fRadiusY = fZero; + } + else if(fTools::more(fRadiusY, fOne)) + { + fRadiusY = fOne; + } + + if(fZero == fRadiusX || fZero == fRadiusY) + { + B2DPolygon aRetval; + + // at least in one direction no radius, use rectangle. + // Do not use createPolygonFromRect() here since original + // creator (historical reasons) still creates a start point at the + // bottom center, so do the same here to get the same line patterns. + // Due to this the order of points is different, too. + const B2DPoint aBottomCenter(rRect.getCenter().getX(), rRect.getMaxY()); + aRetval.append(aBottomCenter); + + aRetval.append( B2DPoint( rRect.getMinX(), rRect.getMaxY() ) ); + aRetval.append( B2DPoint( rRect.getMinX(), rRect.getMinY() ) ); + aRetval.append( B2DPoint( rRect.getMaxX(), rRect.getMinY() ) ); + aRetval.append( B2DPoint( rRect.getMaxX(), rRect.getMaxY() ) ); + + // close + aRetval.setClosed( true ); + + return aRetval; + } + else if(fOne == fRadiusX && fOne == fRadiusY) + { + // in both directions full radius, use ellipse + const B2DPoint aCenter(rRect.getCenter()); + const double fRectRadiusX(rRect.getWidth() / 2.0); + const double fRectRadiusY(rRect.getHeight() / 2.0); + + return createPolygonFromEllipse( aCenter, fRectRadiusX, fRectRadiusY ); + } + else + { + B2DPolygon aRetval; + const double fBowX((rRect.getWidth() / 2.0) * fRadiusX); + const double fBowY((rRect.getHeight() / 2.0) * fRadiusY); + const double fKappa((M_SQRT2 - 1.0) * 4.0 / 3.0); + + // create start point at bottom center + if(fOne != fRadiusX) + { + const B2DPoint aBottomCenter(rRect.getCenter().getX(), rRect.getMaxY()); + aRetval.append(aBottomCenter); + } + + // create first bow + { + const B2DPoint aBottomRight(rRect.getMaxX(), rRect.getMaxY()); + const B2DPoint aStart(aBottomRight + B2DPoint(-fBowX, 0.0)); + const B2DPoint aStop(aBottomRight + B2DPoint(0.0, -fBowY)); + aRetval.append(aStart); + aRetval.appendBezierSegment(interpolate(aStart, aBottomRight, fKappa), interpolate(aStop, aBottomRight, fKappa), aStop); + } + + // create second bow + { + const B2DPoint aTopRight(rRect.getMaxX(), rRect.getMinY()); + const B2DPoint aStart(aTopRight + B2DPoint(0.0, fBowY)); + const B2DPoint aStop(aTopRight + B2DPoint(-fBowX, 0.0)); + aRetval.append(aStart); + aRetval.appendBezierSegment(interpolate(aStart, aTopRight, fKappa), interpolate(aStop, aTopRight, fKappa), aStop); + } + + // create third bow + { + const B2DPoint aTopLeft(rRect.getMinX(), rRect.getMinY()); + const B2DPoint aStart(aTopLeft + B2DPoint(fBowX, 0.0)); + const B2DPoint aStop(aTopLeft + B2DPoint(0.0, fBowY)); + aRetval.append(aStart); + aRetval.appendBezierSegment(interpolate(aStart, aTopLeft, fKappa), interpolate(aStop, aTopLeft, fKappa), aStop); + } + + // create forth bow + { + const B2DPoint aBottomLeft(rRect.getMinX(), rRect.getMaxY()); + const B2DPoint aStart(aBottomLeft + B2DPoint(0.0, -fBowY)); + const B2DPoint aStop(aBottomLeft + B2DPoint(fBowX, 0.0)); + aRetval.append(aStart); + aRetval.appendBezierSegment(interpolate(aStart, aBottomLeft, fKappa), interpolate(aStop, aBottomLeft, fKappa), aStop); + } + + // close + aRetval.setClosed( true ); + + // remove double created points if there are extreme radii envolved + if(fOne == fRadiusX || fOne == fRadiusY) + { + aRetval.removeDoublePoints(); + } + + return aRetval; + } + } + + B2DPolygon createPolygonFromRect( const B2DRectangle& rRect ) + { + B2DPolygon aRetval; + + aRetval.append( B2DPoint( rRect.getMinX(), rRect.getMinY() ) ); + aRetval.append( B2DPoint( rRect.getMaxX(), rRect.getMinY() ) ); + aRetval.append( B2DPoint( rRect.getMaxX(), rRect.getMaxY() ) ); + aRetval.append( B2DPoint( rRect.getMinX(), rRect.getMaxY() ) ); + + // close + aRetval.setClosed( true ); + + return aRetval; + } + + B2DPolygon createPolygonFromCircle( const B2DPoint& rCenter, double fRadius ) + { + return createPolygonFromEllipse( rCenter, fRadius, fRadius ); + } + + B2DPolygon impCreateUnitCircle(sal_uInt32 nStartQuadrant) + { + B2DPolygon aUnitCircle; + const double fKappa((M_SQRT2 - 1.0) * 4.0 / 3.0); + const double fScaledKappa(fKappa * (1.0 / STEPSPERQUARTER)); + const B2DHomMatrix aRotateMatrix(createRotateB2DHomMatrix(F_PI2 / STEPSPERQUARTER)); + + B2DPoint aPoint(1.0, 0.0); + B2DPoint aForward(1.0, fScaledKappa); + B2DPoint aBackward(1.0, -fScaledKappa); + + if(0 != nStartQuadrant) + { + const B2DHomMatrix aQuadrantMatrix(createRotateB2DHomMatrix(F_PI2 * (nStartQuadrant % 4))); + aPoint *= aQuadrantMatrix; + aBackward *= aQuadrantMatrix; + aForward *= aQuadrantMatrix; + } + + aUnitCircle.append(aPoint); + + for(sal_uInt32 a(0); a < STEPSPERQUARTER * 4; a++) + { + aPoint *= aRotateMatrix; + aBackward *= aRotateMatrix; + aUnitCircle.appendBezierSegment(aForward, aBackward, aPoint); + aForward *= aRotateMatrix; + } + + aUnitCircle.setClosed(true); + aUnitCircle.removeDoublePoints(); + + return aUnitCircle; + } + + B2DPolygon createPolygonFromUnitCircle(sal_uInt32 nStartQuadrant) + { + switch(nStartQuadrant % 4) + { + case 1 : + { + static B2DPolygon aUnitCircleStartQuadrantOne; + + if(!aUnitCircleStartQuadrantOne.count()) + { + ::osl::Mutex m_mutex; + aUnitCircleStartQuadrantOne = impCreateUnitCircle(1); + } + + return aUnitCircleStartQuadrantOne; + } + case 2 : + { + static B2DPolygon aUnitCircleStartQuadrantTwo; + + if(!aUnitCircleStartQuadrantTwo.count()) + { + ::osl::Mutex m_mutex; + aUnitCircleStartQuadrantTwo = impCreateUnitCircle(2); + } + + return aUnitCircleStartQuadrantTwo; + } + case 3 : + { + static B2DPolygon aUnitCircleStartQuadrantThree; + + if(!aUnitCircleStartQuadrantThree.count()) + { + ::osl::Mutex m_mutex; + aUnitCircleStartQuadrantThree = impCreateUnitCircle(3); + } + + return aUnitCircleStartQuadrantThree; + } + default : // case 0 : + { + static B2DPolygon aUnitCircleStartQuadrantZero; + + if(!aUnitCircleStartQuadrantZero.count()) + { + ::osl::Mutex m_mutex; + aUnitCircleStartQuadrantZero = impCreateUnitCircle(0); + } + + return aUnitCircleStartQuadrantZero; + } + } + } + + B2DPolygon createPolygonFromEllipse( const B2DPoint& rCenter, double fRadiusX, double fRadiusY ) + { + B2DPolygon aRetval(createPolygonFromUnitCircle()); + const B2DHomMatrix aMatrix(createScaleTranslateB2DHomMatrix(fRadiusX, fRadiusY, rCenter.getX(), rCenter.getY())); + + aRetval.transform(aMatrix); + + return aRetval; + } + + B2DPolygon createPolygonFromUnitEllipseSegment( double fStart, double fEnd ) + { + B2DPolygon aRetval; + + // truncate fStart, fEnd to a range of [0.0 .. F_2PI[ where F_2PI + // falls back to 0.0 to ensure a unique definition + if(fTools::less(fStart, 0.0)) + { + fStart = 0.0; + } + + if(fTools::moreOrEqual(fStart, F_2PI)) + { + fStart = 0.0; + } + + if(fTools::less(fEnd, 0.0)) + { + fEnd = 0.0; + } + + if(fTools::moreOrEqual(fEnd, F_2PI)) + { + fEnd = 0.0; + } + + if(fTools::equal(fStart, fEnd)) + { + // same start and end angle, add single point + aRetval.append(B2DPoint(cos(fStart), sin(fStart))); + } + else + { + const sal_uInt32 nSegments(STEPSPERQUARTER * 4); + const double fAnglePerSegment(F_PI2 / STEPSPERQUARTER); + const sal_uInt32 nStartSegment(sal_uInt32(fStart / fAnglePerSegment) % nSegments); + const sal_uInt32 nEndSegment(sal_uInt32(fEnd / fAnglePerSegment) % nSegments); + const double fKappa((M_SQRT2 - 1.0) * 4.0 / 3.0); + const double fScaledKappa(fKappa * (1.0 / STEPSPERQUARTER)); + + B2DPoint aSegStart(cos(fStart), sin(fStart)); + aRetval.append(aSegStart); + + if(nStartSegment == nEndSegment && fTools::more(fEnd, fStart)) + { + // start and end in one sector and in the right order, create in one segment + const B2DPoint aSegEnd(cos(fEnd), sin(fEnd)); + const double fFactor(fScaledKappa * ((fEnd - fStart) / fAnglePerSegment)); + + aRetval.appendBezierSegment( + aSegStart + (B2DPoint(-aSegStart.getY(), aSegStart.getX()) * fFactor), + aSegEnd - (B2DPoint(-aSegEnd.getY(), aSegEnd.getX()) * fFactor), + aSegEnd); + } + else + { + double fSegEndRad((nStartSegment + 1) * fAnglePerSegment); + double fFactor(fScaledKappa * ((fSegEndRad - fStart) / fAnglePerSegment)); + B2DPoint aSegEnd(cos(fSegEndRad), sin(fSegEndRad)); + + aRetval.appendBezierSegment( + aSegStart + (B2DPoint(-aSegStart.getY(), aSegStart.getX()) * fFactor), + aSegEnd - (B2DPoint(-aSegEnd.getY(), aSegEnd.getX()) * fFactor), + aSegEnd); + + sal_uInt32 nSegment((nStartSegment + 1) % nSegments); + aSegStart = aSegEnd; + + while(nSegment != nEndSegment) + { + // No end in this sector, add full sector. + fSegEndRad = (nSegment + 1) * fAnglePerSegment; + aSegEnd = B2DPoint(cos(fSegEndRad), sin(fSegEndRad)); + + aRetval.appendBezierSegment( + aSegStart + (B2DPoint(-aSegStart.getY(), aSegStart.getX()) * fScaledKappa), + aSegEnd - (B2DPoint(-aSegEnd.getY(), aSegEnd.getX()) * fScaledKappa), + aSegEnd); + + nSegment = (nSegment + 1) % nSegments; + aSegStart = aSegEnd; + } + + // End in this sector + const double fSegStartRad(nSegment * fAnglePerSegment); + fFactor = fScaledKappa * ((fEnd - fSegStartRad) / fAnglePerSegment); + aSegEnd = B2DPoint(cos(fEnd), sin(fEnd)); + + aRetval.appendBezierSegment( + aSegStart + (B2DPoint(-aSegStart.getY(), aSegStart.getX()) * fFactor), + aSegEnd - (B2DPoint(-aSegEnd.getY(), aSegEnd.getX()) * fFactor), + aSegEnd); + } + } + + // remove double points between segments created by segmented creation + aRetval.removeDoublePoints(); + + return aRetval; + } + + B2DPolygon createPolygonFromEllipseSegment( const B2DPoint& rCenter, double fRadiusX, double fRadiusY, double fStart, double fEnd ) + { + B2DPolygon aRetval(createPolygonFromUnitEllipseSegment(fStart, fEnd)); + const B2DHomMatrix aMatrix(createScaleTranslateB2DHomMatrix(fRadiusX, fRadiusY, rCenter.getX(), rCenter.getY())); + + aRetval.transform(aMatrix); + + return aRetval; + } + + bool hasNeutralPoints(const B2DPolygon& rCandidate) + { + OSL_ENSURE(!rCandidate.areControlPointsUsed(), "hasNeutralPoints: ATM works not for curves (!)"); + const sal_uInt32 nPointCount(rCandidate.count()); + + if(nPointCount > 2L) + { + B2DPoint aPrevPoint(rCandidate.getB2DPoint(nPointCount - 1L)); + B2DPoint aCurrPoint(rCandidate.getB2DPoint(0L)); + + for(sal_uInt32 a(0L); a < nPointCount; a++) + { + const B2DPoint aNextPoint(rCandidate.getB2DPoint((a + 1) % nPointCount)); + const B2DVector aPrevVec(aPrevPoint - aCurrPoint); + const B2DVector aNextVec(aNextPoint - aCurrPoint); + const B2VectorOrientation aOrientation(getOrientation(aNextVec, aPrevVec)); + + if(ORIENTATION_NEUTRAL == aOrientation) + { + // current has neutral orientation + return true; + } + else + { + // prepare next + aPrevPoint = aCurrPoint; + aCurrPoint = aNextPoint; + } + } + } + + return false; + } + + B2DPolygon removeNeutralPoints(const B2DPolygon& rCandidate) + { + if(hasNeutralPoints(rCandidate)) + { + const sal_uInt32 nPointCount(rCandidate.count()); + B2DPolygon aRetval; + B2DPoint aPrevPoint(rCandidate.getB2DPoint(nPointCount - 1L)); + B2DPoint aCurrPoint(rCandidate.getB2DPoint(0L)); + + for(sal_uInt32 a(0L); a < nPointCount; a++) + { + const B2DPoint aNextPoint(rCandidate.getB2DPoint((a + 1) % nPointCount)); + const B2DVector aPrevVec(aPrevPoint - aCurrPoint); + const B2DVector aNextVec(aNextPoint - aCurrPoint); + const B2VectorOrientation aOrientation(getOrientation(aNextVec, aPrevVec)); + + if(ORIENTATION_NEUTRAL == aOrientation) + { + // current has neutral orientation, leave it out and prepare next + aCurrPoint = aNextPoint; + } + else + { + // add current point + aRetval.append(aCurrPoint); + + // prepare next + aPrevPoint = aCurrPoint; + aCurrPoint = aNextPoint; + } + } + + while(aRetval.count() && ORIENTATION_NEUTRAL == getOrientationForIndex(aRetval, 0L)) + { + aRetval.remove(0L); + } + + // copy closed state + aRetval.setClosed(rCandidate.isClosed()); + + return aRetval; + } + else + { + return rCandidate; + } + } + + bool isConvex(const B2DPolygon& rCandidate) + { + OSL_ENSURE(!rCandidate.areControlPointsUsed(), "isConvex: ATM works not for curves (!)"); + const sal_uInt32 nPointCount(rCandidate.count()); + + if(nPointCount > 2L) + { + const B2DPoint aPrevPoint(rCandidate.getB2DPoint(nPointCount - 1L)); + B2DPoint aCurrPoint(rCandidate.getB2DPoint(0L)); + B2DVector aCurrVec(aPrevPoint - aCurrPoint); + B2VectorOrientation aOrientation(ORIENTATION_NEUTRAL); + + for(sal_uInt32 a(0L); a < nPointCount; a++) + { + const B2DPoint aNextPoint(rCandidate.getB2DPoint((a + 1) % nPointCount)); + const B2DVector aNextVec(aNextPoint - aCurrPoint); + const B2VectorOrientation aCurrentOrientation(getOrientation(aNextVec, aCurrVec)); + + if(ORIENTATION_NEUTRAL == aOrientation) + { + // set start value, maybe neutral again + aOrientation = aCurrentOrientation; + } + else + { + if(ORIENTATION_NEUTRAL != aCurrentOrientation && aCurrentOrientation != aOrientation) + { + // different orientations found, that's it + return false; + } + } + + // prepare next + aCurrPoint = aNextPoint; + aCurrVec = -aNextVec; + } + } + + return true; + } + + B2VectorOrientation getOrientationForIndex(const B2DPolygon& rCandidate, sal_uInt32 nIndex) + { + OSL_ENSURE(nIndex < rCandidate.count(), "getOrientationForIndex: index out of range (!)"); + const B2DPoint aPrev(rCandidate.getB2DPoint(getIndexOfPredecessor(nIndex, rCandidate))); + const B2DPoint aCurr(rCandidate.getB2DPoint(nIndex)); + const B2DPoint aNext(rCandidate.getB2DPoint(getIndexOfSuccessor(nIndex, rCandidate))); + const B2DVector aBack(aPrev - aCurr); + const B2DVector aForw(aNext - aCurr); + + return getOrientation(aForw, aBack); + } + + bool isPointOnLine(const B2DPoint& rStart, const B2DPoint& rEnd, const B2DPoint& rCandidate, bool bWithPoints) + { + if(rCandidate.equal(rStart) || rCandidate.equal(rEnd)) + { + // candidate is in epsilon around start or end -> inside + return bWithPoints; + } + else if(rStart.equal(rEnd)) + { + // start and end are equal, but candidate is outside their epsilon -> outside + return false; + } + else + { + const B2DVector aEdgeVector(rEnd - rStart); + const B2DVector aTestVector(rCandidate - rStart); + + if(areParallel(aEdgeVector, aTestVector)) + { + const double fZero(0.0); + const double fOne(1.0); + const double fParamTestOnCurr(fabs(aEdgeVector.getX()) > fabs(aEdgeVector.getY()) + ? aTestVector.getX() / aEdgeVector.getX() + : aTestVector.getY() / aEdgeVector.getY()); + + if(fTools::more(fParamTestOnCurr, fZero) && fTools::less(fParamTestOnCurr, fOne)) + { + return true; + } + } + + return false; + } + } + + bool isPointOnPolygon(const B2DPolygon& rCandidate, const B2DPoint& rPoint, bool bWithPoints) + { + const B2DPolygon aCandidate(rCandidate.areControlPointsUsed() ? rCandidate.getDefaultAdaptiveSubdivision() : rCandidate); + const sal_uInt32 nPointCount(aCandidate.count()); + + if(nPointCount > 1L) + { + const sal_uInt32 nLoopCount(aCandidate.isClosed() ? nPointCount : nPointCount - 1L); + B2DPoint aCurrentPoint(aCandidate.getB2DPoint(0L)); + + for(sal_uInt32 a(0L); a < nLoopCount; a++) + { + const B2DPoint aNextPoint(aCandidate.getB2DPoint((a + 1L) % nPointCount)); + + if(isPointOnLine(aCurrentPoint, aNextPoint, rPoint, bWithPoints)) + { + return true; + } + + aCurrentPoint = aNextPoint; + } + } + else if(nPointCount && bWithPoints) + { + return rPoint.equal(aCandidate.getB2DPoint(0L)); + } + + return false; + } + + bool isPointInTriangle(const B2DPoint& rA, const B2DPoint& rB, const B2DPoint& rC, const B2DPoint& rCandidate, bool bWithBorder) + { + if(arePointsOnSameSideOfLine(rA, rB, rC, rCandidate, bWithBorder)) + { + if(arePointsOnSameSideOfLine(rB, rC, rA, rCandidate, bWithBorder)) + { + if(arePointsOnSameSideOfLine(rC, rA, rB, rCandidate, bWithBorder)) + { + return true; + } + } + } + + return false; + } + + bool arePointsOnSameSideOfLine(const B2DPoint& rStart, const B2DPoint& rEnd, const B2DPoint& rCandidateA, const B2DPoint& rCandidateB, bool bWithLine) + { + const B2DVector aLineVector(rEnd - rStart); + const B2DVector aVectorToA(rEnd - rCandidateA); + const double fCrossA(aLineVector.cross(aVectorToA)); + + if(fTools::equalZero(fCrossA)) + { + // one point on the line + return bWithLine; + } + + const B2DVector aVectorToB(rEnd - rCandidateB); + const double fCrossB(aLineVector.cross(aVectorToB)); + + if(fTools::equalZero(fCrossB)) + { + // one point on the line + return bWithLine; + } + + // return true if they both have the same sign + return ((fCrossA > 0.0) == (fCrossB > 0.0)); + } + + void addTriangleFan(const B2DPolygon& rCandidate, B2DPolygon& rTarget) + { + const sal_uInt32 nCount(rCandidate.count()); + + if(nCount > 2L) + { + const B2DPoint aStart(rCandidate.getB2DPoint(0L)); + B2DPoint aLast(rCandidate.getB2DPoint(1L)); + + for(sal_uInt32 a(2L); a < nCount; a++) + { + const B2DPoint aCurrent(rCandidate.getB2DPoint(a)); + rTarget.append(aStart); + rTarget.append(aLast); + rTarget.append(aCurrent); + + // prepare next + aLast = aCurrent; + } + } + } + + namespace + { + /// return 0 for input of 0, -1 for negative and 1 for positive input + inline int lcl_sgn( const double n ) + { + return n == 0.0 ? 0 : 1 - 2*::rtl::math::isSignBitSet(n); + } + } + + bool isRectangle( const B2DPolygon& rPoly ) + { + // polygon must be closed to resemble a rect, and contain + // at least four points. + if( !rPoly.isClosed() || + rPoly.count() < 4 ) + { + return false; + } + + // number of 90 degree turns the polygon has taken + int nNumTurns(0); + + int nVerticalEdgeType=0; + int nHorizontalEdgeType=0; + bool bNullVertex(true); + bool bCWPolygon(false); // when true, polygon is CW + // oriented, when false, CCW + bool bOrientationSet(false); // when false, polygon + // orientation has not yet + // been determined. + + // scan all _edges_ (which involves coming back to point 0 + // for the last edge - thus the modulo operation below) + const sal_Int32 nCount( rPoly.count() ); + for( sal_Int32 i=0; i<nCount; ++i ) + { + const B2DPoint& rPoint0( rPoly.getB2DPoint(i % nCount) ); + const B2DPoint& rPoint1( rPoly.getB2DPoint((i+1) % nCount) ); + + // is 0 for zero direction vector, 1 for south edge and -1 + // for north edge (standard screen coordinate system) + int nCurrVerticalEdgeType( lcl_sgn( rPoint1.getY() - rPoint0.getY() ) ); + + // is 0 for zero direction vector, 1 for east edge and -1 + // for west edge (standard screen coordinate system) + int nCurrHorizontalEdgeType( lcl_sgn(rPoint1.getX() - rPoint0.getX()) ); + + if( nCurrVerticalEdgeType && nCurrHorizontalEdgeType ) + return false; // oblique edge - for sure no rect + + const bool bCurrNullVertex( !nCurrVerticalEdgeType && !nCurrHorizontalEdgeType ); + + // current vertex is equal to previous - just skip, + // until we have a real edge + if( bCurrNullVertex ) + continue; + + // if previous edge has two identical points, because + // no previous edge direction was available, simply + // take this first non-null edge as the start + // direction. That's what will happen here, if + // bNullVertex is false + if( !bNullVertex ) + { + // 2D cross product - is 1 for CW and -1 for CCW turns + const int nCrossProduct( nHorizontalEdgeType*nCurrVerticalEdgeType - + nVerticalEdgeType*nCurrHorizontalEdgeType ); + + if( !nCrossProduct ) + continue; // no change in orientation - + // collinear edges - just go on + + // if polygon orientation is not set, we'll + // determine it now + if( !bOrientationSet ) + { + bCWPolygon = nCrossProduct == 1; + bOrientationSet = true; + } + else + { + // if current turn orientation is not equal + // initial orientation, this is not a + // rectangle (as rectangles have consistent + // orientation). + if( (nCrossProduct == 1) != bCWPolygon ) + return false; + } + + ++nNumTurns; + + // More than four 90 degree turns are an + // indication that this must not be a rectangle. + if( nNumTurns > 4 ) + return false; + } + + // store current state for the next turn + nVerticalEdgeType = nCurrVerticalEdgeType; + nHorizontalEdgeType = nCurrHorizontalEdgeType; + bNullVertex = false; // won't reach this line, + // if bCurrNullVertex is + // true - see above + } + + return true; + } + + B3DPolygon createB3DPolygonFromB2DPolygon(const B2DPolygon& rCandidate, double fZCoordinate) + { + if(rCandidate.areControlPointsUsed()) + { + // call myself recursively with subdivided input + const B2DPolygon aCandidate(adaptiveSubdivideByAngle(rCandidate)); + return createB3DPolygonFromB2DPolygon(aCandidate, fZCoordinate); + } + else + { + B3DPolygon aRetval; + + for(sal_uInt32 a(0L); a < rCandidate.count(); a++) + { + B2DPoint aPoint(rCandidate.getB2DPoint(a)); + aRetval.append(B3DPoint(aPoint.getX(), aPoint.getY(), fZCoordinate)); + } + + // copy closed state + aRetval.setClosed(rCandidate.isClosed()); + + return aRetval; + } + } + + B2DPolygon createB2DPolygonFromB3DPolygon(const B3DPolygon& rCandidate, const B3DHomMatrix& rMat) + { + B2DPolygon aRetval; + const sal_uInt32 nCount(rCandidate.count()); + const bool bIsIdentity(rMat.isIdentity()); + + for(sal_uInt32 a(0L); a < nCount; a++) + { + B3DPoint aCandidate(rCandidate.getB3DPoint(a)); + + if(!bIsIdentity) + { + aCandidate *= rMat; + } + + aRetval.append(B2DPoint(aCandidate.getX(), aCandidate.getY())); + } + + // copy closed state + aRetval.setClosed(rCandidate.isClosed()); + + return aRetval; + } + + double getDistancePointToEndlessRay(const B2DPoint& rPointA, const B2DPoint& rPointB, const B2DPoint& rTestPoint, double& rCut) + { + if(rPointA.equal(rPointB)) + { + rCut = 0.0; + const B2DVector aVector(rTestPoint - rPointA); + return aVector.getLength(); + } + else + { + // get the relative cut value on line vector (Vector1) for cut with perpendicular through TestPoint + const B2DVector aVector1(rPointB - rPointA); + const B2DVector aVector2(rTestPoint - rPointA); + const double fDividend((aVector2.getX() * aVector1.getX()) + (aVector2.getY() * aVector1.getY())); + const double fDivisor((aVector1.getX() * aVector1.getX()) + (aVector1.getY() * aVector1.getY())); + + rCut = fDividend / fDivisor; + + const B2DPoint aCutPoint(rPointA + rCut * aVector1); + const B2DVector aVector(rTestPoint - aCutPoint); + return aVector.getLength(); + } + } + + double getSmallestDistancePointToEdge(const B2DPoint& rPointA, const B2DPoint& rPointB, const B2DPoint& rTestPoint, double& rCut) + { + if(rPointA.equal(rPointB)) + { + rCut = 0.0; + const B2DVector aVector(rTestPoint - rPointA); + return aVector.getLength(); + } + else + { + // get the relative cut value on line vector (Vector1) for cut with perpendicular through TestPoint + const B2DVector aVector1(rPointB - rPointA); + const B2DVector aVector2(rTestPoint - rPointA); + const double fDividend((aVector2.getX() * aVector1.getX()) + (aVector2.getY() * aVector1.getY())); + const double fDivisor((aVector1.getX() * aVector1.getX()) + (aVector1.getY() * aVector1.getY())); + const double fCut(fDividend / fDivisor); + + if(fCut < 0.0) + { + // not in line range, get distance to PointA + rCut = 0.0; + return aVector2.getLength(); + } + else if(fCut > 1.0) + { + // not in line range, get distance to PointB + rCut = 1.0; + const B2DVector aVector(rTestPoint - rPointB); + return aVector.getLength(); + } + else + { + // in line range + const B2DPoint aCutPoint(rPointA + fCut * aVector1); + const B2DVector aVector(rTestPoint - aCutPoint); + rCut = fCut; + return aVector.getLength(); + } + } + } + + double getSmallestDistancePointToPolygon(const B2DPolygon& rCandidate, const B2DPoint& rTestPoint, sal_uInt32& rEdgeIndex, double& rCut) + { + double fRetval(DBL_MAX); + const sal_uInt32 nPointCount(rCandidate.count()); + + if(nPointCount > 1L) + { + const double fZero(0.0); + const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1L); + B2DCubicBezier aBezier; + aBezier.setStartPoint(rCandidate.getB2DPoint(0)); + + for(sal_uInt32 a(0L); a < nEdgeCount; a++) + { + const sal_uInt32 nNextIndex((a + 1) % nPointCount); + aBezier.setEndPoint(rCandidate.getB2DPoint(nNextIndex)); + double fEdgeDist; + double fNewCut; + bool bEdgeIsCurve(false); + + if(rCandidate.areControlPointsUsed()) + { + aBezier.setControlPointA(rCandidate.getNextControlPoint(a)); + aBezier.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex)); + aBezier.testAndSolveTrivialBezier(); + bEdgeIsCurve = aBezier.isBezier(); + } + + if(bEdgeIsCurve) + { + fEdgeDist = aBezier.getSmallestDistancePointToBezierSegment(rTestPoint, fNewCut); + } + else + { + fEdgeDist = getSmallestDistancePointToEdge(aBezier.getStartPoint(), aBezier.getEndPoint(), rTestPoint, fNewCut); + } + + if(DBL_MAX == fRetval || fEdgeDist < fRetval) + { + fRetval = fEdgeDist; + rEdgeIndex = a; + rCut = fNewCut; + + if(fTools::equal(fRetval, fZero)) + { + // already found zero distance, cannot get better. Ensure numerical zero value and end loop. + fRetval = 0.0; + break; + } + } + + // prepare next step + aBezier.setStartPoint(aBezier.getEndPoint()); + } + + if(1.0 == rCut) + { + // correct rEdgeIndex when not last point + if(rCandidate.isClosed()) + { + rEdgeIndex = getIndexOfSuccessor(rEdgeIndex, rCandidate); + rCut = 0.0; + } + else + { + if(rEdgeIndex != nEdgeCount - 1L) + { + rEdgeIndex++; + rCut = 0.0; + } + } + } + } + + return fRetval; + } + + B2DPoint distort(const B2DPoint& rCandidate, const B2DRange& rOriginal, const B2DPoint& rTopLeft, const B2DPoint& rTopRight, const B2DPoint& rBottomLeft, const B2DPoint& rBottomRight) + { + if(fTools::equalZero(rOriginal.getWidth()) || fTools::equalZero(rOriginal.getHeight())) + { + return rCandidate; + } + else + { + const double fRelativeX((rCandidate.getX() - rOriginal.getMinX()) / rOriginal.getWidth()); + const double fRelativeY((rCandidate.getY() - rOriginal.getMinY()) / rOriginal.getHeight()); + const double fOneMinusRelativeX(1.0 - fRelativeX); + const double fOneMinusRelativeY(1.0 - fRelativeY); + const double fNewX((fOneMinusRelativeY) * ((fOneMinusRelativeX) * rTopLeft.getX() + fRelativeX * rTopRight.getX()) + + fRelativeY * ((fOneMinusRelativeX) * rBottomLeft.getX() + fRelativeX * rBottomRight.getX())); + const double fNewY((fOneMinusRelativeX) * ((fOneMinusRelativeY) * rTopLeft.getY() + fRelativeY * rBottomLeft.getY()) + + fRelativeX * ((fOneMinusRelativeY) * rTopRight.getY() + fRelativeY * rBottomRight.getY())); + + return B2DPoint(fNewX, fNewY); + } + } + + B2DPolygon distort(const B2DPolygon& rCandidate, const B2DRange& rOriginal, const B2DPoint& rTopLeft, const B2DPoint& rTopRight, const B2DPoint& rBottomLeft, const B2DPoint& rBottomRight) + { + const sal_uInt32 nPointCount(rCandidate.count()); + + if(nPointCount && 0.0 != rOriginal.getWidth() && 0.0 != rOriginal.getHeight()) + { + B2DPolygon aRetval; + + for(sal_uInt32 a(0L); a < nPointCount; a++) + { + aRetval.append(distort(rCandidate.getB2DPoint(a), rOriginal, rTopLeft, rTopRight, rBottomLeft, rBottomRight)); + + if(rCandidate.areControlPointsUsed()) + { + if(!rCandidate.getPrevControlPoint(a).equalZero()) + { + aRetval.setPrevControlPoint(a, distort(rCandidate.getPrevControlPoint(a), rOriginal, rTopLeft, rTopRight, rBottomLeft, rBottomRight)); + } + + if(!rCandidate.getNextControlPoint(a).equalZero()) + { + aRetval.setNextControlPoint(a, distort(rCandidate.getNextControlPoint(a), rOriginal, rTopLeft, rTopRight, rBottomLeft, rBottomRight)); + } + } + } + + aRetval.setClosed(rCandidate.isClosed()); + return aRetval; + } + else + { + return rCandidate; + } + } + + B2DPolygon rotateAroundPoint(const B2DPolygon& rCandidate, const B2DPoint& rCenter, double fAngle) + { + const sal_uInt32 nPointCount(rCandidate.count()); + B2DPolygon aRetval(rCandidate); + + if(nPointCount) + { + const B2DHomMatrix aMatrix(basegfx::tools::createRotateAroundPoint(rCenter, fAngle)); + + aRetval.transform(aMatrix); + } + + return aRetval; + } + + B2DPolygon expandToCurve(const B2DPolygon& rCandidate) + { + B2DPolygon aRetval(rCandidate); + + for(sal_uInt32 a(0L); a < rCandidate.count(); a++) + { + expandToCurveInPoint(aRetval, a); + } + + return aRetval; + } + + bool expandToCurveInPoint(B2DPolygon& rCandidate, sal_uInt32 nIndex) + { + OSL_ENSURE(nIndex < rCandidate.count(), "expandToCurveInPoint: Access to polygon out of range (!)"); + bool bRetval(false); + const sal_uInt32 nPointCount(rCandidate.count()); + + if(nPointCount) + { + // predecessor + if(!rCandidate.isPrevControlPointUsed(nIndex)) + { + if(!rCandidate.isClosed() && 0 == nIndex) + { + // do not create previous vector for start point of open polygon + } + else + { + const sal_uInt32 nPrevIndex((nIndex + (nPointCount - 1)) % nPointCount); + rCandidate.setPrevControlPoint(nIndex, interpolate(rCandidate.getB2DPoint(nIndex), rCandidate.getB2DPoint(nPrevIndex), 1.0 / 3.0)); + bRetval = true; + } + } + + // successor + if(!rCandidate.isNextControlPointUsed(nIndex)) + { + if(!rCandidate.isClosed() && nIndex + 1 == nPointCount) + { + // do not create next vector for end point of open polygon + } + else + { + const sal_uInt32 nNextIndex((nIndex + 1) % nPointCount); + rCandidate.setNextControlPoint(nIndex, interpolate(rCandidate.getB2DPoint(nIndex), rCandidate.getB2DPoint(nNextIndex), 1.0 / 3.0)); + bRetval = true; + } + } + } + + return bRetval; + } + + B2DPolygon setContinuity(const B2DPolygon& rCandidate, B2VectorContinuity eContinuity) + { + B2DPolygon aRetval(rCandidate); + + for(sal_uInt32 a(0L); a < rCandidate.count(); a++) + { + setContinuityInPoint(aRetval, a, eContinuity); + } + + return aRetval; + } + + bool setContinuityInPoint(B2DPolygon& rCandidate, sal_uInt32 nIndex, B2VectorContinuity eContinuity) + { + OSL_ENSURE(nIndex < rCandidate.count(), "setContinuityInPoint: Access to polygon out of range (!)"); + bool bRetval(false); + const sal_uInt32 nPointCount(rCandidate.count()); + + if(nPointCount) + { + const B2DPoint aCurrentPoint(rCandidate.getB2DPoint(nIndex)); + + switch(eContinuity) + { + case CONTINUITY_NONE : + { + if(rCandidate.isPrevControlPointUsed(nIndex)) + { + if(!rCandidate.isClosed() && 0 == nIndex) + { + // remove existing previous vector for start point of open polygon + rCandidate.resetPrevControlPoint(nIndex); + } + else + { + const sal_uInt32 nPrevIndex((nIndex + (nPointCount - 1)) % nPointCount); + rCandidate.setPrevControlPoint(nIndex, interpolate(aCurrentPoint, rCandidate.getB2DPoint(nPrevIndex), 1.0 / 3.0)); + } + + bRetval = true; + } + + if(rCandidate.isNextControlPointUsed(nIndex)) + { + if(!rCandidate.isClosed() && nIndex == nPointCount + 1) + { + // remove next vector for end point of open polygon + rCandidate.resetNextControlPoint(nIndex); + } + else + { + const sal_uInt32 nNextIndex((nIndex + 1) % nPointCount); + rCandidate.setNextControlPoint(nIndex, interpolate(aCurrentPoint, rCandidate.getB2DPoint(nNextIndex), 1.0 / 3.0)); + } + + bRetval = true; + } + + break; + } + case CONTINUITY_C1 : + { + if(rCandidate.isPrevControlPointUsed(nIndex) && rCandidate.isNextControlPointUsed(nIndex)) + { + // lengths both exist since both are used + B2DVector aVectorPrev(rCandidate.getPrevControlPoint(nIndex) - aCurrentPoint); + B2DVector aVectorNext(rCandidate.getNextControlPoint(nIndex) - aCurrentPoint); + const double fLenPrev(aVectorPrev.getLength()); + const double fLenNext(aVectorNext.getLength()); + aVectorPrev.normalize(); + aVectorNext.normalize(); + const B2VectorOrientation aOrientation(getOrientation(aVectorPrev, aVectorNext)); + + if(ORIENTATION_NEUTRAL == aOrientation && aVectorPrev.scalar(aVectorNext) < 0.0) + { + // parallel and opposite direction; check length + if(fTools::equal(fLenPrev, fLenNext)) + { + // this would be even C2, but we want C1. Use the lengths of the corresponding edges. + const sal_uInt32 nPrevIndex((nIndex + (nPointCount - 1)) % nPointCount); + const sal_uInt32 nNextIndex((nIndex + 1) % nPointCount); + const double fLenPrevEdge(B2DVector(rCandidate.getB2DPoint(nPrevIndex) - aCurrentPoint).getLength() * (1.0 / 3.0)); + const double fLenNextEdge(B2DVector(rCandidate.getB2DPoint(nNextIndex) - aCurrentPoint).getLength() * (1.0 / 3.0)); + + rCandidate.setControlPoints(nIndex, + aCurrentPoint + (aVectorPrev * fLenPrevEdge), + aCurrentPoint + (aVectorNext * fLenNextEdge)); + bRetval = true; + } + } + else + { + // not parallel or same direction, set vectors and length + const B2DVector aNormalizedPerpendicular(getNormalizedPerpendicular(aVectorPrev + aVectorNext)); + + if(ORIENTATION_POSITIVE == aOrientation) + { + rCandidate.setControlPoints(nIndex, + aCurrentPoint - (aNormalizedPerpendicular * fLenPrev), + aCurrentPoint + (aNormalizedPerpendicular * fLenNext)); + } + else + { + rCandidate.setControlPoints(nIndex, + aCurrentPoint + (aNormalizedPerpendicular * fLenPrev), + aCurrentPoint - (aNormalizedPerpendicular * fLenNext)); + } + + bRetval = true; + } + } + break; + } + case CONTINUITY_C2 : + { + if(rCandidate.isPrevControlPointUsed(nIndex) && rCandidate.isNextControlPointUsed(nIndex)) + { + // lengths both exist since both are used + B2DVector aVectorPrev(rCandidate.getPrevControlPoint(nIndex) - aCurrentPoint); + B2DVector aVectorNext(rCandidate.getNextControlPoint(nIndex) - aCurrentPoint); + const double fCommonLength((aVectorPrev.getLength() + aVectorNext.getLength()) / 2.0); + aVectorPrev.normalize(); + aVectorNext.normalize(); + const B2VectorOrientation aOrientation(getOrientation(aVectorPrev, aVectorNext)); + + if(ORIENTATION_NEUTRAL == aOrientation && aVectorPrev.scalar(aVectorNext) < 0.0) + { + // parallel and opposite direction; set length. Use one direction for better numerical correctness + const B2DVector aScaledDirection(aVectorPrev * fCommonLength); + + rCandidate.setControlPoints(nIndex, + aCurrentPoint + aScaledDirection, + aCurrentPoint - aScaledDirection); + } + else + { + // not parallel or same direction, set vectors and length + const B2DVector aNormalizedPerpendicular(getNormalizedPerpendicular(aVectorPrev + aVectorNext)); + const B2DVector aPerpendicular(aNormalizedPerpendicular * fCommonLength); + + if(ORIENTATION_POSITIVE == aOrientation) + { + rCandidate.setControlPoints(nIndex, + aCurrentPoint - aPerpendicular, + aCurrentPoint + aPerpendicular); + } + else + { + rCandidate.setControlPoints(nIndex, + aCurrentPoint + aPerpendicular, + aCurrentPoint - aPerpendicular); + } + } + + bRetval = true; + } + break; + } + } + } + + return bRetval; + } + + B2DPolygon growInNormalDirection(const B2DPolygon& rCandidate, double fValue) + { + if(0.0 != fValue) + { + if(rCandidate.areControlPointsUsed()) + { + // call myself recursively with subdivided input + const B2DPolygon aCandidate(adaptiveSubdivideByAngle(rCandidate)); + return growInNormalDirection(aCandidate, fValue); + } + else + { + B2DPolygon aRetval; + const sal_uInt32 nPointCount(rCandidate.count()); + + if(nPointCount) + { + B2DPoint aPrev(rCandidate.getB2DPoint(nPointCount - 1L)); + B2DPoint aCurrent(rCandidate.getB2DPoint(0L)); + + for(sal_uInt32 a(0L); a < nPointCount; a++) + { + const B2DPoint aNext(rCandidate.getB2DPoint(a + 1L == nPointCount ? 0L : a + 1L)); + const B2DVector aBack(aPrev - aCurrent); + const B2DVector aForw(aNext - aCurrent); + const B2DVector aPerpBack(getNormalizedPerpendicular(aBack)); + const B2DVector aPerpForw(getNormalizedPerpendicular(aForw)); + B2DVector aDirection(aPerpBack - aPerpForw); + aDirection.normalize(); + aDirection *= fValue; + aRetval.append(aCurrent + aDirection); + + // prepare next step + aPrev = aCurrent; + aCurrent = aNext; + } + } + + // copy closed state + aRetval.setClosed(rCandidate.isClosed()); + + return aRetval; + } + } + else + { + return rCandidate; + } + } + + B2DPolygon reSegmentPolygon(const B2DPolygon& rCandidate, sal_uInt32 nSegments) + { + B2DPolygon aRetval; + const sal_uInt32 nPointCount(rCandidate.count()); + + if(nPointCount && nSegments) + { + // get current segment count + const sal_uInt32 nSegmentCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1L); + + if(nSegmentCount == nSegments) + { + aRetval = rCandidate; + } + else + { + const double fLength(getLength(rCandidate)); + const sal_uInt32 nLoopCount(rCandidate.isClosed() ? nSegments : nSegments + 1L); + + for(sal_uInt32 a(0L); a < nLoopCount; a++) + { + const double fRelativePos((double)a / (double)nSegments); // 0.0 .. 1.0 + const B2DPoint aNewPoint(getPositionRelative(rCandidate, fRelativePos, fLength)); + aRetval.append(aNewPoint); + } + + // copy closed flag + aRetval.setClosed(rCandidate.isClosed()); + } + } + + return aRetval; + } + + B2DPolygon reSegmentPolygonEdges(const B2DPolygon& rCandidate, sal_uInt32 nSubEdges, bool bHandleCurvedEdges, bool bHandleStraightEdges) + { + const sal_uInt32 nPointCount(rCandidate.count()); + + if(nPointCount < 2 || nSubEdges < 2 || (!bHandleCurvedEdges && !bHandleStraightEdges)) + { + // nothing to do: + // - less than two points -> no edge at all + // - less than two nSubEdges -> no resegment necessary + // - neither bHandleCurvedEdges nor bHandleStraightEdges -> nothing to do + return rCandidate; + } + else + { + B2DPolygon aRetval; + const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1); + B2DCubicBezier aCurrentEdge; + + // prepare first edge and add start point to target + aCurrentEdge.setStartPoint(rCandidate.getB2DPoint(0)); + aRetval.append(aCurrentEdge.getStartPoint()); + + for(sal_uInt32 a(0); a < nEdgeCount; a++) + { + // fill edge + const sal_uInt32 nNextIndex((a + 1) % nPointCount); + aCurrentEdge.setControlPointA(rCandidate.getNextControlPoint(a)); + aCurrentEdge.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex)); + aCurrentEdge.setEndPoint(rCandidate.getB2DPoint(nNextIndex)); + + if(aCurrentEdge.isBezier()) + { + if(bHandleCurvedEdges) + { + for(sal_uInt32 b(nSubEdges); b > 1; b--) + { + const double fSplitPoint(1.0 / b); + B2DCubicBezier aLeftPart; + + aCurrentEdge.split(fSplitPoint, &aLeftPart, &aCurrentEdge); + aRetval.appendBezierSegment(aLeftPart.getControlPointA(), aLeftPart.getControlPointB(), aLeftPart.getEndPoint()); + } + } + + // copy remaining segment to target + aRetval.appendBezierSegment(aCurrentEdge.getControlPointA(), aCurrentEdge.getControlPointB(), aCurrentEdge.getEndPoint()); + } + else + { + if(bHandleStraightEdges) + { + for(sal_uInt32 b(nSubEdges); b > 1; b--) + { + const double fSplitPoint(1.0 / b); + const B2DPoint aSplitPoint(interpolate(aCurrentEdge.getStartPoint(), aCurrentEdge.getEndPoint(), fSplitPoint)); + + aRetval.append(aSplitPoint); + aCurrentEdge.setStartPoint(aSplitPoint); + } + } + + // copy remaining segment to target + aRetval.append(aCurrentEdge.getEndPoint()); + } + + // prepare next step + aCurrentEdge.setStartPoint(aCurrentEdge.getEndPoint()); + } + + // copy closed flag and return + aRetval.setClosed(rCandidate.isClosed()); + return aRetval; + } + } + + B2DPolygon interpolate(const B2DPolygon& rOld1, const B2DPolygon& rOld2, double t) + { + OSL_ENSURE(rOld1.count() == rOld2.count(), "B2DPolygon interpolate: Different geometry (!)"); + + if(fTools::lessOrEqual(t, 0.0) || rOld1 == rOld2) + { + return rOld1; + } + else if(fTools::moreOrEqual(t, 1.0)) + { + return rOld2; + } + else + { + B2DPolygon aRetval; + const bool bInterpolateVectors(rOld1.areControlPointsUsed() || rOld2.areControlPointsUsed()); + aRetval.setClosed(rOld1.isClosed() && rOld2.isClosed()); + + for(sal_uInt32 a(0L); a < rOld1.count(); a++) + { + aRetval.append(interpolate(rOld1.getB2DPoint(a), rOld2.getB2DPoint(a), t)); + + if(bInterpolateVectors) + { + aRetval.setPrevControlPoint(a, interpolate(rOld1.getPrevControlPoint(a), rOld2.getPrevControlPoint(a), t)); + aRetval.setNextControlPoint(a, interpolate(rOld1.getNextControlPoint(a), rOld2.getNextControlPoint(a), t)); + } + } + + return aRetval; + } + } + + bool isPolyPolygonEqualRectangle( const B2DPolyPolygon& rPolyPoly, + const B2DRange& rRect ) + { + // exclude some cheap cases first + if( rPolyPoly.count() != 1 ) + return false; + + // fill array with rectangle vertices + const B2DPoint aPoints[] = + { + B2DPoint(rRect.getMinX(),rRect.getMinY()), + B2DPoint(rRect.getMaxX(),rRect.getMinY()), + B2DPoint(rRect.getMaxX(),rRect.getMaxY()), + B2DPoint(rRect.getMinX(),rRect.getMaxY()) + }; + + const B2DPolygon& rPoly( rPolyPoly.getB2DPolygon(0) ); + const sal_uInt32 nCount( rPoly.count() ); + const double epsilon = ::std::numeric_limits<double>::epsilon(); + + for(unsigned int j=0; j<4; ++j) + { + const B2DPoint &p1 = aPoints[j]; + const B2DPoint &p2 = aPoints[(j+1)%4]; + bool bPointOnBoundary = false; + for( sal_uInt32 i=0; i<nCount; ++i ) + { + const B2DPoint p(rPoly.getB2DPoint(i)); + + // 1 | x0 y0 1 | + // A = - | x1 y1 1 | + // 2 | x2 y2 1 | + double fDoubleArea = p2.getX()*p.getY() - + p2.getY()*p.getX() - + p1.getX()*p.getY() + + p1.getY()*p.getX() + + p1.getX()*p2.getY() - + p1.getY()*p2.getX(); + + if(fDoubleArea < epsilon) + { + bPointOnBoundary=true; + break; + } + } + if(!(bPointOnBoundary)) + return false; + } + + return true; + } + + + // create simplified version of the original polygon by + // replacing segments with spikes/loops and self intersections + // by several trivial sub-segments + B2DPolygon createSimplifiedPolygon( const B2DPolygon& rCandidate ) + { + const sal_uInt32 nCount(rCandidate.count()); + + if(nCount && rCandidate.areControlPointsUsed()) + { + const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nCount : nCount - 1); + B2DPolygon aRetval; + B2DCubicBezier aSegment; + + aSegment.setStartPoint(rCandidate.getB2DPoint(0)); + aRetval.append(aSegment.getStartPoint()); + + for(sal_uInt32 a(0); a < nEdgeCount; a++) + { + // fill edge + const sal_uInt32 nNextIndex((a + 1) % nCount); + aSegment.setControlPointA(rCandidate.getNextControlPoint(a)); + aSegment.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex)); + aSegment.setEndPoint(rCandidate.getB2DPoint(nNextIndex)); + + if(aSegment.isBezier()) + { + double fExtremumPos(0.0); + sal_uInt32 nExtremumCounter(4); + + while(nExtremumCounter-- && aSegment.isBezier() && aSegment.getMinimumExtremumPosition(fExtremumPos)) + { + // split off left, now extremum-free part and append + B2DCubicBezier aLeft; + + aSegment.split(fExtremumPos, &aLeft, &aSegment); + aLeft.testAndSolveTrivialBezier(); + aSegment.testAndSolveTrivialBezier(); + + if(aLeft.isBezier()) + { + aRetval.appendBezierSegment(aLeft.getControlPointA(), aLeft.getControlPointB(), aLeft.getEndPoint()); + } + else + { + aRetval.append(aLeft.getEndPoint()); + } + } + + // append (evtl. reduced) rest of Segment + if(aSegment.isBezier()) + { + aRetval.appendBezierSegment(aSegment.getControlPointA(), aSegment.getControlPointB(), aSegment.getEndPoint()); + } + else + { + aRetval.append(aSegment.getEndPoint()); + } + } + else + { + // simple edge, append end point + aRetval.append(aSegment.getEndPoint()); + } + + // prepare next edge + aSegment.setStartPoint(aSegment.getEndPoint()); + } + + // copy closed flag and check for double points + aRetval.setClosed(rCandidate.isClosed()); + aRetval.removeDoublePoints(); + + return aRetval; + } + else + { + return rCandidate; + } + } + + // #i76891# + B2DPolygon simplifyCurveSegments(const B2DPolygon& rCandidate) + { + const sal_uInt32 nPointCount(rCandidate.count()); + + if(nPointCount && rCandidate.areControlPointsUsed()) + { + // prepare loop + const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1); + B2DPolygon aRetval; + B2DCubicBezier aBezier; + aBezier.setStartPoint(rCandidate.getB2DPoint(0)); + + // try to avoid costly reallocations + aRetval.reserve( nEdgeCount+1); + + // add start point + aRetval.append(aBezier.getStartPoint()); + + for(sal_uInt32 a(0L); a < nEdgeCount; a++) + { + // get values for edge + const sal_uInt32 nNextIndex((a + 1) % nPointCount); + aBezier.setEndPoint(rCandidate.getB2DPoint(nNextIndex)); + aBezier.setControlPointA(rCandidate.getNextControlPoint(a)); + aBezier.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex)); + aBezier.testAndSolveTrivialBezier(); + + // still bezier? + if(aBezier.isBezier()) + { + // add edge with control vectors + aRetval.appendBezierSegment(aBezier.getControlPointA(), aBezier.getControlPointB(), aBezier.getEndPoint()); + } + else + { + // add edge + aRetval.append(aBezier.getEndPoint()); + } + + // next point + aBezier.setStartPoint(aBezier.getEndPoint()); + } + + if(rCandidate.isClosed()) + { + // set closed flag, rescue control point and correct last double point + closeWithGeometryChange(aRetval); + } + + return aRetval; + } + else + { + return rCandidate; + } + } + + // makes the given indexed point the new polygon start point. To do that, the points in the + // polygon will be rotated. This is only valid for closed polygons, for non-closed ones + // an assertion will be triggered + B2DPolygon makeStartPoint(const B2DPolygon& rCandidate, sal_uInt32 nIndexOfNewStatPoint) + { + const sal_uInt32 nPointCount(rCandidate.count()); + + if(nPointCount > 2 && nIndexOfNewStatPoint != 0 && nIndexOfNewStatPoint < nPointCount) + { + OSL_ENSURE(rCandidate.isClosed(), "makeStartPoint: only valid for closed polygons (!)"); + B2DPolygon aRetval; + + for(sal_uInt32 a(0); a < nPointCount; a++) + { + const sal_uInt32 nSourceIndex((a + nIndexOfNewStatPoint) % nPointCount); + aRetval.append(rCandidate.getB2DPoint(nSourceIndex)); + + if(rCandidate.areControlPointsUsed()) + { + aRetval.setPrevControlPoint(a, rCandidate.getPrevControlPoint(nSourceIndex)); + aRetval.setNextControlPoint(a, rCandidate.getNextControlPoint(nSourceIndex)); + } + } + + return aRetval; + } + + return rCandidate; + } + + B2DPolygon createEdgesOfGivenLength(const B2DPolygon& rCandidate, double fLength, double fStart, double fEnd) + { + B2DPolygon aRetval; + + if(fLength < 0.0) + { + fLength = 0.0; + } + + if(!fTools::equalZero(fLength)) + { + if(fStart < 0.0) + { + fStart = 0.0; + } + + if(fEnd < 0.0) + { + fEnd = 0.0; + } + + if(fEnd < fStart) + { + fEnd = fStart; + } + + // iterate and consume pieces with fLength. First subdivide to reduce input to line segments + const B2DPolygon aCandidate(rCandidate.areControlPointsUsed() ? rCandidate.getDefaultAdaptiveSubdivision() : rCandidate); + const sal_uInt32 nPointCount(aCandidate.count()); + + if(nPointCount > 1) + { + const bool bEndActive(!fTools::equalZero(fEnd)); + const sal_uInt32 nEdgeCount(aCandidate.isClosed() ? nPointCount : nPointCount - 1); + B2DPoint aCurrent(aCandidate.getB2DPoint(0)); + double fPositionInEdge(fStart); + double fAbsolutePosition(fStart); + + for(sal_uInt32 a(0); a < nEdgeCount; a++) + { + const sal_uInt32 nNextIndex((a + 1) % nPointCount); + const B2DPoint aNext(aCandidate.getB2DPoint(nNextIndex)); + const B2DVector aEdge(aNext - aCurrent); + double fEdgeLength(aEdge.getLength()); + + if(!fTools::equalZero(fEdgeLength)) + { + while(fTools::less(fPositionInEdge, fEdgeLength)) + { + // move position on edge forward as long as on edge + const double fScalar(fPositionInEdge / fEdgeLength); + aRetval.append(aCurrent + (aEdge * fScalar)); + fPositionInEdge += fLength; + + if(bEndActive) + { + fAbsolutePosition += fLength; + + if(fTools::more(fAbsolutePosition, fEnd)) + { + break; + } + } + } + + // substract length of current edge + fPositionInEdge -= fEdgeLength; + } + + if(bEndActive && fTools::more(fAbsolutePosition, fEnd)) + { + break; + } + + // prepare next step + aCurrent = aNext; + } + + // keep closed state + aRetval.setClosed(aCandidate.isClosed()); + } + else + { + // source polygon has only one point, return unchanged + aRetval = aCandidate; + } + } + + return aRetval; + } + + B2DPolygon createWaveline(const B2DPolygon& rCandidate, double fWaveWidth, double fWaveHeight) + { + B2DPolygon aRetval; + + if(fWaveWidth < 0.0) + { + fWaveWidth = 0.0; + } + + if(fWaveHeight < 0.0) + { + fWaveHeight = 0.0; + } + + const bool bHasWidth(!fTools::equalZero(fWaveWidth)); + const bool bHasHeight(!fTools::equalZero(fWaveHeight)); + + if(bHasWidth) + { + if(bHasHeight) + { + // width and height, create waveline. First subdivide to reduce input to line segments + // of WaveWidth. Last segment may be missing. If this turns out to be a problem, it + // may be added here again using the original last point from rCandidate. It may + // also be the case that rCandidate was closed. To simplify things it is handled here + // as if it was opened. + // Result from createEdgesOfGivenLength contains no curved segments, handle as straight + // edges. + const B2DPolygon aEqualLenghEdges(createEdgesOfGivenLength(rCandidate, fWaveWidth)); + const sal_uInt32 nPointCount(aEqualLenghEdges.count()); + + if(nPointCount > 1) + { + // iterate over straight edges, add start point + B2DPoint aCurrent(aEqualLenghEdges.getB2DPoint(0)); + aRetval.append(aCurrent); + + for(sal_uInt32 a(0); a < nPointCount - 1; a++) + { + const sal_uInt32 nNextIndex((a + 1) % nPointCount); + const B2DPoint aNext(aEqualLenghEdges.getB2DPoint(nNextIndex)); + const B2DVector aEdge(aNext - aCurrent); + const B2DVector aPerpendicular(getNormalizedPerpendicular(aEdge)); + const B2DVector aControlOffset((aEdge * 0.467308) - (aPerpendicular * fWaveHeight)); + + // add curve segment + aRetval.appendBezierSegment( + aCurrent + aControlOffset, + aNext - aControlOffset, + aNext); + + // prepare next step + aCurrent = aNext; + } + } + } + else + { + // width but no height -> return original polygon + aRetval = rCandidate; + } + } + else + { + // no width -> no waveline, stay empty and return + } + + return aRetval; + } + + ////////////////////////////////////////////////////////////////////// + // comparators with tolerance for 2D Polygons + + bool equal(const B2DPolygon& rCandidateA, const B2DPolygon& rCandidateB, const double& rfSmallValue) + { + const sal_uInt32 nPointCount(rCandidateA.count()); + + if(nPointCount != rCandidateB.count()) + return false; + + const bool bClosed(rCandidateA.isClosed()); + + if(bClosed != rCandidateB.isClosed()) + return false; + + const bool bAreControlPointsUsed(rCandidateA.areControlPointsUsed()); + + if(bAreControlPointsUsed != rCandidateB.areControlPointsUsed()) + return false; + + for(sal_uInt32 a(0); a < nPointCount; a++) + { + const B2DPoint aPoint(rCandidateA.getB2DPoint(a)); + + if(!aPoint.equal(rCandidateB.getB2DPoint(a), rfSmallValue)) + return false; + + if(bAreControlPointsUsed) + { + const basegfx::B2DPoint aPrev(rCandidateA.getPrevControlPoint(a)); + + if(!aPrev.equal(rCandidateB.getPrevControlPoint(a), rfSmallValue)) + return false; + + const basegfx::B2DPoint aNext(rCandidateA.getNextControlPoint(a)); + + if(!aNext.equal(rCandidateB.getNextControlPoint(a), rfSmallValue)) + return false; + } + } + + return true; + } + + bool equal(const B2DPolygon& rCandidateA, const B2DPolygon& rCandidateB) + { + const double fSmallValue(fTools::getSmallValue()); + + return equal(rCandidateA, rCandidateB, fSmallValue); + } + + // snap points of horizontal or vertical edges to discrete values + B2DPolygon snapPointsOfHorizontalOrVerticalEdges(const B2DPolygon& rCandidate) + { + const sal_uInt32 nPointCount(rCandidate.count()); + + if(nPointCount > 1) + { + // Start by copying the source polygon to get a writeable copy. The closed state is + // copied by aRetval's initialisation, too, so no need to copy it in this method + B2DPolygon aRetval(rCandidate); + + // prepare geometry data. Get rounded from original + B2ITuple aPrevTuple(basegfx::fround(rCandidate.getB2DPoint(nPointCount - 1))); + B2DPoint aCurrPoint(rCandidate.getB2DPoint(0)); + B2ITuple aCurrTuple(basegfx::fround(aCurrPoint)); + + // loop over all points. This will also snap the implicit closing edge + // even when not closed, but that's no problem here + for(sal_uInt32 a(0); a < nPointCount; a++) + { + // get next point. Get rounded from original + const bool bLastRun(a + 1 == nPointCount); + const sal_uInt32 nNextIndex(bLastRun ? 0 : a + 1); + const B2DPoint aNextPoint(rCandidate.getB2DPoint(nNextIndex)); + const B2ITuple aNextTuple(basegfx::fround(aNextPoint)); + + // get the states + const bool bPrevVertical(aPrevTuple.getX() == aCurrTuple.getX()); + const bool bNextVertical(aNextTuple.getX() == aCurrTuple.getX()); + const bool bPrevHorizontal(aPrevTuple.getY() == aCurrTuple.getY()); + const bool bNextHorizontal(aNextTuple.getY() == aCurrTuple.getY()); + const bool bSnapX(bPrevVertical || bNextVertical); + const bool bSnapY(bPrevHorizontal || bNextHorizontal); + + if(bSnapX || bSnapY) + { + const B2DPoint aSnappedPoint( + bSnapX ? aCurrTuple.getX() : aCurrPoint.getX(), + bSnapY ? aCurrTuple.getY() : aCurrPoint.getY()); + + aRetval.setB2DPoint(a, aSnappedPoint); + } + + // prepare next point + if(!bLastRun) + { + aPrevTuple = aCurrTuple; + aCurrPoint = aNextPoint; + aCurrTuple = aNextTuple; + } + } + + return aRetval; + } + else + { + return rCandidate; + } + } + + } // end of namespace tools +} // end of namespace basegfx + +////////////////////////////////////////////////////////////////////////////// +// eof |