/**************************************************************
*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements. See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership. The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied. See the License for the
* specific language governing permissions and limitations
* under the License.
*
*************************************************************/
// MARKER(update_precomp.py): autogen include statement, do not remove
#include "precompiled_basegfx.hxx"
#include <basegfx/polygon/b2dtrapezoid.hxx>
#include <basegfx/range/b1drange.hxx>
#include <basegfx/polygon/b2dpolygontools.hxx>
#include <list>
//////////////////////////////////////////////////////////////////////////////
namespace basegfx
{
namespace trapezoidhelper
{
//////////////////////////////////////////////////////////////////////////////
// helper class to hold a simple ege. This is only used for horizontal edges
// currently, thus the YPositions will be equal. I did not create a special
// class for this since holdingthe pointers is more effective and also can be
// used as baseclass for the traversing edges
class TrDeSimpleEdge
{
protected:
// pointers to start and end point
const B2DPoint* mpStart;
const B2DPoint* mpEnd;
public:
// constructor
TrDeSimpleEdge(
const B2DPoint* pStart,
const B2DPoint* pEnd)
: mpStart(pStart),
mpEnd(pEnd)
{
}
// data read access
const B2DPoint& getStart() const { return *mpStart; }
const B2DPoint& getEnd() const { return *mpEnd; }
};
//////////////////////////////////////////////////////////////////////////////
// define vector of simple edges
typedef ::std::vector< TrDeSimpleEdge > TrDeSimpleEdges;
//////////////////////////////////////////////////////////////////////////////
// helper class for holding a traversing edge. It will always have some
// distance in YPos. The slope (in a numerically useful form, see comments) is
// hold and used in SortValue to allow sorting traversing edges by Y, X and slope
// (in that order)
class TrDeEdgeEntry : public TrDeSimpleEdge
{
private:
// the slope in a numerical useful form for sorting
sal_uInt32 mnSortValue;
public:
// convenience data read access
double getDeltaX() const { return mpEnd->getX() - mpStart->getX(); }
double getDeltaY() const { return mpEnd->getY() - mpStart->getY(); }
// convenience data read access. SortValue is created on demand since
// it is not always used
sal_uInt32 getSortValue() const
{
if(0 != mnSortValue)
return mnSortValue;
// get radiant; has to be in the range ]0.0 .. pi[, thus scale to full
// sal_uInt32 range for maximum precision
const double fRadiant(atan2(getDeltaY(), getDeltaX()) * (SAL_MAX_UINT32 / F_PI));
// convert to sal_uInt32 value
const_cast< TrDeEdgeEntry* >(this)->mnSortValue = sal_uInt32(fRadiant);
return mnSortValue;
}
// constructor. SortValue can be given when known, use zero otherwise
TrDeEdgeEntry(
const B2DPoint* pStart,
const B2DPoint* pEnd,
sal_uInt32 nSortValue = 0)
: TrDeSimpleEdge(pStart, pEnd),
mnSortValue(nSortValue)
{
// force traversal of deltaY downward
if(mpEnd->getY() < mpStart->getY())
{
std::swap(mpStart, mpEnd);
}
// no horizontal edges allowed, all neeed to traverse vertically
OSL_ENSURE(mpEnd->getY() > mpStart->getY(), "Illegal TrDeEdgeEntry constructed (!)");
}
// data write access to StartPoint
void setStart( const B2DPoint* pNewStart)
{
OSL_ENSURE(0 != pNewStart, "No null pointer allowed here (!)");
if(mpStart != pNewStart)
{
mpStart = pNewStart;
// no horizontal edges allowed, all neeed to traverse vertivally
OSL_ENSURE(mpEnd->getY() > mpStart->getY(), "Illegal TrDeEdgeEntry constructed (!)");
}
}
// data write access to EndPoint
void setEnd( const B2DPoint* pNewEnd)
{
OSL_ENSURE(0 != pNewEnd, "No null pointer allowed here (!)");
if(mpEnd != pNewEnd)
{
mpEnd = pNewEnd;
// no horizontal edges allowed, all neeed to traverse vertivally
OSL_ENSURE(mpEnd->getY() > mpStart->getY(), "Illegal TrDeEdgeEntry constructed (!)");
}
}
// operator for sort support. Sort by Y, X and slope (in that order)
bool operator<(const TrDeEdgeEntry& rComp) const
{
if(fTools::equal(getStart().getY(), rComp.getStart().getY(), fTools::getSmallValue()))
{
if(fTools::equal(getStart().getX(), rComp.getStart().getX(), fTools::getSmallValue()))
{
// when start points are equal, use the direction the edge is pointing
// to. That value is created on demand and derived from atan2 in the
// range ]0.0 .. pi[ (without extremas, we always have a deltaY in this
// class) and scaled to sal_uInt32 range for best precision. 0 means no angle,
// while SAL_MAX_UINT32 means pi. Thus, the higher the value, the more left
// the edge traverses.
return (getSortValue() > rComp.getSortValue());
}
else
{
return fTools::less(getStart().getX(), rComp.getStart().getX());
}
}
else
{
return fTools::less(getStart().getY(), rComp.getStart().getY());
}
}
// method for cut support
B2DPoint getCutPointForGivenY(double fGivenY)
{
// Calculate cut point locally (do not use interpolate) since it is numerically
// necessary to guarantee the new, equal Y-coordinate
const double fFactor((fGivenY - getStart().getY()) / getDeltaY());
const double fDeltaXNew(fFactor * getDeltaX());
return B2DPoint(getStart().getX() + fDeltaXNew, fGivenY);
}
};
//////////////////////////////////////////////////////////////////////////////
// define double linked list of edges (for fast random insert)
typedef ::std::list< TrDeEdgeEntry > TrDeEdgeEntries;
} // end of anonymous namespace
} // end of namespace basegfx
//////////////////////////////////////////////////////////////////////////////
namespace basegfx
{
namespace trapezoidhelper
{
// helper class to handle the complete trapezoid subdivision of a PolyPolygon
class TrapezoidSubdivider
{
private:
// local data
sal_uInt32 mnInitialEdgeEntryCount;
TrDeEdgeEntries maTrDeEdgeEntries;
::std::vector< B2DPoint > maPoints;
::std::vector< B2DPoint* > maNewPoints;
void addEdgeSorted(
TrDeEdgeEntries::iterator aCurrent,
const TrDeEdgeEntry& rNewEdge)
{
// Loop while new entry is bigger, use operator<
while(aCurrent != maTrDeEdgeEntries.end() && (*aCurrent) < rNewEdge)
{
aCurrent++;
}
// Insert before first which is smaller or equal or at end
maTrDeEdgeEntries.insert(aCurrent, rNewEdge);
}
bool splitEdgeAtGivenPoint(
TrDeEdgeEntries::reference aEdge,
const B2DPoint& rCutPoint,
TrDeEdgeEntries::iterator aCurrent)
{
// do not create edges without deltaY: do not split when start is identical
if(aEdge.getStart().equal(rCutPoint, fTools::getSmallValue()))
{
return false;
}
// do not create edges without deltaY: do not split when end is identical
if(aEdge.getEnd().equal(rCutPoint, fTools::getSmallValue()))
{
return false;
}
const double fOldDeltaYStart(rCutPoint.getY() - aEdge.getStart().getY());
if(fTools::lessOrEqual(fOldDeltaYStart, 0.0))
{
// do not split: the resulting edge would be horizontal
// correct it to new start point
aEdge.setStart(&rCutPoint);
return false;
}
const double fNewDeltaYStart(aEdge.getEnd().getY() - rCutPoint.getY());
if(fTools::lessOrEqual(fNewDeltaYStart, 0.0))
{
// do not split: the resulting edge would be horizontal
// correct it to new end point
aEdge.setEnd(&rCutPoint);
return false;
}
// Create new entry
const TrDeEdgeEntry aNewEdge(
&rCutPoint,
&aEdge.getEnd(),
aEdge.getSortValue());
// Correct old entry
aEdge.setEnd(&rCutPoint);
// Insert sorted (to avoid new sort)
addEdgeSorted(aCurrent, aNewEdge);
return true;
}
bool testAndCorrectEdgeIntersection(
TrDeEdgeEntries::reference aEdgeA,
TrDeEdgeEntries::reference aEdgeB,
TrDeEdgeEntries::iterator aCurrent)
{
// Exclude simple cases: same start or end point
if(aEdgeA.getStart().equal(aEdgeB.getStart(), fTools::getSmallValue()))
{
return false;
}
if(aEdgeA.getStart().equal(aEdgeB.getEnd(), fTools::getSmallValue()))
{
return false;
}
if(aEdgeA.getEnd().equal(aEdgeB.getStart(), fTools::getSmallValue()))
{
return false;
}
if(aEdgeA.getEnd().equal(aEdgeB.getEnd(), fTools::getSmallValue()))
{
return false;
}
// Exclude simple cases: one of the edges has no length anymore
if(aEdgeA.getStart().equal(aEdgeA.getEnd(), fTools::getSmallValue()))
{
return false;
}
if(aEdgeB.getStart().equal(aEdgeB.getEnd(), fTools::getSmallValue()))
{
return false;
}
// check if one point is on the other edge (a touch, not a cut)
const B2DVector aDeltaB(aEdgeB.getDeltaX(), aEdgeB.getDeltaY());
if(tools::isPointOnEdge(aEdgeA.getStart(), aEdgeB.getStart(), aDeltaB))
{
return splitEdgeAtGivenPoint(aEdgeB, aEdgeA.getStart(), aCurrent);
}
if(tools::isPointOnEdge(aEdgeA.getEnd(), aEdgeB.getStart(), aDeltaB))
{
return splitEdgeAtGivenPoint(aEdgeB, aEdgeA.getEnd(), aCurrent);
}
const B2DVector aDeltaA(aEdgeA.getDeltaX(), aEdgeA.getDeltaY());
if(tools::isPointOnEdge(aEdgeB.getStart(), aEdgeA.getStart(), aDeltaA))
{
return splitEdgeAtGivenPoint(aEdgeA, aEdgeB.getStart(), aCurrent);
}
if(tools::isPointOnEdge(aEdgeB.getEnd(), aEdgeA.getStart(), aDeltaA))
{
return splitEdgeAtGivenPoint(aEdgeA, aEdgeB.getEnd(), aCurrent);
}
// check for cut inside edges. Use both t-values to choose the more precise
// one later
double fCutA(0.0);
double fCutB(0.0);
if(tools::findCut(
aEdgeA.getStart(), aDeltaA,
aEdgeB.getStart(), aDeltaB,
CUTFLAG_LINE,
&fCutA,
&fCutB))
{
// use a simple metric (length criteria) for choosing the numerically
// better cut
const double fSimpleLengthA(aDeltaA.getX() + aDeltaA.getY());
const double fSimpleLengthB(aDeltaB.getX() + aDeltaB.getY());
const bool bAIsLonger(fSimpleLengthA > fSimpleLengthB);
B2DPoint* pNewPoint = bAIsLonger
? new B2DPoint(aEdgeA.getStart() + (fCutA * aDeltaA))
: new B2DPoint(aEdgeB.getStart() + (fCutB * aDeltaB));
bool bRetval(false);
// try to split both edges
bRetval = splitEdgeAtGivenPoint(aEdgeA, *pNewPoint, aCurrent);
bRetval |= splitEdgeAtGivenPoint(aEdgeB, *pNewPoint, aCurrent);
if(bRetval)
{
maNewPoints.push_back(pNewPoint);
}
else
{
delete pNewPoint;
}
return bRetval;
}
return false;
}
void solveHorizontalEdges(TrDeSimpleEdges& rTrDeSimpleEdges)
{
if(rTrDeSimpleEdges.size() && maTrDeEdgeEntries.size())
{
// there were horizontal edges. These can be excluded, but
// cuts with other edges need to be solved and added before
// ignoring them
sal_uInt32 a(0);
for(a = 0; a < rTrDeSimpleEdges.size(); a++)
{
// get horizontal edge as candidate; prepare it's range and fixed Y
const TrDeSimpleEdge& rHorEdge = rTrDeSimpleEdges[a];
const B1DRange aRange(rHorEdge.getStart().getX(), rHorEdge.getEnd().getX());
const double fFixedY(rHorEdge.getStart().getY());
// loop over traversing edges
TrDeEdgeEntries::iterator aCurrent(maTrDeEdgeEntries.begin());
do
{
// get compare edge
TrDeEdgeEntries::reference aCompare(*aCurrent++);
if(fTools::lessOrEqual(aCompare.getEnd().getY(), fFixedY))
{
// edge ends above horizontal edge, continue
continue;
}
if(fTools::moreOrEqual(aCompare.getStart().getY(), fFixedY))
{
// edge starts below horizontal edge, continue
continue;
}
// vertical overlap, get horizontal range
const B1DRange aCompareRange(aCompare.getStart().getX(), aCompare.getEnd().getX());
if(aRange.overlaps(aCompareRange))
{
// possible cut, get cut point
const B2DPoint aSplit(aCompare.getCutPointForGivenY(fFixedY));
if(fTools::more(aSplit.getX(), aRange.getMinimum())
&& fTools::less(aSplit.getX(), aRange.getMaximum()))
{
// cut is in XRange of horizontal edge, potenitally needed cut
B2DPoint* pNewPoint = new B2DPoint(aSplit);
if(splitEdgeAtGivenPoint(aCompare, *pNewPoint, aCurrent))
{
maNewPoints.push_back(pNewPoint);
}
else
{
delete pNewPoint;
}
}
}
}
while(aCurrent != maTrDeEdgeEntries.end()
&& fTools::less(aCurrent->getStart().getY(), fFixedY));
}
}
}
public:
TrapezoidSubdivider(
const B2DPolyPolygon& rSourcePolyPolygon)
: mnInitialEdgeEntryCount(0),
maTrDeEdgeEntries(),
maPoints(),
maNewPoints()
{
B2DPolyPolygon aSource(rSourcePolyPolygon);
const sal_uInt32 nPolygonCount(rSourcePolyPolygon.count());
TrDeSimpleEdges aTrDeSimpleEdges;
sal_uInt32 a(0), b(0);
sal_uInt32 nAllPointCount(0);
// ensure there are no curves used
if(aSource.areControlPointsUsed())
{
aSource = aSource.getDefaultAdaptiveSubdivision();
}
for(a = 0; a < nPolygonCount; a++)
{
// 1st run: count points
const B2DPolygon aPolygonCandidate(aSource.getB2DPolygon(a));
const sal_uInt32 nCount(aPolygonCandidate.count());
if(nCount > 2)
{
nAllPointCount += nCount;
}
}
if(nAllPointCount)
{
// reserve needed points. CAUTION: maPoints size is NOT to be changed anymore
// after 2nd loop since pointers to it are used in the edges
maPoints.reserve(nAllPointCount);
for(a = 0; a < nPolygonCount; a++)
{
// 2nd run: add points
const B2DPolygon aPolygonCandidate(aSource.getB2DPolygon(a));
const sal_uInt32 nCount(aPolygonCandidate.count());
if(nCount > 2)
{
for(b = 0; b < nCount; b++)
{
maPoints.push_back(aPolygonCandidate.getB2DPoint(b));
}
}
}
// Moved the edge construction to a 3rd run: doing it in the 2nd run is
// possible(and i used it), but requires a working vector::reserve()
// implementation, else the vector will be reallocated and the pointers
// in the edges may be wrong. Security first here.
sal_uInt32 nStartIndex(0);
for(a = 0; a < nPolygonCount; a++)
{
const B2DPolygon aPolygonCandidate(aSource.getB2DPolygon(a));
const sal_uInt32 nCount(aPolygonCandidate.count());
if(nCount > 2)
{
// get the last point of the current polygon
B2DPoint* pPrev(&maPoints[nCount + nStartIndex - 1]);
for(b = 0; b < nCount; b++)
{
// get next point
B2DPoint* pCurr(&maPoints[nStartIndex++]);
if(fTools::equal(pPrev->getY(), pCurr->getY(), fTools::getSmallValue()))
{
// horizontal edge, check for single point
if(!fTools::equal(pPrev->getX(), pCurr->getX(), fTools::getSmallValue()))
{
// X-order not needed, just add
aTrDeSimpleEdges.push_back(TrDeSimpleEdge(pPrev, pCurr));
const double fMiddle((pPrev->getY() + pCurr->getY()) * 0.5);
pPrev->setY(fMiddle);
pCurr->setY(fMiddle);
}
}
else
{
// vertical edge. Positive Y-direction is guaranteed by the
// TrDeEdgeEntry constructor
maTrDeEdgeEntries.push_back(TrDeEdgeEntry(pPrev, pCurr, 0));
mnInitialEdgeEntryCount++;
}
// prepare next step
pPrev = pCurr;
}
}
}
}
if(maTrDeEdgeEntries.size())
{
// single and initial sort of traversing edges
maTrDeEdgeEntries.sort();
// solve horizontal edges if there are any detected
solveHorizontalEdges(aTrDeSimpleEdges);
}
}
~TrapezoidSubdivider()
{
// delete the extra points created for cuts
const sal_uInt32 nCount(maNewPoints.size());
for(sal_uInt32 a(0); a < nCount; a++)
{
delete maNewPoints[a];
}
}
void Subdivide(B2DTrapezoidVector& ro_Result)
{
// This is the central subdivider. The strategy is to use the first two entries
// from the traversing edges as a potential trapezoid and do the needed corrections
// and adaptions on the way.
//
// There always must be two edges with the same YStart value: When adding the polygons
// in the constructor, there is always a topmost point from which two edges start; when
// the topmost is an edge, there is a start and end of this edge from which two edges
// start. All cases have two edges with same StartY (QED).
//
// Based on this these edges get corrected when:
// - one is longer than the other
// - they intersect
// - they intersect with other edges
// - another edge starts inside the thought trapezoid
//
// All this cases again produce a valid state so that the first two edges have a common
// Ystart again. Some cases lead to a restart of the process, some allow consuming the
// edges and create the intended trapezoid.
//
// Be careful when doing chages here: It is essential to keep all possible paths
// in valid states and to be numerically correct. This is especially needed e.g.
// by using fTools::equal(..) in the more robust small-value incarnation.
B1DRange aLeftRange;
B1DRange aRightRange;
if(!maTrDeEdgeEntries.empty())
{
// measuring shows that the relation between edges and created trapezoids is
// mostly in the 1:1 range, thus reserve as much trapezoids as edges exist. Do
// not use maTrDeEdgeEntries.size() since that may be a non-constant time
// operation for Lists. Instead, use mnInitialEdgeEntryCount which will contain
// the roughly counted adds to the List
ro_Result.reserve(ro_Result.size() + mnInitialEdgeEntryCount);
}
while(!maTrDeEdgeEntries.empty())
{
// Prepare current operator and get first edge
TrDeEdgeEntries::iterator aCurrent(maTrDeEdgeEntries.begin());
TrDeEdgeEntries::reference aLeft(*aCurrent++);
if(aCurrent == maTrDeEdgeEntries.end())
{
// Should not happen: No 2nd edge; consume the single edge
// to not have an endless loop and start next. During development
// i constantly had breakpoints here, so i am sure enough to add an
// assertion here
OSL_ENSURE(false, "Trapeziod decomposer in illegal state (!)");
maTrDeEdgeEntries.pop_front();
continue;
}
// get second edge
TrDeEdgeEntries::reference aRight(*aCurrent++);
if(!fTools::equal(aLeft.getStart().getY(), aRight.getStart().getY(), fTools::getSmallValue()))
{
// Should not happen: We have a 2nd edge, but YStart is on another
// line; consume the single edge to not have an endless loop and start
// next. During development i constantly had breakpoints here, so i am
// sure enough to add an assertion here
OSL_ENSURE(false, "Trapeziod decomposer in illegal state (!)");
maTrDeEdgeEntries.pop_front();
continue;
}
// aLeft and aRight build a thought trapezoid now. They have a common
// start line (same Y for start points). Potentially, one of the edges
// is longer than the other. It is only needed to look at the shorter
// length which build the potential trapezoid. To do so, get the end points
// locally and adapt the evtl. longer one. Use only aLeftEnd and aRightEnd
// from here on, not the aLeft.getEnd() or aRight.getEnd() accesses.
B2DPoint aLeftEnd(aLeft.getEnd());
B2DPoint aRightEnd(aRight.getEnd());
// check if end points are on the same line. If yes, no adaption
// needs to be prepared. Also remember which one actually is longer.
const bool bEndOnSameLine(fTools::equal(aLeftEnd.getY(), aRightEnd.getY(), fTools::getSmallValue()));
bool bLeftIsLonger(false);
if(!bEndOnSameLine)
{
// check which edge is longer and correct accordingly
bLeftIsLonger = fTools::more(aLeftEnd.getY(), aRightEnd.getY());
if(bLeftIsLonger)
{
aLeftEnd = aLeft.getCutPointForGivenY(aRightEnd.getY());
}
else
{
aRightEnd = aRight.getCutPointForGivenY(aLeftEnd.getY());
}
}
// check for same start and end points
const bool bSameStartPoint(aLeft.getStart().equal(aRight.getStart(), fTools::getSmallValue()));
const bool bSameEndPoint(aLeftEnd.equal(aRightEnd, fTools::getSmallValue()));
// check the simple case that the edges form a 'blind' edge (deadend)
if(bSameStartPoint && bSameEndPoint)
{
// correct the longer edge if prepared
if(!bEndOnSameLine)
{
if(bLeftIsLonger)
{
B2DPoint* pNewPoint = new B2DPoint(aLeftEnd);
if(splitEdgeAtGivenPoint(aLeft, *pNewPoint, aCurrent))
{
maNewPoints.push_back(pNewPoint);
}
else
{
delete pNewPoint;
}
}
else
{
B2DPoint* pNewPoint = new B2DPoint(aRightEnd);
if(splitEdgeAtGivenPoint(aRight, *pNewPoint, aCurrent))
{
maNewPoints.push_back(pNewPoint);
}
else
{
delete pNewPoint;
}
}
}
// consume both edges and start next run
maTrDeEdgeEntries.pop_front();
maTrDeEdgeEntries.pop_front();
continue;
}
// check if the edges self-intersect. This can only happen when
// start and end point are different
bool bRangesSet(false);
if(!(bSameStartPoint || bSameEndPoint))
{
// get XRanges of edges
aLeftRange = B1DRange(aLeft.getStart().getX(), aLeftEnd.getX());
aRightRange = B1DRange(aRight.getStart().getX(), aRightEnd.getX());
bRangesSet = true;
// use fast range test first
if(aLeftRange.overlaps(aRightRange))
{
// real cut test and correction. If correction was needed,
// start new run
if(testAndCorrectEdgeIntersection(aLeft, aRight, aCurrent))
{
continue;
}
}
}
// now we need to check if there are intersections with other edges
// or if other edges start inside the candidate trapezoid
if(aCurrent != maTrDeEdgeEntries.end()
&& fTools::less(aCurrent->getStart().getY(), aLeftEnd.getY()))
{
// get XRanges of edges
if(!bRangesSet)
{
aLeftRange = B1DRange(aLeft.getStart().getX(), aLeftEnd.getX());
aRightRange = B1DRange(aRight.getStart().getX(), aRightEnd.getX());
}
// build full XRange for fast check
B1DRange aAllRange(aLeftRange);
aAllRange.expand(aRightRange);
// prepare loop iterator; aCurrent needs to stay unchanged for
// eventual sorted insertions of new EdgeNodes. Also prepare stop flag
TrDeEdgeEntries::iterator aLoop(aCurrent);
bool bDone(false);
do
{
// get compare edge and it's XRange
TrDeEdgeEntries::reference aCompare(*aLoop++);
// avoid edges using the same start point as one of
// the edges. These can neither have their start point
// in the thought trapezoid nor cut with one of the edges
if(aCompare.getStart().equal(aRight.getStart(), fTools::getSmallValue()))
{
continue;
}
// get compare XRange
const B1DRange aCompareRange(aCompare.getStart().getX(), aCompare.getEnd().getX());
// use fast range test first
if(aAllRange.overlaps(aCompareRange))
{
// check for start point inside thought trapezoid
if(fTools::more(aCompare.getStart().getY(), aLeft.getStart().getY()))
{
// calculate the two possible split points at compare's Y
const B2DPoint aSplitLeft(aLeft.getCutPointForGivenY(aCompare.getStart().getY()));
const B2DPoint aSplitRight(aRight.getCutPointForGivenY(aCompare.getStart().getY()));
// check for start point of aCompare being inside thought
// trapezoid
if(aCompare.getStart().getX() >= aSplitLeft.getX() &&
aCompare.getStart().getX() <= aSplitRight.getX())
{
// is inside, correct and restart loop
B2DPoint* pNewLeft = new B2DPoint(aSplitLeft);
if(splitEdgeAtGivenPoint(aLeft, *pNewLeft, aCurrent))
{
maNewPoints.push_back(pNewLeft);
bDone = true;
}
else
{
delete pNewLeft;
}
B2DPoint* pNewRight = new B2DPoint(aSplitRight);
if(splitEdgeAtGivenPoint(aRight, *pNewRight, aCurrent))
{
maNewPoints.push_back(pNewRight);
bDone = true;
}
else
{
delete pNewRight;
}
}
}
if(!bDone && aLeftRange.overlaps(aCompareRange))
{
// test for concrete cut of compare edge with left edge
bDone = testAndCorrectEdgeIntersection(aLeft, aCompare, aCurrent);
}
if(!bDone && aRightRange.overlaps(aCompareRange))
{
// test for concrete cut of compare edge with Right edge
bDone = testAndCorrectEdgeIntersection(aRight, aCompare, aCurrent);
}
}
}
while(!bDone
&& aLoop != maTrDeEdgeEntries.end()
&& fTools::less(aLoop->getStart().getY(), aLeftEnd.getY()));
if(bDone)
{
// something needed to be changed; start next loop
continue;
}
}
// when we get here, the intended trapezoid can be used. It needs to
// be corrected, eventually (if prepared); but this is no reason not to
// use it in the same loop iteration
if(!bEndOnSameLine)
{
if(bLeftIsLonger)
{
B2DPoint* pNewPoint = new B2DPoint(aLeftEnd);
if(splitEdgeAtGivenPoint(aLeft, *pNewPoint, aCurrent))
{
maNewPoints.push_back(pNewPoint);
}
else
{
delete pNewPoint;
}
}
else
{
B2DPoint* pNewPoint = new B2DPoint(aRightEnd);
if(splitEdgeAtGivenPoint(aRight, *pNewPoint, aCurrent))
{
maNewPoints.push_back(pNewPoint);
}
else
{
delete pNewPoint;
}
}
}
// the two edges start at the same Y, they use the same DeltaY, they
// do not cut themselves and not any other edge in range. Create a
// B2DTrapezoid and consume both edges
ro_Result.push_back(
B2DTrapezoid(
aLeft.getStart().getX(),
aRight.getStart().getX(),
aLeft.getStart().getY(),
aLeftEnd.getX(),
aRightEnd.getX(),
aLeftEnd.getY()));
maTrDeEdgeEntries.pop_front();
maTrDeEdgeEntries.pop_front();
}
}
};
} // end of anonymous namespace
} // end of namespace basegfx
//////////////////////////////////////////////////////////////////////////////
namespace basegfx
{
B2DTrapezoid::B2DTrapezoid(
const double& rfTopXLeft,
const double& rfTopXRight,
const double& rfTopY,
const double& rfBottomXLeft,
const double& rfBottomXRight,
const double& rfBottomY)
: mfTopXLeft(rfTopXLeft),
mfTopXRight(rfTopXRight),
mfTopY(rfTopY),
mfBottomXLeft(rfBottomXLeft),
mfBottomXRight(rfBottomXRight),
mfBottomY(rfBottomY)
{
// guarantee mfTopXRight >= mfTopXLeft
if(mfTopXLeft > mfTopXRight)
{
std::swap(mfTopXLeft, mfTopXRight);
}
// guarantee mfBottomXRight >= mfBottomXLeft
if(mfBottomXLeft > mfBottomXRight)
{
std::swap(mfBottomXLeft, mfBottomXRight);
}
// guarantee mfBottomY >= mfTopY
if(mfTopY > mfBottomY)
{
std::swap(mfTopY, mfBottomY);
std::swap(mfTopXLeft, mfBottomXLeft);
std::swap(mfTopXRight, mfBottomXRight);
}
}
B2DPolygon B2DTrapezoid::getB2DPolygon() const
{
B2DPolygon aRetval;
aRetval.append(B2DPoint(getTopXLeft(), getTopY()));
aRetval.append(B2DPoint(getTopXRight(), getTopY()));
aRetval.append(B2DPoint(getBottomXRight(), getBottomY()));
aRetval.append(B2DPoint(getBottomXLeft(), getBottomY()));
aRetval.setClosed(true);
return aRetval;
}
} // end of namespace basegfx
//////////////////////////////////////////////////////////////////////////////
namespace basegfx
{
namespace tools
{
// convert Source PolyPolygon to trapezoids
void trapezoidSubdivide(B2DTrapezoidVector& ro_Result, const B2DPolyPolygon& rSourcePolyPolygon)
{
trapezoidhelper::TrapezoidSubdivider aTrapezoidSubdivider(rSourcePolyPolygon);
aTrapezoidSubdivider.Subdivide(ro_Result);
}
void createLineTrapezoidFromEdge(
B2DTrapezoidVector& ro_Result,
const B2DPoint& rPointA,
const B2DPoint& rPointB,
double fLineWidth)
{
if(fTools::lessOrEqual(fLineWidth, 0.0))
{
// no line witdh
return;
}
if(rPointA.equal(rPointB, fTools::getSmallValue()))
{
// points are equal, no edge
return;
}
const double fHalfLineWidth(0.5 * fLineWidth);
if(fTools::equal(rPointA.getX(), rPointB.getX(), fTools::getSmallValue()))
{
// vertical line
const double fLeftX(rPointA.getX() - fHalfLineWidth);
const double fRightX(rPointA.getX() + fHalfLineWidth);
ro_Result.push_back(
B2DTrapezoid(
fLeftX,
fRightX,
std::min(rPointA.getY(), rPointB.getY()),
fLeftX,
fRightX,
std::max(rPointA.getY(), rPointB.getY())));
}
else if(fTools::equal(rPointA.getY(), rPointB.getY(), fTools::getSmallValue()))
{
// horizontal line
const double fLeftX(std::min(rPointA.getX(), rPointB.getX()));
const double fRightX(std::max(rPointA.getX(), rPointB.getX()));
ro_Result.push_back(
B2DTrapezoid(
fLeftX,
fRightX,
rPointA.getY() - fHalfLineWidth,
fLeftX,
fRightX,
rPointA.getY() + fHalfLineWidth));
}
else
{
// diagonal line
// create perpendicular vector
const B2DVector aDelta(rPointB - rPointA);
B2DVector aPerpendicular(-aDelta.getY(), aDelta.getX());
aPerpendicular.setLength(fHalfLineWidth);
// create StartLow, StartHigh, EndLow and EndHigh
const B2DPoint aStartLow(rPointA + aPerpendicular);
const B2DPoint aStartHigh(rPointA - aPerpendicular);
const B2DPoint aEndHigh(rPointB - aPerpendicular);
const B2DPoint aEndLow(rPointB + aPerpendicular);
// create EdgeEntries
basegfx::trapezoidhelper::TrDeEdgeEntries aTrDeEdgeEntries;
aTrDeEdgeEntries.push_back(basegfx::trapezoidhelper::TrDeEdgeEntry(&aStartLow, &aStartHigh, 0));
aTrDeEdgeEntries.push_back(basegfx::trapezoidhelper::TrDeEdgeEntry(&aStartHigh, &aEndHigh, 0));
aTrDeEdgeEntries.push_back(basegfx::trapezoidhelper::TrDeEdgeEntry(&aEndHigh, &aEndLow, 0));
aTrDeEdgeEntries.push_back(basegfx::trapezoidhelper::TrDeEdgeEntry(&aEndLow, &aStartLow, 0));
aTrDeEdgeEntries.sort();
// here we know we have exactly four edges, and they do not cut, touch or
// intersect. This makes processing much easier. Get the first two as start
// edges for the thought trapezoid
basegfx::trapezoidhelper::TrDeEdgeEntries::iterator aCurrent(aTrDeEdgeEntries.begin());
basegfx::trapezoidhelper::TrDeEdgeEntries::reference aLeft(*aCurrent++);
basegfx::trapezoidhelper::TrDeEdgeEntries::reference aRight(*aCurrent++);
const bool bEndOnSameLine(fTools::equal(aLeft.getEnd().getY(), aRight.getEnd().getY(), fTools::getSmallValue()));
if(bEndOnSameLine)
{
// create two triangle trapezoids
ro_Result.push_back(
B2DTrapezoid(
aLeft.getStart().getX(),
aRight.getStart().getX(),
aLeft.getStart().getY(),
aLeft.getEnd().getX(),
aRight.getEnd().getX(),
aLeft.getEnd().getY()));
basegfx::trapezoidhelper::TrDeEdgeEntries::reference aLeft2(*aCurrent++);
basegfx::trapezoidhelper::TrDeEdgeEntries::reference aRight2(*aCurrent++);
ro_Result.push_back(
B2DTrapezoid(
aLeft2.getStart().getX(),
aRight2.getStart().getX(),
aLeft2.getStart().getY(),
aLeft2.getEnd().getX(),
aRight2.getEnd().getX(),
aLeft2.getEnd().getY()));
}
else
{
// create three trapezoids. Check which edge is longer and
// correct accordingly
const bool bLeftIsLonger(fTools::more(aLeft.getEnd().getY(), aRight.getEnd().getY()));
if(bLeftIsLonger)
{
basegfx::trapezoidhelper::TrDeEdgeEntries::reference aRight2(*aCurrent++);
basegfx::trapezoidhelper::TrDeEdgeEntries::reference aLeft2(*aCurrent++);
const B2DPoint aSplitLeft(aLeft.getCutPointForGivenY(aRight.getEnd().getY()));
const B2DPoint aSplitRight(aRight2.getCutPointForGivenY(aLeft.getEnd().getY()));
ro_Result.push_back(
B2DTrapezoid(
aLeft.getStart().getX(),
aRight.getStart().getX(),
aLeft.getStart().getY(),
aSplitLeft.getX(),
aRight.getEnd().getX(),
aRight.getEnd().getY()));
ro_Result.push_back(
B2DTrapezoid(
aSplitLeft.getX(),
aRight.getEnd().getX(),
aRight.getEnd().getY(),
aLeft2.getStart().getX(),
aSplitRight.getX(),
aLeft2.getStart().getY()));
ro_Result.push_back(
B2DTrapezoid(
aLeft2.getStart().getX(),
aSplitRight.getX(),
aLeft2.getStart().getY(),
aLeft2.getEnd().getX(),
aRight2.getEnd().getX(),
aLeft2.getEnd().getY()));
}
else
{
basegfx::trapezoidhelper::TrDeEdgeEntries::reference aLeft2(*aCurrent++);
basegfx::trapezoidhelper::TrDeEdgeEntries::reference aRight2(*aCurrent++);
const B2DPoint aSplitRight(aRight.getCutPointForGivenY(aLeft.getEnd().getY()));
const B2DPoint aSplitLeft(aLeft2.getCutPointForGivenY(aRight.getEnd().getY()));
ro_Result.push_back(
B2DTrapezoid(
aLeft.getStart().getX(),
aRight.getStart().getX(),
aLeft.getStart().getY(),
aLeft.getEnd().getX(),
aSplitRight.getX(),
aLeft.getEnd().getY()));
ro_Result.push_back(
B2DTrapezoid(
aLeft.getEnd().getX(),
aSplitRight.getX(),
aLeft.getEnd().getY(),
aSplitLeft.getX(),
aRight.getEnd().getX(),
aRight2.getStart().getY()));
ro_Result.push_back(
B2DTrapezoid(
aSplitLeft.getX(),
aRight.getEnd().getX(),
aRight2.getStart().getY(),
aLeft2.getEnd().getX(),
aRight2.getEnd().getX(),
aLeft2.getEnd().getY()));
}
}
}
}
void createLineTrapezoidFromB2DPolygon(
B2DTrapezoidVector& ro_Result,
const B2DPolygon& rPolygon,
double fLineWidth)
{
if(fTools::lessOrEqual(fLineWidth, 0.0))
{
return;
}
// ensure there are no curves used
B2DPolygon aSource(rPolygon);
if(aSource.areControlPointsUsed())
{
const double fPrecisionFactor = 0.25;
aSource = adaptiveSubdivideByDistance( aSource, fLineWidth * fPrecisionFactor );
}
const sal_uInt32 nPointCount(aSource.count());
if(!nPointCount)
{
return;
}
const sal_uInt32 nEdgeCount(aSource.isClosed() ? nPointCount : nPointCount - 1);
B2DPoint aCurrent(aSource.getB2DPoint(0));
ro_Result.reserve(ro_Result.size() + (3 * nEdgeCount));
for(sal_uInt32 a(0); a < nEdgeCount; a++)
{
const sal_uInt32 nNextIndex((a + 1) % nPointCount);
const B2DPoint aNext(aSource.getB2DPoint(nNextIndex));
createLineTrapezoidFromEdge(ro_Result, aCurrent, aNext, fLineWidth);
aCurrent = aNext;
}
}
void createLineTrapezoidFromB2DPolyPolygon(
B2DTrapezoidVector& ro_Result,
const B2DPolyPolygon& rPolyPolygon,
double fLineWidth)
{
if(fTools::lessOrEqual(fLineWidth, 0.0))
{
return;
}
// ensure there are no curves used
B2DPolyPolygon aSource(rPolyPolygon);
if(aSource.areControlPointsUsed())
{
aSource = aSource.getDefaultAdaptiveSubdivision();
}
const sal_uInt32 nCount(aSource.count());
if(!nCount)
{
return;
}
for(sal_uInt32 a(0); a < nCount; a++)
{
createLineTrapezoidFromB2DPolygon(
ro_Result,
aSource.getB2DPolygon(a),
fLineWidth);
}
}
} // end of namespace tools
} // end of namespace basegfx
//////////////////////////////////////////////////////////////////////////////
// eof