xref: /trunk/main/basegfx/source/polygon/b2dtrapezoid.cxx (revision 52230ee9)

/**************************************************************
 *
 * 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 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

		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 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(0 != pNewStart, "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(0 != pNewEnd, "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(), 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 its 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, potentially 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 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. 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 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(), 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 width
				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