1163 lines
48 KiB
C++
1163 lines
48 KiB
C++
/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
|
|
/*
|
|
* This file is part of the LibreOffice project.
|
|
*
|
|
* This Source Code Form is subject to the terms of the Mozilla Public
|
|
* License, v. 2.0. If a copy of the MPL was not distributed with this
|
|
* file, You can obtain one at http://mozilla.org/MPL/2.0/.
|
|
*
|
|
* This file incorporates work covered by the following license notice:
|
|
*
|
|
* 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 .
|
|
*/
|
|
|
|
#include <basegfx/polygon/b2dtrapezoid.hxx>
|
|
#include <basegfx/range/b1drange.hxx>
|
|
#include <basegfx/polygon/b2dpolygontools.hxx>
|
|
#include <basegfx/polygon/b2dpolypolygon.hxx>
|
|
|
|
#include <osl/diagnose.h>
|
|
|
|
#include <list>
|
|
|
|
namespace basegfx::trapezoidhelper
|
|
{
|
|
|
|
// helper class to hold a simple edge. This is only used for horizontal edges
|
|
// currently, thus the YPositions will be equal. I did not create a special
|
|
// class for this since holding the pointers is more effective and also can be
|
|
// used as baseclass for the traversing edges
|
|
|
|
namespace {
|
|
|
|
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)
|
|
|
|
namespace {
|
|
|
|
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(mnSortValue != 0)
|
|
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 / M_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)
|
|
: TrDeSimpleEdge(pStart, pEnd),
|
|
mnSortValue(nSortValue)
|
|
{
|
|
// force traversal of deltaY downward
|
|
if(mpEnd->getY() < mpStart->getY())
|
|
{
|
|
std::swap(mpStart, mpEnd);
|
|
}
|
|
|
|
// no horizontal edges allowed, all need to traverse vertically
|
|
OSL_ENSURE(mpEnd->getY() > mpStart->getY(), "Illegal TrDeEdgeEntry constructed (!)");
|
|
}
|
|
|
|
// data write access to StartPoint
|
|
void setStart( const B2DPoint* pNewStart)
|
|
{
|
|
OSL_ENSURE(pNewStart != nullptr, "No null pointer allowed here (!)");
|
|
|
|
if(mpStart != pNewStart)
|
|
{
|
|
mpStart = pNewStart;
|
|
|
|
// no horizontal edges allowed, all need to traverse vertically
|
|
OSL_ENSURE(mpEnd->getY() > mpStart->getY(), "Illegal TrDeEdgeEntry constructed (!)");
|
|
}
|
|
}
|
|
|
|
// data write access to EndPoint
|
|
void setEnd( const B2DPoint* pNewEnd)
|
|
{
|
|
OSL_ENSURE(pNewEnd != nullptr, "No null pointer allowed here (!)");
|
|
|
|
if(mpEnd != pNewEnd)
|
|
{
|
|
mpEnd = pNewEnd;
|
|
|
|
// no horizontal edges allowed, all need to traverse vertically
|
|
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()))
|
|
{
|
|
if(fTools::equal(getStart().getX(), rComp.getStart().getX()))
|
|
{
|
|
// 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) const
|
|
{
|
|
// avoid div/0
|
|
if (getDeltaY() == 0)
|
|
return B2DPoint(getStart().getX(), 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;
|
|
|
|
|
|
|
|
// FIXME: templatize this and use it for TrDeEdgeEntries too ...
|
|
|
|
namespace {
|
|
|
|
/// Class to allow efficient allocation and release of B2DPoints
|
|
class PointBlockAllocator
|
|
{
|
|
static const size_t nBlockSize = 32;
|
|
size_t nCurPoint;
|
|
B2DPoint *mpPointBase;
|
|
/// Special case the first allocation to avoid it.
|
|
B2DPoint maFirstStackBlock[nBlockSize];
|
|
std::vector< B2DPoint * > maBlocks;
|
|
public:
|
|
PointBlockAllocator() :
|
|
nCurPoint( nBlockSize ),
|
|
mpPointBase( maFirstStackBlock )
|
|
{
|
|
}
|
|
|
|
~PointBlockAllocator()
|
|
{
|
|
while(!maBlocks.empty())
|
|
{
|
|
delete [] maBlocks.back();
|
|
maBlocks.pop_back();
|
|
}
|
|
}
|
|
|
|
B2DPoint *allocatePoint()
|
|
{
|
|
if(nCurPoint >= nBlockSize)
|
|
{
|
|
mpPointBase = new B2DPoint[nBlockSize];
|
|
maBlocks.push_back(mpPointBase);
|
|
nCurPoint = 0;
|
|
}
|
|
return mpPointBase + nCurPoint++;
|
|
}
|
|
|
|
B2DPoint *allocatePoint(const B2DTuple &rPoint)
|
|
{
|
|
B2DPoint *pPoint = allocatePoint();
|
|
*pPoint = rPoint;
|
|
return pPoint;
|
|
}
|
|
|
|
/// This is a very uncommon case but why not ...
|
|
void freeIfLast(B2DPoint const *pPoint)
|
|
{
|
|
// just re-use the last point if we can.
|
|
if ( nCurPoint > 0 && pPoint == mpPointBase + nCurPoint - 1 )
|
|
nCurPoint--;
|
|
}
|
|
};
|
|
|
|
// helper class to handle the complete trapezoid subdivision of a PolyPolygon
|
|
class TrapezoidSubdivider
|
|
{
|
|
private:
|
|
// local data
|
|
TrDeEdgeEntries maTrDeEdgeEntries;
|
|
std::vector< B2DPoint > maPoints;
|
|
/// new points allocated for cuts
|
|
PointBlockAllocator 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,
|
|
const TrDeEdgeEntries::iterator& aCurrent)
|
|
{
|
|
// do not create edges without deltaY: do not split when start is identical
|
|
if(aEdge.getStart().equal(rCutPoint))
|
|
{
|
|
return false;
|
|
}
|
|
|
|
// do not create edges without deltaY: do not split when end is identical
|
|
if(aEdge.getEnd().equal(rCutPoint))
|
|
{
|
|
return false;
|
|
}
|
|
|
|
const double fOldDeltaYStart(rCutPoint.getY() - aEdge.getStart().getY());
|
|
|
|
if(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(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,
|
|
const TrDeEdgeEntries::iterator& aCurrent)
|
|
{
|
|
// Exclude simple cases: same start or end point
|
|
if(aEdgeA.getStart().equal(aEdgeB.getStart()))
|
|
{
|
|
return false;
|
|
}
|
|
|
|
if(aEdgeA.getStart().equal(aEdgeB.getEnd()))
|
|
{
|
|
return false;
|
|
}
|
|
|
|
if(aEdgeA.getEnd().equal(aEdgeB.getStart()))
|
|
{
|
|
return false;
|
|
}
|
|
|
|
if(aEdgeA.getEnd().equal(aEdgeB.getEnd()))
|
|
{
|
|
return false;
|
|
}
|
|
|
|
// Exclude simple cases: one of the edges has no length anymore
|
|
if(aEdgeA.getStart().equal(aEdgeA.getEnd()))
|
|
{
|
|
return false;
|
|
}
|
|
|
|
if(aEdgeB.getStart().equal(aEdgeB.getEnd()))
|
|
{
|
|
return false;
|
|
}
|
|
|
|
// check if one point is on the other edge (a touch, not a cut)
|
|
const B2DVector aDeltaB(aEdgeB.getDeltaX(), aEdgeB.getDeltaY());
|
|
|
|
if(utils::isPointOnEdge(aEdgeA.getStart(), aEdgeB.getStart(), aDeltaB))
|
|
{
|
|
return splitEdgeAtGivenPoint(aEdgeB, aEdgeA.getStart(), aCurrent);
|
|
}
|
|
|
|
if(utils::isPointOnEdge(aEdgeA.getEnd(), aEdgeB.getStart(), aDeltaB))
|
|
{
|
|
return splitEdgeAtGivenPoint(aEdgeB, aEdgeA.getEnd(), aCurrent);
|
|
}
|
|
|
|
const B2DVector aDeltaA(aEdgeA.getDeltaX(), aEdgeA.getDeltaY());
|
|
|
|
if(utils::isPointOnEdge(aEdgeB.getStart(), aEdgeA.getStart(), aDeltaA))
|
|
{
|
|
return splitEdgeAtGivenPoint(aEdgeA, aEdgeB.getStart(), aCurrent);
|
|
}
|
|
|
|
if(utils::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(utils::findCut(
|
|
aEdgeA.getStart(), aDeltaA,
|
|
aEdgeB.getStart(), aDeltaB,
|
|
CutFlagValue::LINE,
|
|
&fCutA,
|
|
&fCutB) == CutFlagValue::NONE)
|
|
return false;
|
|
|
|
// 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
|
|
? maNewPoints.allocatePoint(aEdgeA.getStart() + (fCutA * aDeltaA))
|
|
: maNewPoints.allocatePoint(aEdgeB.getStart() + (fCutB * aDeltaB));
|
|
|
|
// try to split both edges
|
|
bool bRetval = splitEdgeAtGivenPoint(aEdgeA, *pNewPoint, aCurrent);
|
|
bRetval |= splitEdgeAtGivenPoint(aEdgeB, *pNewPoint, aCurrent);
|
|
|
|
if(!bRetval)
|
|
maNewPoints.freeIfLast(pNewPoint);
|
|
|
|
return bRetval;
|
|
}
|
|
|
|
void solveHorizontalEdges(TrDeSimpleEdges& rTrDeSimpleEdges)
|
|
{
|
|
if(rTrDeSimpleEdges.empty() || maTrDeEdgeEntries.empty())
|
|
return;
|
|
|
|
// there were horizontal edges. These can be excluded, but
|
|
// cuts with other edges need to be solved and added before
|
|
// ignoring them
|
|
for(const TrDeSimpleEdge & rHorEdge : rTrDeSimpleEdges)
|
|
{
|
|
// get horizontal edge as candidate; prepare its range and fixed Y
|
|
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, potentially needed cut
|
|
B2DPoint* pNewPoint = maNewPoints.allocatePoint(aSplit);
|
|
|
|
if(!splitEdgeAtGivenPoint(aCompare, *pNewPoint, aCurrent))
|
|
{
|
|
maNewPoints.freeIfLast(pNewPoint);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
while(aCurrent != maTrDeEdgeEntries.end()
|
|
&& fTools::less(aCurrent->getStart().getY(), fFixedY));
|
|
}
|
|
}
|
|
|
|
public:
|
|
explicit TrapezoidSubdivider(
|
|
const B2DPolyPolygon& rSourcePolyPolygon)
|
|
{
|
|
B2DPolyPolygon aSource(rSourcePolyPolygon);
|
|
TrDeSimpleEdges aTrDeSimpleEdges;
|
|
sal_uInt32 nAllPointCount(0);
|
|
|
|
// ensure there are no curves used
|
|
if(aSource.areControlPointsUsed())
|
|
{
|
|
aSource = aSource.getDefaultAdaptiveSubdivision();
|
|
}
|
|
|
|
for(const auto& aPolygonCandidate : std::as_const(aSource))
|
|
{
|
|
// 1st run: count points
|
|
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(const auto& aPolygonCandidate : std::as_const(aSource))
|
|
{
|
|
// 2nd run: add points
|
|
const sal_uInt32 nCount(aPolygonCandidate.count());
|
|
|
|
if(nCount > 2)
|
|
{
|
|
for(sal_uInt32 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(const auto& aPolygonCandidate : std::as_const(aSource))
|
|
{
|
|
const sal_uInt32 nCount(aPolygonCandidate.count());
|
|
|
|
if(nCount > 2)
|
|
{
|
|
// get the last point of the current polygon
|
|
B2DPoint* pPrev(&maPoints[nCount + nStartIndex - 1]);
|
|
|
|
for(sal_uInt32 b = 0; b < nCount; b++)
|
|
{
|
|
// get next point
|
|
B2DPoint* pCurr(&maPoints[nStartIndex++]);
|
|
|
|
if(fTools::equal(pPrev->getY(), pCurr->getY()))
|
|
{
|
|
// horizontal edge, check for single point
|
|
if(!fTools::equal(pPrev->getX(), pCurr->getX()))
|
|
{
|
|
// X-order not needed, just add
|
|
aTrDeSimpleEdges.emplace_back(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.emplace_back(pPrev, pCurr, 0);
|
|
}
|
|
|
|
// prepare next step
|
|
pPrev = pCurr;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
if(!maTrDeEdgeEntries.empty())
|
|
{
|
|
// single and initial sort of traversing edges
|
|
maTrDeEdgeEntries.sort();
|
|
|
|
// solve horizontal edges if there are any detected
|
|
solveHorizontalEdges(aTrDeSimpleEdges);
|
|
}
|
|
}
|
|
|
|
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 adaptations 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 changes 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.
|
|
ro_Result.reserve(ro_Result.size() + maTrDeEdgeEntries.size());
|
|
}
|
|
|
|
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_FAIL("Trapezoid decomposer in illegal state (!)");
|
|
maTrDeEdgeEntries.pop_front();
|
|
continue;
|
|
}
|
|
|
|
// get second edge
|
|
TrDeEdgeEntries::reference aRight(*aCurrent++);
|
|
|
|
if(!fTools::equal(aLeft.getStart().getY(), aRight.getStart().getY()))
|
|
{
|
|
// 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_FAIL("Trapezoid 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 adaptation
|
|
// needs to be prepared. Also remember which one actually is longer.
|
|
const bool bEndOnSameLine(fTools::equal(aLeftEnd.getY(), aRightEnd.getY()));
|
|
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()));
|
|
const bool bSameEndPoint(aLeftEnd.equal(aRightEnd));
|
|
|
|
// 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 = maNewPoints.allocatePoint(aLeftEnd);
|
|
|
|
if(!splitEdgeAtGivenPoint(aLeft, *pNewPoint, aCurrent))
|
|
{
|
|
maNewPoints.freeIfLast(pNewPoint);
|
|
}
|
|
}
|
|
else
|
|
{
|
|
B2DPoint* pNewPoint = maNewPoints.allocatePoint(aRightEnd);
|
|
|
|
if(!splitEdgeAtGivenPoint(aRight, *pNewPoint, aCurrent))
|
|
{
|
|
maNewPoints.freeIfLast(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
|
|
// possibly sorted insertions of new EdgeNodes. Also prepare stop flag
|
|
TrDeEdgeEntries::iterator aLoop(aCurrent);
|
|
bool bDone(false);
|
|
|
|
do
|
|
{
|
|
// get compare edge and its 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()))
|
|
{
|
|
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 = maNewPoints.allocatePoint(aSplitLeft);
|
|
|
|
if(splitEdgeAtGivenPoint(aLeft, *pNewLeft, aCurrent))
|
|
{
|
|
bDone = true;
|
|
}
|
|
else
|
|
{
|
|
maNewPoints.freeIfLast(pNewLeft);
|
|
}
|
|
|
|
B2DPoint* pNewRight = maNewPoints.allocatePoint(aSplitRight);
|
|
|
|
if(splitEdgeAtGivenPoint(aRight, *pNewRight, aCurrent))
|
|
{
|
|
bDone = true;
|
|
}
|
|
else
|
|
{
|
|
maNewPoints.freeIfLast(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 possibly (if prepared); but this is no reason not to
|
|
// use it in the same loop iteration
|
|
if(!bEndOnSameLine)
|
|
{
|
|
if(bLeftIsLonger)
|
|
{
|
|
B2DPoint* pNewPoint = maNewPoints.allocatePoint(aLeftEnd);
|
|
|
|
if(!splitEdgeAtGivenPoint(aLeft, *pNewPoint, aCurrent))
|
|
{
|
|
maNewPoints.freeIfLast(pNewPoint);
|
|
}
|
|
}
|
|
else
|
|
{
|
|
B2DPoint* pNewPoint = maNewPoints.allocatePoint(aRightEnd);
|
|
|
|
if(!splitEdgeAtGivenPoint(aRight, *pNewPoint, aCurrent))
|
|
{
|
|
maNewPoints.freeIfLast(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.emplace_back(
|
|
aLeft.getStart().getX(),
|
|
aRight.getStart().getX(),
|
|
aLeft.getStart().getY(),
|
|
aLeftEnd.getX(),
|
|
aRightEnd.getX(),
|
|
aLeftEnd.getY());
|
|
|
|
maTrDeEdgeEntries.pop_front();
|
|
maTrDeEdgeEntries.pop_front();
|
|
}
|
|
}
|
|
};
|
|
|
|
}
|
|
} // end of namespace
|
|
|
|
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::utils
|
|
{
|
|
// convert Source utils::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(fLineWidth <= 0.0)
|
|
{
|
|
// no line width
|
|
return;
|
|
}
|
|
|
|
if(rPointA.equal(rPointB))
|
|
{
|
|
// points are equal, no edge
|
|
return;
|
|
}
|
|
|
|
const double fHalfLineWidth(0.5 * fLineWidth);
|
|
|
|
if(fTools::equal(rPointA.getX(), rPointB.getX()))
|
|
{
|
|
// vertical line
|
|
const double fLeftX(rPointA.getX() - fHalfLineWidth);
|
|
const double fRightX(rPointA.getX() + fHalfLineWidth);
|
|
|
|
ro_Result.emplace_back(
|
|
fLeftX,
|
|
fRightX,
|
|
std::min(rPointA.getY(), rPointB.getY()),
|
|
fLeftX,
|
|
fRightX,
|
|
std::max(rPointA.getY(), rPointB.getY()));
|
|
}
|
|
else if(fTools::equal(rPointA.getY(), rPointB.getY()))
|
|
{
|
|
// horizontal line
|
|
const double fLeftX(std::min(rPointA.getX(), rPointB.getX()));
|
|
const double fRightX(std::max(rPointA.getX(), rPointB.getX()));
|
|
|
|
ro_Result.emplace_back(
|
|
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.emplace_back(&aStartLow, &aStartHigh, 0);
|
|
aTrDeEdgeEntries.emplace_back(&aStartHigh, &aEndHigh, 0);
|
|
aTrDeEdgeEntries.emplace_back(&aEndHigh, &aEndLow, 0);
|
|
aTrDeEdgeEntries.emplace_back(&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()));
|
|
|
|
if(bEndOnSameLine)
|
|
{
|
|
// create two triangle trapezoids
|
|
ro_Result.emplace_back(
|
|
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.emplace_back(
|
|
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.emplace_back(
|
|
aLeft.getStart().getX(),
|
|
aRight.getStart().getX(),
|
|
aLeft.getStart().getY(),
|
|
aSplitLeft.getX(),
|
|
aRight.getEnd().getX(),
|
|
aRight.getEnd().getY());
|
|
|
|
ro_Result.emplace_back(
|
|
aSplitLeft.getX(),
|
|
aRight.getEnd().getX(),
|
|
aRight.getEnd().getY(),
|
|
aLeft2.getStart().getX(),
|
|
aSplitRight.getX(),
|
|
aLeft2.getStart().getY());
|
|
|
|
ro_Result.emplace_back(
|
|
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.emplace_back(
|
|
aLeft.getStart().getX(),
|
|
aRight.getStart().getX(),
|
|
aLeft.getStart().getY(),
|
|
aLeft.getEnd().getX(),
|
|
aSplitRight.getX(),
|
|
aLeft.getEnd().getY());
|
|
|
|
ro_Result.emplace_back(
|
|
aLeft.getEnd().getX(),
|
|
aSplitRight.getX(),
|
|
aLeft.getEnd().getY(),
|
|
aSplitLeft.getX(),
|
|
aRight.getEnd().getX(),
|
|
aRight2.getStart().getY());
|
|
|
|
ro_Result.emplace_back(
|
|
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(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;
|
|
}
|
|
}
|
|
|
|
|
|
} // end of namespace
|
|
|
|
/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|