summaryrefslogtreecommitdiff
path: root/basegfx/source/polygon/b2dtrapezoid.cxx
diff options
context:
space:
mode:
authorArmin Le Grand <Armin.Le.Grand@Sun.COM>2010-01-06 11:25:16 +0100
committerArmin Le Grand <Armin.Le.Grand@Sun.COM>2010-01-06 11:25:16 +0100
commit18ae13f478c25da4852799fd8d2595ed0a695494 (patch)
tree0899ea720e2719cbd986a79207717395ad4fb103 /basegfx/source/polygon/b2dtrapezoid.cxx
parent3e659f82dedbb5ddeb2814ce5267445234f7e7fd (diff)
aw079: #i107360# Added functionality for edges, polygons and polypolygons
Diffstat (limited to 'basegfx/source/polygon/b2dtrapezoid.cxx')
-rw-r--r--basegfx/source/polygon/b2dtrapezoid.cxx502
1 files changed, 417 insertions, 85 deletions
diff --git a/basegfx/source/polygon/b2dtrapezoid.cxx b/basegfx/source/polygon/b2dtrapezoid.cxx
index e935545e0b05..4cd63f938114 100644
--- a/basegfx/source/polygon/b2dtrapezoid.cxx
+++ b/basegfx/source/polygon/b2dtrapezoid.cxx
@@ -42,14 +42,20 @@ 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)
@@ -65,13 +71,19 @@ namespace basegfx
//////////////////////////////////////////////////////////////////////////////
// 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:
@@ -79,7 +91,8 @@ namespace basegfx
double getDeltaX() const { return mpEnd->getX() - mpStart->getX(); }
double getDeltaY() const { return mpEnd->getY() - mpStart->getY(); }
- // convenience data read access
+ // convenience data read access. SortValue is created on demand since
+ // it is not always used
sal_uInt32 getSortValue() const
{
if(0 != mnSortValue)
@@ -95,21 +108,29 @@ namespace basegfx
return mnSortValue;
}
- // constructor
+ // constructor. SortValue can be given when known, use zero otherwise
TrDeEdgeEntry(
const B2DPoint* pStart,
const B2DPoint* pEnd,
- sal_uInt32 nSortValue)
+ sal_uInt32 nSortValue = 0)
: TrDeSimpleEdge(pStart, pEnd),
mnSortValue(nSortValue)
{
- // no horizontal edges allowed, all neeed to traverse vertivally
+ // 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
+ // data write access to StartPoint
void setStart( const B2DPoint* pNewStart)
{
+ OSL_ENSURE(0 != pNewStart, "No null pointer allowed here (!)");
+
if(mpStart != pNewStart)
{
mpStart = pNewStart;
@@ -119,8 +140,11 @@ namespace basegfx
}
}
+ // data write access to EndPoint
void setEnd( const B2DPoint* pNewEnd)
{
+ OSL_ENSURE(0 != pNewEnd, "No null pointer allowed here (!)");
+
if(mpEnd != pNewEnd)
{
mpEnd = pNewEnd;
@@ -130,7 +154,7 @@ namespace basegfx
}
}
- // operator for sort support
+ // 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()))
@@ -138,9 +162,11 @@ namespace basegfx
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 derived from atan2 in the range ]0.0 .. pi[ 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 resides.
+ // 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
@@ -154,10 +180,21 @@ namespace basegfx
}
}
+ // 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
@@ -169,10 +206,12 @@ namespace basegfx
{
namespace trapezoidhelper
{
+ // helper class to handle the complete trapezoid subdivision of a PolyPolygon
class TrapezoidSubdivider
{
private:
- sal_uInt32 mnEdgeEntryCount;
+ // local data
+ sal_uInt32 mnInitialEdgeEntryCount;
TrDeEdgeEntries maTrDeEdgeEntries;
::std::vector< B2DPoint > maPoints;
::std::vector< B2DPoint* > maNewPoints;
@@ -189,7 +228,6 @@ namespace basegfx
// Insert before first which is smaller or equal or at end
maTrDeEdgeEntries.insert(aCurrent, rNewEdge);
- mnEdgeEntryCount++;
}
bool splitEdgeAtGivenPoint(
@@ -197,11 +235,13 @@ namespace basegfx
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;
@@ -222,6 +262,7 @@ namespace basegfx
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;
}
@@ -278,7 +319,7 @@ namespace basegfx
return false;
}
- // now check if one point is on the other edge
+ // 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))
@@ -303,7 +344,8 @@ namespace basegfx
return splitEdgeAtGivenPoint(aEdgeA, aEdgeB.getEnd(), aCurrent);
}
- // check for cut inside edges
+ // check for cut inside edges. Use both t-values to choose the more precise
+ // one later
double fCutA(0.0);
double fCutB(0.0);
@@ -314,6 +356,8 @@ namespace basegfx
&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);
@@ -322,6 +366,7 @@ namespace basegfx
: new B2DPoint(aEdgeB.getStart() + (fCutB * aDeltaB));
bool bRetval(false);
+ // try to split both edges
bRetval = splitEdgeAtGivenPoint(aEdgeA, *pNewPoint, aCurrent);
bRetval |= splitEdgeAtGivenPoint(aEdgeB, *pNewPoint, aCurrent);
@@ -340,24 +385,13 @@ namespace basegfx
return false;
}
- B2DPoint getCutPointForGivenY(
- const TrDeEdgeEntry& rEdge,
- 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 - rEdge.getStart().getY()) / rEdge.getDeltaY());
- const double fDeltaXNew(fFactor * rEdge.getDeltaX());
-
- return B2DPoint(rEdge.getStart().getX() + fDeltaXNew, fGivenY);
- }
-
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
+ // cuts with other edges need to be solved and added before
+ // ignoring them
sal_uInt32 a(0);
for(a = 0; a < rTrDeSimpleEdges.size(); a++)
@@ -367,7 +401,7 @@ namespace basegfx
const B1DRange aRange(rHorEdge.getStart().getX(), rHorEdge.getEnd().getX());
const double fFixedY(rHorEdge.getStart().getY());
- // loop over edges
+ // loop over traversing edges
TrDeEdgeEntries::iterator aCurrent(maTrDeEdgeEntries.begin());
do
@@ -375,15 +409,15 @@ namespace basegfx
// get compare edge
TrDeEdgeEntries::reference aCompare(*aCurrent++);
- if(fTools::moreOrEqual(aCompare.getStart().getY(), fFixedY))
+ if(fTools::lessOrEqual(aCompare.getEnd().getY(), fFixedY))
{
- // edge starts below horizontal edge, continue
+ // edge ends above horizontal edge, continue
continue;
}
- if(fTools::lessOrEqual(aCompare.getEnd().getY(), fFixedY))
+ if(fTools::moreOrEqual(aCompare.getStart().getY(), fFixedY))
{
- // edge ends above horizontal edge, continue
+ // edge starts below horizontal edge, continue
continue;
}
@@ -393,7 +427,7 @@ namespace basegfx
if(aRange.overlaps(aCompareRange))
{
// possible cut, get cut point
- const B2DPoint aSplit(getCutPointForGivenY(aCompare, fFixedY));
+ const B2DPoint aSplit(aCompare.getCutPointForGivenY(fFixedY));
if(fTools::more(aSplit.getX(), aRange.getMinimum())
&& fTools::less(aSplit.getX(), aRange.getMaximum()))
@@ -421,19 +455,27 @@ namespace basegfx
public:
TrapezoidSubdivider(
const B2DPolyPolygon& rSourcePolyPolygon)
- : mnEdgeEntryCount(0),
+ : 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++)
{
- const B2DPolygon aPolygonCandidate(rSourcePolyPolygon.getB2DPolygon(a));
+ // 1st run: count points
+ const B2DPolygon aPolygonCandidate(aSource.getB2DPolygon(a));
const sal_uInt32 nCount(aPolygonCandidate.count());
if(nCount > 2)
@@ -444,12 +486,14 @@ namespace basegfx
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);
- sal_uInt32 nStartIndex(0);
for(a = 0; a < nPolygonCount; a++)
{
- const B2DPolygon aPolygonCandidate(rSourcePolyPolygon.getB2DPolygon(a));
+ // 2nd run: add points
+ const B2DPolygon aPolygonCandidate(aSource.getB2DPolygon(a));
const sal_uInt32 nCount(aPolygonCandidate.count());
if(nCount > 2)
@@ -461,20 +505,25 @@ namespace basegfx
}
}
- // moved the edge construction to a 3rd loop; doing it in the 2nd loop is
- // possible, but requires q working vector::reserve() implementation, else
- // the vector will be reallocated and the pointers will be wrong
+ // 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(rSourcePolyPolygon.getB2DPolygon(a));
+ const B2DPolygon aPolygonCandidate(aSource.getB2DPolygon(a));
const sal_uInt32 nCount(aPolygonCandidate.count());
if(nCount > 2)
{
- B2DPoint* pPrev(&maPoints[maPoints.size() - 1]);
+ // 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()))
@@ -492,19 +541,13 @@ namespace basegfx
}
else
{
- // vertical edge, add with positive Y-direction
- if(pPrev->getY() < pCurr->getY())
- {
- maTrDeEdgeEntries.push_back(TrDeEdgeEntry(pPrev, pCurr, 0));
- }
- else
- {
- maTrDeEdgeEntries.push_back(TrDeEdgeEntry(pCurr, pPrev, 0));
- }
-
- mnEdgeEntryCount++;
+ // vertical edge. Positive Y-direction is guaranteed by the
+ // TrDeEdgeEntry constructor
+ maTrDeEdgeEntries.push_back(TrDeEdgeEntry(pPrev, pCurr, 0));
+ mnInitialEdgeEntryCount++;
}
+ // prepare next step
pPrev = pCurr;
}
}
@@ -513,14 +556,17 @@ namespace basegfx
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++)
@@ -529,20 +575,41 @@ namespace basegfx
}
}
- B2DTrapezoidVector Subdivide()
+ void Subdivide(B2DTrapezoidVector& ro_Result)
{
- B2DTrapezoidVector aRetval;
+ // 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.0 range, thus reserve as much trapezoids as edges exist. Do
+ // 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 mnEdgeEntryCount which will contain the
- // roughly counted adds to the List
- aRetval.reserve(mnEdgeEntryCount);
+ // 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())
@@ -554,7 +621,10 @@ namespace basegfx
if(aCurrent == maTrDeEdgeEntries.end())
{
// Should not happen: No 2nd edge; consume the single edge
- // and start next loop
+ // 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;
}
@@ -565,7 +635,10 @@ namespace basegfx
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 and start next loop
+ // 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;
}
@@ -573,13 +646,14 @@ namespace basegfx
// 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 traezoid. To do so, get the end points
- // locally and adapt the evtl. longer one
+ // 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
+ // 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);
@@ -590,11 +664,11 @@ namespace basegfx
if(bLeftIsLonger)
{
- aLeftEnd = getCutPointForGivenY(aLeft, aRightEnd.getY());
+ aLeftEnd = aLeft.getCutPointForGivenY(aRightEnd.getY());
}
else
{
- aRightEnd = getCutPointForGivenY(aRight, aLeftEnd.getY());
+ aRightEnd = aRight.getCutPointForGivenY(aLeftEnd.getY());
}
}
@@ -602,7 +676,7 @@ namespace basegfx
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
+ // check the simple case that the edges form a 'blind' edge (deadend)
if(bSameStartPoint && bSameEndPoint)
{
// correct the longer edge if prepared
@@ -657,7 +731,7 @@ namespace basegfx
// use fast range test first
if(aLeftRange.overlaps(aRightRange))
{
- // real cut test and correction. If corrected,
+ // real cut test and correction. If correction was needed,
// start new run
if(testAndCorrectEdgeIntersection(aLeft, aRight, aCurrent))
{
@@ -676,7 +750,6 @@ namespace basegfx
{
aLeftRange = B1DRange(aLeft.getStart().getX(), aLeftEnd.getX());
aRightRange = B1DRange(aRight.getStart().getX(), aRightEnd.getX());
- bRangesSet = true;
}
// build full XRange for fast check
@@ -684,7 +757,7 @@ namespace basegfx
aAllRange.expand(aRightRange);
// prepare loop iterator; aCurrent needs to stay unchanged for
- // eventual insertions of new EdgeNodes. Also prepare stop flag
+ // eventual sorted insertions of new EdgeNodes. Also prepare stop flag
TrDeEdgeEntries::iterator aLoop(aCurrent);
bool bDone(false);
@@ -695,7 +768,7 @@ namespace basegfx
// avoid edges using the same start point as one of
// the edges. These can neither have their start point
- // in the thought edge nor cut with one of the edges
+ // in the thought trapezoid nor cut with one of the edges
if(aCompare.getStart().equal(aRight.getStart(), fTools::getSmallValue()))
{
continue;
@@ -704,15 +777,15 @@ namespace basegfx
// get compare XRange
const B1DRange aCompareRange(aCompare.getStart().getX(), aCompare.getEnd().getX());
- // use fast range test
+ // 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(getCutPointForGivenY(aLeft, aCompare.getStart().getY()));
- const B2DPoint aSplitRight(getCutPointForGivenY(aRight, aCompare.getStart().getY()));
+ 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
@@ -806,7 +879,7 @@ namespace basegfx
// 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
- aRetval.push_back(
+ ro_Result.push_back(
B2DTrapezoid(
aLeft.getStart().getX(),
aRight.getStart().getX(),
@@ -818,8 +891,6 @@ namespace basegfx
maTrDeEdgeEntries.pop_front();
maTrDeEdgeEntries.pop_front();
}
-
- return aRetval;
}
};
} // end of anonymous namespace
@@ -836,23 +907,32 @@ namespace basegfx
const double& rfBottomXLeft,
const double& rfBottomXRight,
const double& rfBottomY)
- :
- mfTopXLeft(rfTopXLeft),
+ : mfTopXLeft(rfTopXLeft),
mfTopXRight(rfTopXRight),
mfTopY(rfTopY),
mfBottomXLeft(rfBottomXLeft),
mfBottomXRight(rfBottomXRight),
mfBottomY(rfBottomY)
{
- if(rfTopXLeft > rfTopXRight)
+ // guarantee mfTopXRight >= mfTopXLeft
+ if(mfTopXLeft > mfTopXRight)
{
std::swap(mfTopXLeft, mfTopXRight);
}
- if(rfBottomXLeft > rfBottomXRight)
+ // 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
@@ -875,19 +955,271 @@ namespace basegfx
{
namespace tools
{
- // convert SourcePolyPolygon to trapezoids
- B2DTrapezoidVector trapezoidSubdivide(const B2DPolyPolygon& rSourcePolyPolygon)
+ // 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)
{
- B2DPolyPolygon aSource(rSourcePolyPolygon);
+ if(fTools::lessOrEqual(fLineWidth, 0.0))
+ {
+ return;
+ }
+
+ // ensure there are no curves used
+ B2DPolygon aSource(rPolygon);
if(aSource.areControlPointsUsed())
{
aSource = aSource.getDefaultAdaptiveSubdivision();
}
- trapezoidhelper::TrapezoidSubdivider aTrapezoidSubdivider(aSource);
- return aTrapezoidSubdivider.Subdivide();
+ 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