    /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
    /*
     * This file is part of the LibreOffice project.
     *
     * This Source Code Form is subject to the terms of the Mozilla Public
     * License, v. 2.0. If a copy of the MPL was not distributed with this
     * file, You can obtain one at http://mozilla.org/MPL/2.0/.
     *
     * This file incorporates work covered by the following license notice:
     *
     *   Licensed to the Apache Software Foundation (ASF) under one or more
     *   contributor license agreements. See the NOTICE file distributed
     *   with this work for additional information regarding copyright
     *   ownership. The ASF licenses this file to you under the Apache
     *   License, Version 2.0 (the "License"); you may not use this file
     *   except in compliance with the License. You may obtain a copy of
     *   the License at http://www.apache.org/licenses/LICENSE-2.0 .
     */

    #include <basegfx/polygon/b2dtrapezoid.hxx>
    #include <basegfx/range/b1drange.hxx>
    #include <basegfx/polygon/b2dpolygontools.hxx>

    #include <osl/diagnose.h>

    #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(mnSortValue != 0)
                        return mnSortValue;

                    // get radiant; has to be in the range ]0.0 .. pi[, thus scale to full
                    // sal_uInt32 range for maximum precision
                    const double fRadiant(atan2(getDeltaY(), getDeltaX()) * (SAL_MAX_UINT32 / 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)
                :   TrDeSimpleEdge(pStart, pEnd),
                    mnSortValue(nSortValue)
                {
                    // force traversal of deltaY downward
                    if(mpEnd->getY() < mpStart->getY())
                    {
                        std::swap(mpStart, mpEnd);
                    }

                    // no horizontal edges allowed, all need to traverse vertically
                    OSL_ENSURE(mpEnd->getY() > mpStart->getY(), "Illegal TrDeEdgeEntry constructed (!)");
                }

                // data write access to StartPoint
                void setStart( const B2DPoint* pNewStart)
                {
                    OSL_ENSURE(pNewStart != nullptr, "No null pointer allowed here (!)");

                    if(mpStart != pNewStart)
                    {
                        mpStart = pNewStart;

                        // no horizontal edges allowed, all need to traverse vertically
                        OSL_ENSURE(mpEnd->getY() > mpStart->getY(), "Illegal TrDeEdgeEntry constructed (!)");
                    }
                }

                // data write access to EndPoint
                void setEnd( const B2DPoint* pNewEnd)
                {
                    OSL_ENSURE(pNewEnd != nullptr, "No null pointer allowed here (!)");

                    if(mpEnd != pNewEnd)
                    {
                        mpEnd = pNewEnd;

                        // no horizontal edges allowed, all need to traverse vertically
                        OSL_ENSURE(mpEnd->getY() > mpStart->getY(), "Illegal TrDeEdgeEntry constructed (!)");
                    }
                }

                // operator for sort support. Sort by Y, X and slope (in that order)
                bool operator<(const TrDeEdgeEntry& rComp) const
                {
                    if(fTools::equal(getStart().getY(), rComp.getStart().getY()))
                    {
                        if(fTools::equal(getStart().getX(), rComp.getStart().getX()))
                        {
                            // when start points are equal, use the direction the edge is pointing
                            // to. That value is created on demand and derived from atan2 in the
                            // range ]0.0 .. pi[ (without extremas, we always have a deltaY in this
                            // class) and scaled to sal_uInt32 range for best precision. 0 means no angle,
                            // while SAL_MAX_UINT32 means pi. Thus, the higher the value, the more left
                            // the edge traverses.
                            return (getSortValue() > rComp.getSortValue());
                        }
                        else
                        {
                            return fTools::less(getStart().getX(), rComp.getStart().getX());
                        }
                    }
                    else
                    {
                        return fTools::less(getStart().getY(), rComp.getStart().getY());
                    }
                }

                // method for cut support
                B2DPoint getCutPointForGivenY(double fGivenY) const
                {
                    // 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
        {
            // FIXME: templatize this and use it for TrDeEdgeEntries too ...

            /// Class to allow efficient allocation and release of B2DPoints
            class PointBlockAllocator
            {
                static const size_t nBlockSize = 32;
                size_t nCurPoint;
                B2DPoint *mpPointBase;
                /// Special case the first allocation to avoid it.
                B2DPoint maFirstStackBlock[nBlockSize];
                std::vector< B2DPoint * > maBlocks;
            public:
                PointBlockAllocator() :
                    nCurPoint( nBlockSize ),
                    mpPointBase( maFirstStackBlock )
                {
                }

                ~PointBlockAllocator()
                {
                    while(maBlocks.size() > 0)
                    {
                        delete [] maBlocks.back();
                        maBlocks.pop_back();
                    }
                }

                B2DPoint *allocatePoint()
                {
                    if(nCurPoint >= nBlockSize)
                    {
                        mpPointBase = new B2DPoint[nBlockSize];
                        maBlocks.push_back(mpPointBase);
                        nCurPoint = 0;
                    }
                    return mpPointBase + nCurPoint++;
                }

                B2DPoint *allocatePoint(const B2DTuple &rPoint)
                {
                    B2DPoint *pPoint = allocatePoint();
                    *pPoint = rPoint;
                    return pPoint;
                }

                /// This is a very uncommon case but why not ...
                void freeIfLast(B2DPoint const *pPoint)
                {
                    // just re-use the last point if we can.
                    if ( nCurPoint > 0 && pPoint == mpPointBase + nCurPoint - 1 )
                        nCurPoint--;
                }
            };

            // helper class to handle the complete trapezoid subdivision of a PolyPolygon
            class TrapezoidSubdivider
            {
            private:
                // local data
                sal_uInt32                  mnInitialEdgeEntryCount;
                TrDeEdgeEntries             maTrDeEdgeEntries;
                std::vector< B2DPoint >   maPoints;
                /// new points allocated for cuts
                PointBlockAllocator         maNewPoints;

                void addEdgeSorted(
                    TrDeEdgeEntries::iterator aCurrent,
                    const TrDeEdgeEntry& rNewEdge)
                {
                    // Loop while new entry is bigger, use operator<
                    while(aCurrent != maTrDeEdgeEntries.end() && (*aCurrent) < rNewEdge)
                    {
                        ++aCurrent;
                    }

                    // Insert before first which is smaller or equal or at end
                    maTrDeEdgeEntries.insert(aCurrent, rNewEdge);
                }

                bool splitEdgeAtGivenPoint(
                    TrDeEdgeEntries::reference aEdge,
                    const B2DPoint& rCutPoint,
                    const TrDeEdgeEntries::iterator& aCurrent)
                {
                    // do not create edges without deltaY: do not split when start is identical
                    if(aEdge.getStart().equal(rCutPoint))
                    {
                        return false;
                    }

                    // do not create edges without deltaY: do not split when end is identical
                    if(aEdge.getEnd().equal(rCutPoint))
                    {
                        return false;
                    }

                    const double fOldDeltaYStart(rCutPoint.getY() - aEdge.getStart().getY());

                    if(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,
                    const TrDeEdgeEntries::iterator& aCurrent)
                {
                    // Exclude simple cases: same start or end point
                    if(aEdgeA.getStart().equal(aEdgeB.getStart()))
                    {
                        return false;
                    }

                    if(aEdgeA.getStart().equal(aEdgeB.getEnd()))
                    {
                        return false;
                    }

                    if(aEdgeA.getEnd().equal(aEdgeB.getStart()))
                    {
                        return false;
                    }

                    if(aEdgeA.getEnd().equal(aEdgeB.getEnd()))
                    {
                        return false;
                    }

                    // Exclude simple cases: one of the edges has no length anymore
                    if(aEdgeA.getStart().equal(aEdgeA.getEnd()))
                    {
                        return false;
                    }

                    if(aEdgeB.getStart().equal(aEdgeB.getEnd()))
                    {
                        return false;
                    }

                    // check if one point is on the other edge (a touch, not a cut)
                    const B2DVector aDeltaB(aEdgeB.getDeltaX(), aEdgeB.getDeltaY());

                    if(utils::isPointOnEdge(aEdgeA.getStart(), aEdgeB.getStart(), aDeltaB))
                    {
                        return splitEdgeAtGivenPoint(aEdgeB, aEdgeA.getStart(), aCurrent);
                    }

                    if(utils::isPointOnEdge(aEdgeA.getEnd(), aEdgeB.getStart(), aDeltaB))
                    {
                        return splitEdgeAtGivenPoint(aEdgeB, aEdgeA.getEnd(), aCurrent);
                    }

                    const B2DVector aDeltaA(aEdgeA.getDeltaX(), aEdgeA.getDeltaY());

                    if(utils::isPointOnEdge(aEdgeB.getStart(), aEdgeA.getStart(), aDeltaA))
                    {
                        return splitEdgeAtGivenPoint(aEdgeA, aEdgeB.getStart(), aCurrent);
                    }

                    if(utils::isPointOnEdge(aEdgeB.getEnd(), aEdgeA.getStart(), aDeltaA))
                    {
                        return splitEdgeAtGivenPoint(aEdgeA, aEdgeB.getEnd(), aCurrent);
                    }

                    // check for cut inside edges. Use both t-values to choose the more precise
                    // one later
                    double fCutA(0.0);
                    double fCutB(0.0);

                    if(utils::findCut(
                        aEdgeA.getStart(), aDeltaA,
                        aEdgeB.getStart(), aDeltaB,
                        CutFlagValue::LINE,
                        &fCutA,
                        &fCutB) != CutFlagValue::NONE)
                    {
                        // use a simple metric (length criteria) for choosing the numerically
                        // better cut
                        const double fSimpleLengthA(aDeltaA.getX() + aDeltaA.getY());
                        const double fSimpleLengthB(aDeltaB.getX() + aDeltaB.getY());
                        const bool bAIsLonger(fSimpleLengthA > fSimpleLengthB);
                        B2DPoint* pNewPoint = bAIsLonger
                            ? maNewPoints.allocatePoint(aEdgeA.getStart() + (fCutA * aDeltaA))
                            : maNewPoints.allocatePoint(aEdgeB.getStart() + (fCutB * aDeltaB));

                        // try to split both edges
                        bool bRetval = splitEdgeAtGivenPoint(aEdgeA, *pNewPoint, aCurrent);
                        bRetval |= splitEdgeAtGivenPoint(aEdgeB, *pNewPoint, aCurrent);

                        if(!bRetval)
                            maNewPoints.freeIfLast(pNewPoint);

                        return bRetval;
                    }

                    return false;
                }

                void solveHorizontalEdges(TrDeSimpleEdges& rTrDeSimpleEdges)
                {
                    if(!rTrDeSimpleEdges.empty() && !maTrDeEdgeEntries.empty())
                    {
                        // there were horizontal edges. These can be excluded, but
                        // cuts with other edges need to be solved and added before
                        // ignoring them
                        for(TrDeSimpleEdge & rHorEdge : rTrDeSimpleEdges)
                        {
                            // get horizontal edge as candidate; prepare its range and fixed Y
                            const B1DRange aRange(rHorEdge.getStart().getX(), rHorEdge.getEnd().getX());
                            const double fFixedY(rHorEdge.getStart().getY());

                            // loop over traversing edges
                            TrDeEdgeEntries::iterator aCurrent(maTrDeEdgeEntries.begin());

                            do
                            {
                                // get compare edge
                                TrDeEdgeEntries::reference aCompare(*aCurrent++);

                                if(fTools::lessOrEqual(aCompare.getEnd().getY(), fFixedY))
                                {
                                    // edge ends above horizontal edge, continue
                                    continue;
                                }

                                if(fTools::moreOrEqual(aCompare.getStart().getY(), fFixedY))
                                {
                                    // edge starts below horizontal edge, continue
                                    continue;
                                }

                                // vertical overlap, get horizontal range
                                const B1DRange aCompareRange(aCompare.getStart().getX(), aCompare.getEnd().getX());

                                if(aRange.overlaps(aCompareRange))
                                {
                                    // possible cut, get cut point
                                    const B2DPoint aSplit(aCompare.getCutPointForGivenY(fFixedY));

                                    if(fTools::more(aSplit.getX(), aRange.getMinimum())
                                        && fTools::less(aSplit.getX(), aRange.getMaximum()))
                                    {
                                        // cut is in XRange of horizontal edge, potentially needed cut
                                        B2DPoint* pNewPoint = maNewPoints.allocatePoint(aSplit);

                                        if(!splitEdgeAtGivenPoint(aCompare, *pNewPoint, aCurrent))
                                        {
                                            maNewPoints.freeIfLast(pNewPoint);
                                        }
                                    }
                                }
                            }
                            while(aCurrent != maTrDeEdgeEntries.end()
                                && fTools::less(aCurrent->getStart().getY(), fFixedY));
                        }
                    }
                }

            public:
                explicit TrapezoidSubdivider(
                    const B2DPolyPolygon& rSourcePolyPolygon)
                :   mnInitialEdgeEntryCount(0),
                    maTrDeEdgeEntries(),
                    maPoints(),
                    maNewPoints()
                {
                    B2DPolyPolygon aSource(rSourcePolyPolygon);
                    TrDeSimpleEdges aTrDeSimpleEdges;
                    sal_uInt32 nAllPointCount(0);

                    // ensure there are no curves used
                    if(aSource.areControlPointsUsed())
                    {
                        aSource = aSource.getDefaultAdaptiveSubdivision();
                    }

                    for(const auto& aPolygonCandidate : aSource)
                    {
                        // 1st run: count points
                        const sal_uInt32 nCount(aPolygonCandidate.count());

                        if(nCount > 2)
                        {
                            nAllPointCount += nCount;
                        }
                    }

                    if(nAllPointCount)
                    {
                        // reserve needed points. CAUTION: maPoints size is NOT to be changed anymore
                        // after 2nd loop since pointers to it are used in the edges
                        maPoints.reserve(nAllPointCount);

                        for(const auto& aPolygonCandidate : aSource)
                        {
                            // 2nd run: add points
                            const sal_uInt32 nCount(aPolygonCandidate.count());

                            if(nCount > 2)
                            {
                                for(sal_uInt32 b = 0; b < nCount; b++)
                                {
                                    maPoints.push_back(aPolygonCandidate.getB2DPoint(b));
                                }
                            }
                        }

                        // Moved the edge construction to a 3rd run: doing it in the 2nd run is
                        // possible(and i used it), but requires a working vector::reserve()
                        // implementation, else the vector will be reallocated and the pointers
                        // in the edges may be wrong. Security first here.
                        sal_uInt32 nStartIndex(0);

                        for(const auto& aPolygonCandidate : aSource)
                        {
                            const sal_uInt32 nCount(aPolygonCandidate.count());

                            if(nCount > 2)
                            {
                                // get the last point of the current polygon
                                B2DPoint* pPrev(&maPoints[nCount + nStartIndex - 1]);

                                for(sal_uInt32 b = 0; b < nCount; b++)
                                {
                                    // get next point
                                    B2DPoint* pCurr(&maPoints[nStartIndex++]);

                                    if(fTools::equal(pPrev->getY(), pCurr->getY()))
                                    {
                                        // horizontal edge, check for single point
                                        if(!fTools::equal(pPrev->getX(), pCurr->getX()))
                                        {
                                            // X-order not needed, just add
                                            aTrDeSimpleEdges.emplace_back(pPrev, pCurr);

                                            const double fMiddle((pPrev->getY() + pCurr->getY()) * 0.5);
                                            pPrev->setY(fMiddle);
                                            pCurr->setY(fMiddle);
                                        }
                                    }
                                    else
                                    {
                                        // vertical edge. Positive Y-direction is guaranteed by the
                                        // TrDeEdgeEntry constructor
                                        maTrDeEdgeEntries.emplace_back(pPrev, pCurr, 0);
                                        mnInitialEdgeEntryCount++;
                                    }

                                    // prepare next step
                                    pPrev = pCurr;
                                }
                            }
                        }
                    }

                    if(!maTrDeEdgeEntries.empty())
                    {
                        // single and initial sort of traversing edges
                        maTrDeEdgeEntries.sort();

                        // solve horizontal edges if there are any detected
                        solveHorizontalEdges(aTrDeSimpleEdges);
                    }
                }

                void Subdivide(B2DTrapezoidVector& ro_Result)
                {
                    // This is the central subdivider. The strategy is to use the first two entries
                    // from the traversing edges as a potential trapezoid and do the needed corrections
                    // and 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_FAIL("Trapezoid decomposer in illegal state (!)");
                            maTrDeEdgeEntries.pop_front();
                            continue;
                        }

                        // get second edge
                        TrDeEdgeEntries::reference aRight(*aCurrent++);

                        if(!fTools::equal(aLeft.getStart().getY(), aRight.getStart().getY()))
                        {
                            // Should not happen: We have a 2nd edge, but YStart is on another
                            // line; consume the single edge to not have an endless loop and start
                            // next. During development i constantly had breakpoints here, so i am
                            // sure enough to add an assertion here
                            OSL_FAIL("Trapezoid decomposer in illegal state (!)");
                            maTrDeEdgeEntries.pop_front();
                            continue;
                        }

                        // aLeft and aRight build a thought trapezoid now. They have a common
                        // start line (same Y for start points). Potentially, one of the edges
                        // is longer than the other. It is only needed to look at the shorter
                        // length which build the potential trapezoid. To do so, get the end points
                        // locally and adapt the evtl. longer one. Use only aLeftEnd and aRightEnd
                        // from here on, not the aLeft.getEnd() or aRight.getEnd() accesses.
                        B2DPoint aLeftEnd(aLeft.getEnd());
                        B2DPoint aRightEnd(aRight.getEnd());

                        // check if end points are on the same line. If yes, no adaption
                        // needs to be prepared. Also remember which one actually is longer.
                        const bool bEndOnSameLine(fTools::equal(aLeftEnd.getY(), aRightEnd.getY()));
                        bool bLeftIsLonger(false);

                        if(!bEndOnSameLine)
                        {
                            // check which edge is longer and correct accordingly
                            bLeftIsLonger = fTools::more(aLeftEnd.getY(), aRightEnd.getY());

                            if(bLeftIsLonger)
                            {
                                aLeftEnd = aLeft.getCutPointForGivenY(aRightEnd.getY());
                            }
                            else
                            {
                                aRightEnd = aRight.getCutPointForGivenY(aLeftEnd.getY());
                            }
                        }

                        // check for same start and end points
                        const bool bSameStartPoint(aLeft.getStart().equal(aRight.getStart()));
                        const bool bSameEndPoint(aLeftEnd.equal(aRightEnd));

                        // check the simple case that the edges form a 'blind' edge (deadend)
                        if(bSameStartPoint && bSameEndPoint)
                        {
                            // correct the longer edge if prepared
                            if(!bEndOnSameLine)
                            {
                                if(bLeftIsLonger)
                                {
                                    B2DPoint* pNewPoint = maNewPoints.allocatePoint(aLeftEnd);

                                    if(!splitEdgeAtGivenPoint(aLeft, *pNewPoint, aCurrent))
                                    {
                                        maNewPoints.freeIfLast(pNewPoint);
                                    }
                                }
                                else
                                {
                                    B2DPoint* pNewPoint = maNewPoints.allocatePoint(aRightEnd);

                                    if(!splitEdgeAtGivenPoint(aRight, *pNewPoint, aCurrent))
                                    {
                                        maNewPoints.freeIfLast(pNewPoint);
                                    }
                                }
                            }

                            // consume both edges and start next run
                            maTrDeEdgeEntries.pop_front();
                            maTrDeEdgeEntries.pop_front();

                            continue;
                        }

                        // check if the edges self-intersect. This can only happen when
                        // start and end point are different
                        bool bRangesSet(false);

                        if(!(bSameStartPoint || bSameEndPoint))
                        {
                            // get XRanges of edges
                            aLeftRange = B1DRange(aLeft.getStart().getX(), aLeftEnd.getX());
                            aRightRange = B1DRange(aRight.getStart().getX(), aRightEnd.getX());
                            bRangesSet = true;

                            // use fast range test first
                            if(aLeftRange.overlaps(aRightRange))
                            {
                                // real cut test and correction. If correction was needed,
                                // start new run
                                if(testAndCorrectEdgeIntersection(aLeft, aRight, aCurrent))
                                {
                                    continue;
                                }
                            }
                        }

                        // now we need to check if there are intersections with other edges
                        // or if other edges start inside the candidate trapezoid
                        if(aCurrent != maTrDeEdgeEntries.end()
                            && fTools::less(aCurrent->getStart().getY(), aLeftEnd.getY()))
                        {
                            // get XRanges of edges
                            if(!bRangesSet)
                            {
                                aLeftRange = B1DRange(aLeft.getStart().getX(), aLeftEnd.getX());
                                aRightRange = B1DRange(aRight.getStart().getX(), aRightEnd.getX());
                            }

                            // build full XRange for fast check
                            B1DRange aAllRange(aLeftRange);
                            aAllRange.expand(aRightRange);

                            // prepare loop iterator; aCurrent needs to stay unchanged for
                            // possibly sorted insertions of new EdgeNodes. Also prepare stop flag
                            TrDeEdgeEntries::iterator aLoop(aCurrent);
                            bool bDone(false);

                            do
                            {
                                // get compare edge and its XRange
                                TrDeEdgeEntries::reference aCompare(*aLoop++);

                                // avoid edges using the same start point as one of
                                // the edges. These can neither have their start point
                                // in the thought trapezoid nor cut with one of the edges
                                if(aCompare.getStart().equal(aRight.getStart()))
                                {
                                    continue;
                                }

                                // get compare XRange
                                const B1DRange aCompareRange(aCompare.getStart().getX(), aCompare.getEnd().getX());

                                // use fast range test first
                                if(aAllRange.overlaps(aCompareRange))
                                {
                                    // check for start point inside thought trapezoid
                                    if(fTools::more(aCompare.getStart().getY(), aLeft.getStart().getY()))
                                    {
                                        // calculate the two possible split points at compare's Y
                                        const B2DPoint aSplitLeft(aLeft.getCutPointForGivenY(aCompare.getStart().getY()));
                                        const B2DPoint aSplitRight(aRight.getCutPointForGivenY(aCompare.getStart().getY()));

                                        // check for start point of aCompare being inside thought
                                        // trapezoid
                                        if(aCompare.getStart().getX() >= aSplitLeft.getX() &&
                                            aCompare.getStart().getX() <= aSplitRight.getX())
                                        {
                                            // is inside, correct and restart loop
                                            B2DPoint* pNewLeft = maNewPoints.allocatePoint(aSplitLeft);

                                            if(splitEdgeAtGivenPoint(aLeft, *pNewLeft, aCurrent))
                                            {
                                                bDone = true;
                                            }
                                            else
                                            {
                                                maNewPoints.freeIfLast(pNewLeft);
                                            }

                                            B2DPoint* pNewRight = maNewPoints.allocatePoint(aSplitRight);

                                            if(splitEdgeAtGivenPoint(aRight, *pNewRight, aCurrent))
                                            {
                                                bDone = true;
                                            }
                                            else
                                            {
                                                maNewPoints.freeIfLast(pNewRight);
                                            }
                                        }
                                    }

                                    if(!bDone && aLeftRange.overlaps(aCompareRange))
                                    {
                                        // test for concrete cut of compare edge with left edge
                                        bDone = testAndCorrectEdgeIntersection(aLeft, aCompare, aCurrent);
                                    }

                                    if(!bDone && aRightRange.overlaps(aCompareRange))
                                    {
                                        // test for concrete cut of compare edge with Right edge
                                        bDone = testAndCorrectEdgeIntersection(aRight, aCompare, aCurrent);
                                    }
                                }
                            }
                            while(!bDone
                                && aLoop != maTrDeEdgeEntries.end()
                                && fTools::less(aLoop->getStart().getY(), aLeftEnd.getY()));

                            if(bDone)
                            {
                                // something needed to be changed; start next loop
                                continue;
                            }
                        }

                        // when we get here, the intended trapezoid can be used. It needs to
                        // be corrected possibly (if prepared); but this is no reason not to
                        // use it in the same loop iteration
                        if(!bEndOnSameLine)
                        {
                            if(bLeftIsLonger)
                            {
                                B2DPoint* pNewPoint = maNewPoints.allocatePoint(aLeftEnd);

                                if(!splitEdgeAtGivenPoint(aLeft, *pNewPoint, aCurrent))
                                {
                                    maNewPoints.freeIfLast(pNewPoint);
                                }
                            }
                            else
                            {
                                B2DPoint* pNewPoint = maNewPoints.allocatePoint(aRightEnd);

                                if(!splitEdgeAtGivenPoint(aRight, *pNewPoint, aCurrent))
                                {
                                    maNewPoints.freeIfLast(pNewPoint);
                                }
                            }
                        }

                        // the two edges start at the same Y, they use the same DeltaY, they
                        // do not cut themselves and not any other edge in range. Create a
                        // B2DTrapezoid and consume both edges
                        ro_Result.emplace_back(
                                aLeft.getStart().getX(),
                                aRight.getStart().getX(),
                                aLeft.getStart().getY(),
                                aLeftEnd.getX(),
                                aRightEnd.getX(),
                                aLeftEnd.getY());

                        maTrDeEdgeEntries.pop_front();
                        maTrDeEdgeEntries.pop_front();
                    }
                }
            };
        } // end of 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 utils
        {
            // convert Source utils::PolyPolygon to trapezoids
            void trapezoidSubdivide(B2DTrapezoidVector& ro_Result, const B2DPolyPolygon& rSourcePolyPolygon)
            {
                trapezoidhelper::TrapezoidSubdivider aTrapezoidSubdivider(rSourcePolyPolygon);

                aTrapezoidSubdivider.Subdivide(ro_Result);
            }

            void createLineTrapezoidFromEdge(
                B2DTrapezoidVector& ro_Result,
                const B2DPoint& rPointA,
                const B2DPoint& rPointB,
                double fLineWidth)
            {
                if(fTools::lessOrEqual(fLineWidth, 0.0))
                {
                    // no line width
                    return;
                }

                if(rPointA.equal(rPointB))
                {
                    // points are equal, no edge
                    return;
                }

                const double fHalfLineWidth(0.5 * fLineWidth);

                if(fTools::equal(rPointA.getX(), rPointB.getX()))
                {
                    // vertical line
                    const double fLeftX(rPointA.getX() - fHalfLineWidth);
                    const double fRightX(rPointA.getX() + fHalfLineWidth);

                    ro_Result.emplace_back(
                            fLeftX,
                            fRightX,
                            std::min(rPointA.getY(), rPointB.getY()),
                            fLeftX,
                            fRightX,
                            std::max(rPointA.getY(), rPointB.getY()));
                }
                else if(fTools::equal(rPointA.getY(), rPointB.getY()))
                {
                    // horizontal line
                    const double fLeftX(std::min(rPointA.getX(), rPointB.getX()));
                    const double fRightX(std::max(rPointA.getX(), rPointB.getX()));

                    ro_Result.emplace_back(
                            fLeftX,
                            fRightX,
                            rPointA.getY() - fHalfLineWidth,
                            fLeftX,
                            fRightX,
                            rPointA.getY() + fHalfLineWidth);
                }
                else
                {
                    // diagonal line
                    // create perpendicular vector
                    const B2DVector aDelta(rPointB - rPointA);
                    B2DVector aPerpendicular(-aDelta.getY(), aDelta.getX());
                    aPerpendicular.setLength(fHalfLineWidth);

                    // create StartLow, StartHigh, EndLow and EndHigh
                    const B2DPoint aStartLow(rPointA + aPerpendicular);
                    const B2DPoint aStartHigh(rPointA - aPerpendicular);
                    const B2DPoint aEndHigh(rPointB - aPerpendicular);
                    const B2DPoint aEndLow(rPointB + aPerpendicular);

                    // create EdgeEntries
                    basegfx::trapezoidhelper::TrDeEdgeEntries aTrDeEdgeEntries;

                    aTrDeEdgeEntries.emplace_back(&aStartLow, &aStartHigh, 0);
                    aTrDeEdgeEntries.emplace_back(&aStartHigh, &aEndHigh, 0);
                    aTrDeEdgeEntries.emplace_back(&aEndHigh, &aEndLow, 0);
                    aTrDeEdgeEntries.emplace_back(&aEndLow, &aStartLow, 0);
                    aTrDeEdgeEntries.sort();

                    // here we know we have exactly four edges, and they do not cut, touch or
                    // intersect. This makes processing much easier. Get the first two as start
                    // edges for the thought trapezoid
                    basegfx::trapezoidhelper::TrDeEdgeEntries::iterator aCurrent(aTrDeEdgeEntries.begin());
                    basegfx::trapezoidhelper::TrDeEdgeEntries::reference aLeft(*aCurrent++);
                    basegfx::trapezoidhelper::TrDeEdgeEntries::reference aRight(*aCurrent++);
                    const bool bEndOnSameLine(fTools::equal(aLeft.getEnd().getY(), aRight.getEnd().getY()));

                    if(bEndOnSameLine)
                    {
                        // create two triangle trapezoids
                        ro_Result.emplace_back(
                                aLeft.getStart().getX(),
                                aRight.getStart().getX(),
                                aLeft.getStart().getY(),
                                aLeft.getEnd().getX(),
                                aRight.getEnd().getX(),
                                aLeft.getEnd().getY());

                        basegfx::trapezoidhelper::TrDeEdgeEntries::reference aLeft2(*aCurrent++);
                        basegfx::trapezoidhelper::TrDeEdgeEntries::reference aRight2(*aCurrent++);

                        ro_Result.emplace_back(
                                aLeft2.getStart().getX(),
                                aRight2.getStart().getX(),
                                aLeft2.getStart().getY(),
                                aLeft2.getEnd().getX(),
                                aRight2.getEnd().getX(),
                                aLeft2.getEnd().getY());
                    }
                    else
                    {
                        // create three trapezoids. Check which edge is longer and
                        // correct accordingly
                        const bool bLeftIsLonger(fTools::more(aLeft.getEnd().getY(), aRight.getEnd().getY()));

                        if(bLeftIsLonger)
                        {
                            basegfx::trapezoidhelper::TrDeEdgeEntries::reference aRight2(*aCurrent++);
                            basegfx::trapezoidhelper::TrDeEdgeEntries::reference aLeft2(*aCurrent++);
                            const B2DPoint aSplitLeft(aLeft.getCutPointForGivenY(aRight.getEnd().getY()));
                            const B2DPoint aSplitRight(aRight2.getCutPointForGivenY(aLeft.getEnd().getY()));

                            ro_Result.emplace_back(
                                    aLeft.getStart().getX(),
                                    aRight.getStart().getX(),
                                    aLeft.getStart().getY(),
                                    aSplitLeft.getX(),
                                    aRight.getEnd().getX(),
                                    aRight.getEnd().getY());

                            ro_Result.emplace_back(
                                    aSplitLeft.getX(),
                                    aRight.getEnd().getX(),
                                    aRight.getEnd().getY(),
                                    aLeft2.getStart().getX(),
                                    aSplitRight.getX(),
                                    aLeft2.getStart().getY());

                            ro_Result.emplace_back(
                                    aLeft2.getStart().getX(),
                                    aSplitRight.getX(),
                                    aLeft2.getStart().getY(),
                                    aLeft2.getEnd().getX(),
                                    aRight2.getEnd().getX(),
                                    aLeft2.getEnd().getY());
                        }
                        else
                        {
                            basegfx::trapezoidhelper::TrDeEdgeEntries::reference aLeft2(*aCurrent++);
                            basegfx::trapezoidhelper::TrDeEdgeEntries::reference aRight2(*aCurrent++);
                            const B2DPoint aSplitRight(aRight.getCutPointForGivenY(aLeft.getEnd().getY()));
                            const B2DPoint aSplitLeft(aLeft2.getCutPointForGivenY(aRight.getEnd().getY()));

                            ro_Result.emplace_back(
                                    aLeft.getStart().getX(),
                                    aRight.getStart().getX(),
                                    aLeft.getStart().getY(),
                                    aLeft.getEnd().getX(),
                                    aSplitRight.getX(),
                                    aLeft.getEnd().getY());

                            ro_Result.emplace_back(
                                    aLeft.getEnd().getX(),
                                    aSplitRight.getX(),
                                    aLeft.getEnd().getY(),
                                    aSplitLeft.getX(),
                                    aRight.getEnd().getX(),
                                    aRight2.getStart().getY());

                            ro_Result.emplace_back(
                                    aSplitLeft.getX(),
                                    aRight.getEnd().getX(),
                                    aRight2.getStart().getY(),
                                    aLeft2.getEnd().getX(),
                                    aRight2.getEnd().getX(),
                                    aLeft2.getEnd().getY());
                        }
                    }
                }
            }

            void createLineTrapezoidFromB2DPolygon(
                B2DTrapezoidVector& ro_Result,
                const B2DPolygon& rPolygon,
                double fLineWidth)
            {
                if(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;
                }
            }

        } // end of namespace utils
    } // end of namespace basegfx

    /* vim:set shiftwidth=4 softtabstop=4 expandtab: */

↑ V778 Two similar code fragments were found. Perhaps, this is a typo and 'getEnd' variable should be used instead of 'getStart'.

↑ V778 Two similar code fragments were found. Perhaps, this is a typo and 'getEnd' variable should be used instead of 'getStart'.