/*************************************************************************
*
* 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 createUnitPolygon()
{
static B2DPolygon aRetval;
if(!aRetval.count())
{
aRetval.append( B2DPoint( 0.0, 0.0 ) );
aRetval.append( B2DPoint( 1.0, 0.0 ) );
aRetval.append( B2DPoint( 1.0, 1.0 ) );
aRetval.append( B2DPoint( 0.0, 1.0 ) );
// 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 ||
rPoly.areControlPointsUsed() )
{
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