aw079: #i107360# Added functionality for edges, polygons and polypolygons

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