LCOV - code coverage report
Current view: top level - basegfx/source/range - b2drangeclipper.cxx (source / functions) Hit Total Coverage
Test: commit e02a6cb2c3e2b23b203b422e4e0680877f232636 Lines: 1 211 0.5 %
Date: 2014-04-14 Functions: 2 47 4.3 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
       2             : /*
       3             :  * This file is part of the LibreOffice project.
       4             :  *
       5             :  * This Source Code Form is subject to the terms of the Mozilla Public
       6             :  * License, v. 2.0. If a copy of the MPL was not distributed with this
       7             :  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
       8             :  *
       9             :  * This file incorporates work covered by the following license notice:
      10             :  *
      11             :  *   Licensed to the Apache Software Foundation (ASF) under one or more
      12             :  *   contributor license agreements. See the NOTICE file distributed
      13             :  *   with this work for additional information regarding copyright
      14             :  *   ownership. The ASF licenses this file to you under the Apache
      15             :  *   License, Version 2.0 (the "License"); you may not use this file
      16             :  *   except in compliance with the License. You may obtain a copy of
      17             :  *   the License at http://www.apache.org/licenses/LICENSE-2.0 .
      18             :  */
      19             : 
      20             : #include <rtl/math.hxx>
      21             : 
      22             : #include <basegfx/tuple/b2dtuple.hxx>
      23             : #include <basegfx/range/b2drange.hxx>
      24             : #include <basegfx/range/b2drangeclipper.hxx>
      25             : #include <basegfx/range/b2dpolyrange.hxx>
      26             : #include <basegfx/polygon/b2dpolypolygon.hxx>
      27             : #include <basegfx/polygon/b2dpolygontools.hxx>
      28             : #include <basegfx/polygon/b2dpolypolygontools.hxx>
      29             : 
      30             : #include <o3tl/vector_pool.hxx>
      31             : #include <boost/bind.hpp>
      32             : #include <boost/utility.hpp>
      33             : 
      34             : #include <algorithm>
      35             : #include <deque>
      36             : #include <list>
      37             : 
      38             : 
      39             : namespace basegfx
      40             : {
      41             :     namespace
      42             :     {
      43             :         // Generating a poly-polygon from a bunch of rectangles
      44             : 
      45             :         // Helper functionality for sweep-line algorithm
      46             :         // ====================================================
      47             : 
      48             :         typedef std::vector<B2DRange> VectorOfRanges;
      49             : 
      50             :         class ImplPolygon;
      51             :         typedef o3tl::vector_pool<ImplPolygon> VectorOfPolygons;
      52             : 
      53             : 
      54             :         /** This class represents an active edge
      55             : 
      56             :             As the sweep line traverses across the overall area,
      57             :             rectangle edges parallel to it generate events, and
      58             :             rectangle edges orthogonal to it generate active
      59             :             edges. This class represents the latter.
      60             :          */
      61             :         class ActiveEdge
      62             :         {
      63             :         public:
      64             :             /** The two possible active rectangle edges differ by one
      65             :                 coordinate value - the upper edge has the lower, the
      66             :                 lower edge the higher value.
      67             :              */
      68             :             enum EdgeType {
      69             :                 /// edge with lower coordinate value
      70             :                 UPPER=0,
      71             :                 /// edge with higher coordinate value
      72             :                 LOWER=1
      73             :             };
      74             : 
      75             :             enum EdgeDirection {
      76             :                 /// edge proceeds to the left
      77             :                 PROCEED_LEFT=0,
      78             :                 /// edge proceeds to the right
      79             :                 PROCEED_RIGHT=1
      80             :             };
      81             : 
      82             :             /** Create active edge
      83             : 
      84             :                 @param rRect
      85             :                 Rectangle this edge is part of
      86             : 
      87             :                 @param fInvariantCoord
      88             :                 The invariant coordinate value of this edge
      89             : 
      90             :                 @param eEdgeType
      91             :                 Is fInvariantCoord the lower or the higher value, for
      92             :                 this rect?
      93             :              */
      94           0 :             ActiveEdge( const B2DRectangle& rRect,
      95             :                         const double&       fInvariantCoord,
      96             :                         std::ptrdiff_t      nPolyIdx,
      97             :                         EdgeType            eEdgeType,
      98             :                         EdgeDirection       eEdgeDirection ) :
      99             :                 mfInvariantCoord(fInvariantCoord),
     100             :                 mpAssociatedRect( &rRect ),
     101             :                 mnPolygonIdx( nPolyIdx ),
     102             :                 meEdgeType( eEdgeType ),
     103           0 :                 meEdgeDirection( eEdgeDirection )
     104           0 :             {}
     105             : 
     106           0 :             double              getInvariantCoord() const { return mfInvariantCoord; }
     107           0 :             const B2DRectangle& getRect() const { return *mpAssociatedRect; }
     108           0 :             std::ptrdiff_t      getTargetPolygonIndex() const { return mnPolygonIdx; }
     109           0 :             void                setTargetPolygonIndex( std::ptrdiff_t nIdx ) { mnPolygonIdx = nIdx; }
     110           0 :             EdgeDirection       getEdgeDirection() const { return meEdgeDirection; }
     111             : 
     112             :         private:
     113             :             /** The invariant coordinate value of this edge (e.g. the
     114             :                 common y value, for a horizontal edge)
     115             :              */
     116             :             double              mfInvariantCoord;
     117             : 
     118             :             /** Associated rectangle
     119             : 
     120             :                 This on the one hand saves some storage space (the
     121             :                 vector of rectangles is persistent, anyway), and on
     122             :                 the other hand provides an identifier to match active
     123             :                 edges and x events (see below)
     124             : 
     125             :                 Ptr because class needs to be assignable
     126             :              */
     127             :             const B2DRectangle* mpAssociatedRect;
     128             : 
     129             :             /** Index of the polygon this edge is currently involved
     130             :                 with.
     131             : 
     132             :                 Note that this can change for some kinds of edge
     133             :                 intersection, as the algorithm tends to swap
     134             :                 associated polygons there.
     135             : 
     136             :                 -1 denotes no assigned polygon
     137             :              */
     138             :             std::ptrdiff_t      mnPolygonIdx;
     139             : 
     140             :             /// 'upper' or 'lower' edge of original rectangle.
     141             :             EdgeType            meEdgeType;
     142             : 
     143             :             /// 'left' or 'right'
     144             :             EdgeDirection       meEdgeDirection;
     145             :         };
     146             : 
     147             :         // Needs to be list - various places hold ptrs to elements
     148             :         typedef std::list< ActiveEdge > ListOfEdges;
     149             : 
     150             : 
     151             :         /** Element of the sweep line event list
     152             : 
     153             :             As the sweep line traverses across the overall area,
     154             :             rectangle edges parallel to it generate events, and
     155             :             rectangle edges orthogonal to it generate active
     156             :             edges. This class represents the former.
     157             : 
     158             :             The class defines an element of the sweep line list. The
     159             :             sweep line's position jumps in steps defined by the
     160             :             coordinates of the sorted SweepLineEvent entries.
     161             :          */
     162             :         class SweepLineEvent
     163             :         {
     164             :         public:
     165             :             /** The two possible sweep line rectangle edges differ by
     166             :                 one coordinate value - the starting edge has the
     167             :                 lower, the finishing edge the higher value.
     168             :              */
     169             :             enum EdgeType {
     170             :                 /// edge with lower coordinate value
     171             :                 STARTING_EDGE=0,
     172             :                 /// edge with higher coordinate value
     173             :                 FINISHING_EDGE=1
     174             :             };
     175             : 
     176             :             /** The two possible sweep line directions
     177             :              */
     178             :             enum EdgeDirection {
     179             :                 PROCEED_UP=0,
     180             :                 PROCEED_DOWN=1
     181             :             };
     182             : 
     183             :             /** Create sweep line event
     184             : 
     185             :                 @param fPos
     186             :                 Coordinate position of the event
     187             : 
     188             :                 @param rRect
     189             :                 Rectangle this event is generated for.
     190             : 
     191             :                 @param eEdgeType
     192             :                 Is fPos the lower or the higher value, for the
     193             :                 rectangle this event is generated for?
     194             :              */
     195           0 :             SweepLineEvent( double              fPos,
     196             :                             const B2DRectangle& rRect,
     197             :                             EdgeType            eEdgeType,
     198             :                             EdgeDirection       eDirection) :
     199             :                 mfPos( fPos ),
     200             :                 mpAssociatedRect( &rRect ),
     201             :                 meEdgeType( eEdgeType ),
     202           0 :                 meEdgeDirection( eDirection )
     203           0 :             {}
     204             : 
     205           0 :             double              getPos() const { return mfPos; }
     206           0 :             const B2DRectangle& getRect() const { return *mpAssociatedRect; }
     207           0 :             EdgeType            getEdgeType() const { return meEdgeType; }
     208           0 :             EdgeDirection       getEdgeDirection() const { return meEdgeDirection; }
     209             : 
     210             :             /// For STL sort
     211           0 :             bool operator<( const SweepLineEvent& rRHS ) const { return mfPos < rRHS.mfPos; }
     212             : 
     213             :         private:
     214             :             /// position of the event, in the direction of the line sweep
     215             :             double                mfPos;
     216             : 
     217             :             /** Rectangle this event is generated for
     218             : 
     219             :                 This on the one hand saves some storage space (the
     220             :                 vector of rectangles is persistent, anyway), and on
     221             :                 the other hand provides an identifier to match active
     222             :                 edges and events (see below)
     223             : 
     224             :                 Ptr because class needs to be assignable
     225             :              */
     226             :             const B2DRectangle*   mpAssociatedRect;
     227             : 
     228             :             /// 'upper' or 'lower' edge of original rectangle.
     229             :             EdgeType              meEdgeType;
     230             : 
     231             :             /// 'up' or 'down'
     232             :             EdgeDirection         meEdgeDirection;
     233             :         };
     234             : 
     235             :         typedef std::vector< SweepLineEvent > VectorOfEvents;
     236             : 
     237             : 
     238             :         /** Smart point container for B2DMultiRange::getPolyPolygon()
     239             : 
     240             :             This class provides methods needed only here, and is used
     241             :             as a place to store some additional information per
     242             :             polygon. Also, most of the intersection logic is
     243             :             implemented here.
     244             :          */
     245           0 :         class ImplPolygon
     246             :         {
     247             :         public:
     248             :             /** Create polygon
     249             :              */
     250           0 :             ImplPolygon() :
     251             :                 mpLeadingRightEdge(NULL),
     252             :                 mnIdx(-1),
     253             :                 maPoints(),
     254           0 :                 mbIsFinished(false)
     255             :             {
     256             :                 // completely ad-hoc. but what the hell.
     257           0 :                 maPoints.reserve(11);
     258           0 :             }
     259             : 
     260           0 :             void setPolygonPoolIndex( std::ptrdiff_t nIdx ) { mnIdx = nIdx; }
     261             :             bool isFinished() const { return mbIsFinished; }
     262             : 
     263             :             /// Add point to the end of the existing points
     264           0 :             void append( const B2DPoint& rPoint )
     265             :             {
     266             :                 OSL_PRECOND( maPoints.empty() ||
     267             :                              maPoints.back().getX() == rPoint.getX() ||
     268             :                              maPoints.back().getY() == rPoint.getY(),
     269             :                              "ImplPolygon::append(): added point violates 90 degree line angle constraint!" );
     270             : 
     271           0 :                 if( maPoints.empty() ||
     272           0 :                     maPoints.back() != rPoint )
     273             :                 {
     274             :                     // avoid duplicate points
     275           0 :                     maPoints.push_back( rPoint );
     276             :                 }
     277           0 :             }
     278             : 
     279             :             /** Perform the intersection of this polygon with an
     280             :                 active edge.
     281             : 
     282             :                 @param rEvent
     283             :                 The vertical line event that generated the
     284             :                 intersection
     285             : 
     286             :                 @param rActiveEdge
     287             :                 The active edge that generated the intersection
     288             : 
     289             :                 @param rPolygonPool
     290             :                 Polygon pool, we sometimes need to allocate a new one
     291             : 
     292             :                 @param bIsFinishingEdge
     293             :                 True, when this is hitting the last edge of the
     294             :                 vertical sweep - every vertical sweep starts and ends
     295             :                 with upper and lower edge of the _same_ rectangle.
     296             : 
     297             :                 @return the new current polygon (that's the one
     298             :                 processing must proceed with, when going through the
     299             :                 list of upcoming active edges).
     300             :              */
     301           0 :             std::ptrdiff_t intersect( SweepLineEvent&   rEvent,
     302             :                                       ActiveEdge&       rActiveEdge,
     303             :                                       VectorOfPolygons& rPolygonPool,
     304             :                                       B2DPolyPolygon&   rRes,
     305             :                                       bool              isFinishingEdge )
     306             :             {
     307             :                 OSL_PRECOND( !isFinished(),
     308             :                              "ImplPolygon::intersect(): called on already finished polygon!" );
     309             :                 OSL_PRECOND( !isFinishingEdge
     310             :                              || (isFinishingEdge && &rEvent.getRect() == &rActiveEdge.getRect()),
     311             :                              "ImplPolygon::intersect(): inconsistent ending!" );
     312             : 
     313             :                 const B2DPoint aIntersectionPoint( rEvent.getPos(),
     314           0 :                                                    rActiveEdge.getInvariantCoord() );
     315             : 
     316             :                 // intersection point, goes to our polygon
     317             :                 // unconditionally
     318           0 :                 append(aIntersectionPoint);
     319             : 
     320           0 :                 if( isFinishingEdge )
     321             :                 {
     322             :                     // isSweepLineEnteringRect ?
     323           0 :                     if( rEvent.getEdgeType() == SweepLineEvent::STARTING_EDGE)
     324           0 :                         handleFinalOwnRightEdge(rActiveEdge);
     325             :                     else
     326             :                         handleFinalOwnLeftEdge(rActiveEdge,
     327             :                                                rPolygonPool,
     328           0 :                                                rRes);
     329             : 
     330             :                     // we're done with this rect & sweep line
     331           0 :                     return -1;
     332             :                 }
     333           0 :                 else if( metOwnEdge(rEvent,rActiveEdge) )
     334             :                 {
     335           0 :                     handleInitialOwnEdge(rEvent, rActiveEdge);
     336             : 
     337             :                     // point already added, all init done, continue
     338             :                     // with same poly
     339           0 :                     return mnIdx;
     340             :                 }
     341             :                 else
     342             :                 {
     343             :                     OSL_ENSURE( rActiveEdge.getTargetPolygonIndex() != -1,
     344             :                                 "ImplPolygon::intersect(): non-trivial intersection hit empty polygon!" );
     345             : 
     346             :                     const bool isHittingLeftEdge(
     347           0 :                         rActiveEdge.getEdgeDirection() == ActiveEdge::PROCEED_LEFT);
     348             : 
     349           0 :                     if( isHittingLeftEdge )
     350             :                         return handleComplexLeftEdge(rActiveEdge,
     351             :                                                      aIntersectionPoint,
     352             :                                                      rPolygonPool,
     353           0 :                                                      rRes);
     354             :                     else
     355             :                         return handleComplexRightEdge(rActiveEdge,
     356             :                                                       aIntersectionPoint,
     357           0 :                                                       rPolygonPool);
     358           0 :                 }
     359             :             }
     360             : 
     361             :         private:
     362           0 :             void handleInitialOwnEdge(SweepLineEvent& rEvent,
     363             :                                       ActiveEdge&     rActiveEdge)
     364             :             {
     365             :                 const bool isActiveEdgeProceedLeft(
     366           0 :                     rActiveEdge.getEdgeDirection() == ActiveEdge::PROCEED_LEFT);
     367             :                 const bool isSweepLineEnteringRect(
     368           0 :                     rEvent.getEdgeType() == SweepLineEvent::STARTING_EDGE);
     369             :                 (void)isActiveEdgeProceedLeft;
     370             :                 (void)isSweepLineEnteringRect;
     371             : 
     372             :                 OSL_ENSURE( isSweepLineEnteringRect == isActiveEdgeProceedLeft,
     373             :                             "ImplPolygon::intersect(): sweep initial own edge hit: wrong polygon order" );
     374             : 
     375             :                 OSL_ENSURE( isSweepLineEnteringRect ||
     376             :                             mpLeadingRightEdge == &rActiveEdge,
     377             :                             "ImplPolygon::intersect(): sweep initial own edge hit: wrong leading edge" );
     378           0 :             }
     379             : 
     380           0 :             void handleFinalOwnRightEdge(ActiveEdge& rActiveEdge)
     381             :             {
     382             :                 OSL_ENSURE( rActiveEdge.getEdgeDirection() == ActiveEdge::PROCEED_RIGHT,
     383             :                             "ImplPolygon::handleInitialOwnRightEdge(): start edge wrong polygon order" );
     384             : 
     385           0 :                 rActiveEdge.setTargetPolygonIndex(mnIdx);
     386           0 :                 mpLeadingRightEdge = &rActiveEdge;
     387           0 :             }
     388             : 
     389           0 :             void handleFinalOwnLeftEdge(ActiveEdge&       rActiveEdge,
     390             :                                         VectorOfPolygons& rPolygonPool,
     391             :                                         B2DPolyPolygon&   rRes)
     392             :             {
     393             :                 OSL_ENSURE( rActiveEdge.getEdgeDirection() == ActiveEdge::PROCEED_LEFT,
     394             :                             "ImplPolygon::handleFinalOwnLeftEdge(): end edge wrong polygon order" );
     395             : 
     396             :                 const bool isHittingOurTail(
     397           0 :                     rActiveEdge.getTargetPolygonIndex() == mnIdx);
     398             : 
     399           0 :                 if( isHittingOurTail )
     400           0 :                     finish(rRes); // just finish. no fuss.
     401             :                 else
     402             :                 {
     403             :                     // temp poly hits final left edge
     404           0 :                     const std::ptrdiff_t nTmpIdx=rActiveEdge.getTargetPolygonIndex();
     405           0 :                     ImplPolygon& rTmp=rPolygonPool.get(nTmpIdx);
     406             : 
     407             :                     // active edge's polygon has points
     408             :                     // already. ours need to go in front of them.
     409             :                     maPoints.insert(maPoints.end(),
     410             :                                     rTmp.maPoints.begin(),
     411           0 :                                     rTmp.maPoints.end());
     412             : 
     413             :                     // adjust leading edges, we're switching the polygon
     414           0 :                     ActiveEdge* const pFarEdge=rTmp.mpLeadingRightEdge;
     415             : 
     416           0 :                     mpLeadingRightEdge = pFarEdge;
     417           0 :                     pFarEdge->setTargetPolygonIndex(mnIdx);
     418             : 
     419             :                     // nTmpIdx is an empty shell, get rid of it
     420           0 :                     rPolygonPool.free(nTmpIdx);
     421             :                 }
     422           0 :             }
     423             : 
     424           0 :             std::ptrdiff_t handleComplexLeftEdge(ActiveEdge&       rActiveEdge,
     425             :                                                  const B2DPoint&   rIntersectionPoint,
     426             :                                                  VectorOfPolygons& rPolygonPool,
     427             :                                                  B2DPolyPolygon&   rRes)
     428             :             {
     429             :                 const bool isHittingOurTail(
     430           0 :                     rActiveEdge.getTargetPolygonIndex() == mnIdx);
     431           0 :                 if( isHittingOurTail )
     432             :                 {
     433           0 :                     finish(rRes);
     434             : 
     435             :                     // so "this" is done - need new polygon to collect
     436             :                     // further points
     437           0 :                     const std::ptrdiff_t nIdxNewPolygon=rPolygonPool.alloc();
     438           0 :                     rPolygonPool.get(nIdxNewPolygon).setPolygonPoolIndex(nIdxNewPolygon);
     439           0 :                     rPolygonPool.get(nIdxNewPolygon).append(rIntersectionPoint);
     440             : 
     441           0 :                     rActiveEdge.setTargetPolygonIndex(nIdxNewPolygon);
     442             : 
     443           0 :                     return nIdxNewPolygon;
     444             :                 }
     445             :                 else
     446             :                 {
     447           0 :                     const std::ptrdiff_t nTmpIdx=rActiveEdge.getTargetPolygonIndex();
     448           0 :                     ImplPolygon& rTmp=rPolygonPool.get(nTmpIdx);
     449             : 
     450             :                     // active edge's polygon has points
     451             :                     // already. ours need to go in front of them.
     452             :                     maPoints.insert(maPoints.end(),
     453             :                                     rTmp.maPoints.begin(),
     454           0 :                                     rTmp.maPoints.end());
     455             : 
     456           0 :                     rTmp.maPoints.clear();
     457           0 :                     rTmp.append(rIntersectionPoint);
     458             : 
     459             :                     // adjust leading edges, we're switching the polygon
     460           0 :                     ActiveEdge* const pFarEdge=rTmp.mpLeadingRightEdge;
     461           0 :                     ActiveEdge* const pNearEdge=&rActiveEdge;
     462             : 
     463           0 :                     rTmp.mpLeadingRightEdge = NULL;
     464           0 :                     pNearEdge->setTargetPolygonIndex(nTmpIdx);
     465             : 
     466           0 :                     mpLeadingRightEdge = pFarEdge;
     467           0 :                     pFarEdge->setTargetPolygonIndex(mnIdx);
     468             : 
     469           0 :                     return nTmpIdx;
     470             :                 }
     471             :             }
     472             : 
     473           0 :             std::ptrdiff_t handleComplexRightEdge(ActiveEdge&       rActiveEdge,
     474             :                                                   const B2DPoint&   rIntersectionPoint,
     475             :                                                   VectorOfPolygons& rPolygonPool)
     476             :             {
     477           0 :                 const std::ptrdiff_t nTmpIdx=rActiveEdge.getTargetPolygonIndex();
     478           0 :                 ImplPolygon& rTmp=rPolygonPool.get(nTmpIdx);
     479             : 
     480           0 :                 rTmp.append(rIntersectionPoint);
     481             : 
     482           0 :                 rActiveEdge.setTargetPolygonIndex(mnIdx);
     483           0 :                 mpLeadingRightEdge = &rActiveEdge;
     484             : 
     485           0 :                 rTmp.mpLeadingRightEdge = NULL;
     486             : 
     487           0 :                 return nTmpIdx;
     488             :             }
     489             : 
     490             :             /// True when sweep line hits our own active edge
     491           0 :             bool metOwnEdge(const SweepLineEvent& rEvent,
     492             :                             ActiveEdge&           rActiveEdge)
     493             :             {
     494           0 :                 const bool bHitOwnEdge=&rEvent.getRect() == &rActiveEdge.getRect();
     495           0 :                 return bHitOwnEdge;
     496             :             }
     497             : 
     498             :             /// Retrieve B2DPolygon from this object
     499           0 :             B2DPolygon getPolygon() const
     500             :             {
     501           0 :                 B2DPolygon aRes;
     502             :                 std::for_each( maPoints.begin(),
     503             :                                maPoints.end(),
     504             :                                boost::bind(
     505             :                      &B2DPolygon::append,
     506             :                                    boost::ref(aRes),
     507             :                                    _1,
     508           0 :                                    1 ) );
     509           0 :                 aRes.setClosed( true );
     510           0 :                 return aRes;
     511             :             }
     512             : 
     513             :             /** Finish this polygon, push to result set.
     514             :              */
     515           0 :             void finish(B2DPolyPolygon& rRes)
     516             :             {
     517             :                 OSL_PRECOND( maPoints.empty() ||
     518             :                              maPoints.front().getX() == maPoints.back().getX() ||
     519             :                              maPoints.front().getY() == maPoints.back().getY(),
     520             :                              "ImplPolygon::finish(): first and last point violate 90 degree line angle constraint!" );
     521             : 
     522           0 :                 mbIsFinished = true;
     523           0 :                 mpLeadingRightEdge = NULL;
     524             : 
     525           0 :                 rRes.append(getPolygon());
     526           0 :             }
     527             : 
     528             :             /** Refers to the current leading edge element of this
     529             :                 polygon, or NULL. The leading edge denotes the 'front'
     530             :                 of the polygon vertex sequence, i.e. the coordinates
     531             :                 at the polygon's leading edge are returned from
     532             :                 maPoints.front()
     533             :              */
     534             :             ActiveEdge*           mpLeadingRightEdge;
     535             : 
     536             :             /// current index into vector pool
     537             :             std::ptrdiff_t        mnIdx;
     538             : 
     539             :             /// Container for the actual polygon points
     540             :             std::vector<B2DPoint> maPoints;
     541             : 
     542             :             /// When true, this polygon is 'done', i.e. nothing must be added anymore.
     543             :             bool                  mbIsFinished;
     544             :         };
     545             : 
     546             :         /** Init sweep line event list
     547             : 
     548             :             This method fills the event list with the sweep line
     549             :             events generated from the input rectangles, and sorts them
     550             :             with increasing x.
     551             :          */
     552           0 :         void setupSweepLineEventListFromRanges( VectorOfEvents& o_rEventVector,
     553             :                                                 const std::vector<B2DRange>& rRanges,
     554             :                                                 const std::vector<B2VectorOrientation>& rOrientations )
     555             :         {
     556             :             // we need exactly 2*rectVec.size() events: one for the
     557             :             // left, and one for the right edge of each rectangle
     558           0 :             o_rEventVector.clear();
     559           0 :             o_rEventVector.reserve( 2*rRanges.size() );
     560             : 
     561             :             // generate events
     562             :             // ===============
     563             : 
     564             :             // first pass: add all left edges in increasing order
     565           0 :             std::vector<B2DRange>::const_iterator aCurrRect=rRanges.begin();
     566           0 :             std::vector<B2VectorOrientation>::const_iterator aCurrOrientation=rOrientations.begin();
     567           0 :             const std::vector<B2DRange>::const_iterator aEnd=rRanges.end();
     568           0 :             const std::vector<B2VectorOrientation>::const_iterator aEndOrientation=rOrientations.end();
     569           0 :             while( aCurrRect != aEnd && aCurrOrientation != aEndOrientation )
     570             :             {
     571           0 :                 const B2DRectangle& rCurrRect( *aCurrRect++ );
     572             : 
     573             :                 o_rEventVector.push_back(
     574             :                     SweepLineEvent( rCurrRect.getMinX(),
     575             :                                     rCurrRect,
     576             :                                     SweepLineEvent::STARTING_EDGE,
     577           0 :                                     (*aCurrOrientation++) == ORIENTATION_POSITIVE ?
     578           0 :                                     SweepLineEvent::PROCEED_UP : SweepLineEvent::PROCEED_DOWN) );
     579             :             }
     580             : 
     581             :             // second pass: add all right edges in reversed order
     582           0 :             std::vector<B2DRange>::const_reverse_iterator aCurrRectR=rRanges.rbegin();
     583           0 :             std::vector<B2VectorOrientation>::const_reverse_iterator aCurrOrientationR=rOrientations.rbegin();
     584           0 :             const std::vector<B2DRange>::const_reverse_iterator aEndR=rRanges.rend();
     585           0 :             while( aCurrRectR != aEndR )
     586             :             {
     587           0 :                 const B2DRectangle& rCurrRect( *aCurrRectR++ );
     588             : 
     589             :                 o_rEventVector.push_back(
     590             :                     SweepLineEvent( rCurrRect.getMaxX(),
     591             :                                     rCurrRect,
     592             :                                     SweepLineEvent::FINISHING_EDGE,
     593           0 :                                     (*aCurrOrientationR++) == ORIENTATION_POSITIVE ?
     594           0 :                                     SweepLineEvent::PROCEED_DOWN : SweepLineEvent::PROCEED_UP ) );
     595             :             }
     596             : 
     597             :             // sort events
     598             :             // ===========
     599             : 
     600             :             // since we use stable_sort, the order of events with the
     601             :             // same x value will not change. The elaborate two-pass
     602             :             // add above thus ensures, that for each two rectangles
     603             :             // with similar left and right x coordinates, the
     604             :             // rectangle whose left event comes first will have its
     605             :             // right event come last. This is advantageous for the
     606             :             // clip algorithm below, see handleRightEdgeCrossing().
     607             : 
     608             :             std::stable_sort( o_rEventVector.begin(),
     609           0 :                               o_rEventVector.end() );
     610           0 :         }
     611             : 
     612             :         /** Insert two active edge segments for the given rectangle.
     613             : 
     614             :             This method creates two active edge segments from the
     615             :             given rect, and inserts them into the active edge list,
     616             :             such that this stays sorted (if it was before).
     617             : 
     618             :             @param io_rEdgeList
     619             :             Active edge list to insert into
     620             : 
     621             :             @param io_rPolygons
     622             :             Vector of polygons. Each rectangle added creates one
     623             :             tentative result polygon in this vector, and the edge list
     624             :             entries holds a reference to that polygon (this _requires_
     625             :             that the polygon vector does not reallocate, i.e. it must
     626             :             have at least the maximal number of rectangles reserved)
     627             : 
     628             :             @param o_CurrentPolygon
     629             :             The then-current polygon when processing this sweep line
     630             :             event
     631             : 
     632             :             @param rCurrEvent
     633             :             The actual event that caused this call
     634             :          */
     635           0 :         void createActiveEdgesFromStartEvent( ListOfEdges&      io_rEdgeList,
     636             :                                               VectorOfPolygons& io_rPolygonPool,
     637             :                                               SweepLineEvent&   rCurrEvent )
     638             :         {
     639           0 :             ListOfEdges         aNewEdges;
     640           0 :             const B2DRectangle& rRect=rCurrEvent.getRect();
     641           0 :             const bool          bGoesDown=rCurrEvent.getEdgeDirection() == SweepLineEvent::PROCEED_DOWN;
     642             : 
     643             :             // start event - new rect starts here, needs polygon to
     644             :             // collect points into
     645           0 :             const std::ptrdiff_t nIdxPolygon=io_rPolygonPool.alloc();
     646           0 :             io_rPolygonPool.get(nIdxPolygon).setPolygonPoolIndex(nIdxPolygon);
     647             : 
     648             :             // upper edge
     649             :             aNewEdges.push_back(
     650             :                 ActiveEdge(
     651             :                     rRect,
     652           0 :                     rRect.getMinY(),
     653             :                     bGoesDown ? nIdxPolygon : -1,
     654             :                     ActiveEdge::UPPER,
     655           0 :                     bGoesDown ? ActiveEdge::PROCEED_LEFT : ActiveEdge::PROCEED_RIGHT) );
     656             :             // lower edge
     657             :             aNewEdges.push_back(
     658             :                 ActiveEdge(
     659             :                     rRect,
     660           0 :                     rRect.getMaxY(),
     661             :                     bGoesDown ? -1 : nIdxPolygon,
     662             :                     ActiveEdge::LOWER,
     663           0 :                     bGoesDown ? ActiveEdge::PROCEED_RIGHT : ActiveEdge::PROCEED_LEFT ) );
     664             : 
     665             :             // furthermore, have to respect a special tie-breaking
     666             :             // rule here, for edges which share the same y value:
     667             :             // newly added upper edges must be inserted _before_ any
     668             :             // other edge with the same y value, and newly added lower
     669             :             // edges must be _after_ all other edges with the same
     670             :             // y. This ensures that the left vertical edge processing
     671             :             // below encounters the upper edge of the current rect
     672             :             // first, and the lower edge last, which automatically
     673             :             // starts and finishes this rect correctly (as only then,
     674             :             // the polygon will have their associated active edges
     675             :             // set).
     676           0 :             const double                nMinY( rRect.getMinY() );
     677           0 :             const double                nMaxY( rRect.getMaxY() );
     678           0 :             ListOfEdges::iterator       aCurr( io_rEdgeList.begin() );
     679           0 :             const ListOfEdges::iterator aEnd ( io_rEdgeList.end() );
     680           0 :             while( aCurr != aEnd )
     681             :             {
     682           0 :                 const double nCurrY( aCurr->getInvariantCoord() );
     683             : 
     684           0 :                 if( nCurrY >= nMinY &&
     685           0 :                     aNewEdges.size() == 2 ) // only add, if not yet done.
     686             :                 {
     687             :                     // insert upper edge _before_ aCurr. Thus, it will
     688             :                     // be the first entry for a range of equal y
     689             :                     // values. Using splice here, since we hold
     690             :                     // references to the moved list element!
     691             :                     io_rEdgeList.splice( aCurr,
     692             :                                          aNewEdges,
     693           0 :                                          aNewEdges.begin() );
     694             :                 }
     695             : 
     696           0 :                 if( nCurrY > nMaxY )
     697             :                 {
     698             :                     // insert lower edge _before_ aCurr. Thus, it will
     699             :                     // be the last entry for a range of equal y values
     700             :                     // (aCurr is the first entry strictly larger than
     701             :                     // nMaxY). Using splice here, since we hold
     702             :                     // references to the moved list element!
     703             :                     io_rEdgeList.splice( aCurr,
     704             :                                          aNewEdges,
     705           0 :                                          aNewEdges.begin() );
     706             :                     // done with insertion, can early-exit here.
     707           0 :                     return;
     708             :                 }
     709             : 
     710           0 :                 ++aCurr;
     711             :             }
     712             : 
     713             :             // append remainder of aNewList (might still contain 2 or
     714             :             // 1 elements, depending of the contents of io_rEdgeList).
     715             :             io_rEdgeList.splice( aCurr,
     716           0 :                                  aNewEdges );
     717             :         }
     718             : 
     719           0 :         inline bool isSameRect(ActiveEdge&              rEdge,
     720             :                                const basegfx::B2DRange& rRect)
     721             :         {
     722           0 :             return &rEdge.getRect() == &rRect;
     723             :         }
     724             : 
     725             :         // wow what a hack. necessary because stl's list::erase does
     726             :         // not eat reverse_iterator
     727             :         template<typename Cont, typename Iter> Iter eraseFromList(Cont&, Iter);
     728           0 :         template<> inline ListOfEdges::iterator eraseFromList(
     729             :             ListOfEdges& rList, ListOfEdges::iterator aIter)
     730             :         {
     731           0 :             return rList.erase(aIter);
     732             :         }
     733           0 :         template<> inline ListOfEdges::reverse_iterator eraseFromList(
     734             :             ListOfEdges& rList, ListOfEdges::reverse_iterator aIter)
     735             :         {
     736             :             return ListOfEdges::reverse_iterator(
     737           0 :                     rList.erase(boost::prior(aIter.base())));
     738             :         }
     739             : 
     740             :         template<int bPerformErase,
     741           0 :                  typename Iterator> inline void processActiveEdges(
     742             :             Iterator          first,
     743             :             Iterator          last,
     744             :             ListOfEdges&      rActiveEdgeList,
     745             :             SweepLineEvent&   rCurrEvent,
     746             :             VectorOfPolygons& rPolygonPool,
     747             :             B2DPolyPolygon&   rRes )
     748             :         {
     749           0 :             const basegfx::B2DRange& rCurrRect=rCurrEvent.getRect();
     750             : 
     751             :             // fast-forward to rCurrEvent's first active edge (holds
     752             :             // for both starting and finishing sweep line events, a
     753             :             // rect is regarded _outside_ any rects whose events have
     754             :             // started earlier
     755           0 :             first = std::find_if(first, last,
     756             :                                  boost::bind(
     757             :                          &isSameRect,
     758             :                                      _1,
     759           0 :                                      boost::cref(rCurrRect)));
     760             : 
     761           0 :             if(first == last)
     762           0 :                 return;
     763             : 
     764           0 :             int nCount=0;
     765           0 :             std::ptrdiff_t nCurrPolyIdx=-1;
     766           0 :             while(first != last)
     767             :             {
     768           0 :                 if( nCurrPolyIdx == -1 )
     769           0 :                     nCurrPolyIdx=first->getTargetPolygonIndex();
     770             : 
     771             :                 OSL_ASSERT(nCurrPolyIdx != -1);
     772             : 
     773             :                 // second encounter of my rect -> second edge
     774             :                 // encountered, done
     775             :                 const bool bExit=
     776             :                     nCount &&
     777           0 :                     isSameRect(*first,
     778           0 :                                rCurrRect);
     779             : 
     780             :                 // deal with current active edge
     781           0 :                 nCurrPolyIdx =
     782           0 :                     rPolygonPool.get(nCurrPolyIdx).intersect(
     783             :                         rCurrEvent,
     784           0 :                         *first,
     785             :                         rPolygonPool,
     786             :                         rRes,
     787             :                         bExit);
     788             : 
     789             :                 // prune upper & lower active edges, if requested
     790           0 :                 if( bPerformErase && (bExit || !nCount) )
     791           0 :                     first = eraseFromList(rActiveEdgeList,first);
     792             :                 else
     793           0 :                     ++first;
     794             : 
     795             :                 // delayed exit, had to prune first
     796           0 :                 if( bExit )
     797           0 :                     return;
     798             : 
     799           0 :                 ++nCount;
     800             :             }
     801             :         }
     802             : 
     803           0 :         template<int bPerformErase> inline void processActiveEdgesTopDown(
     804             :             SweepLineEvent&   rCurrEvent,
     805             :             ListOfEdges&      rActiveEdgeList,
     806             :             VectorOfPolygons& rPolygonPool,
     807             :             B2DPolyPolygon&   rRes )
     808             :         {
     809           0 :             processActiveEdges<bPerformErase>(
     810             :                 rActiveEdgeList. begin(),
     811             :                 rActiveEdgeList. end(),
     812             :                 rActiveEdgeList,
     813             :                 rCurrEvent,
     814             :                 rPolygonPool,
     815           0 :                 rRes);
     816           0 :         }
     817             : 
     818           0 :         template<int bPerformErase> inline void processActiveEdgesBottomUp(
     819             :             SweepLineEvent&   rCurrEvent,
     820             :             ListOfEdges&      rActiveEdgeList,
     821             :             VectorOfPolygons& rPolygonPool,
     822             :             B2DPolyPolygon&   rRes )
     823             :         {
     824           0 :             processActiveEdges<bPerformErase>(
     825             :                 rActiveEdgeList. rbegin(),
     826             :                 rActiveEdgeList. rend(),
     827             :                 rActiveEdgeList,
     828             :                 rCurrEvent,
     829             :                 rPolygonPool,
     830           0 :                 rRes);
     831           0 :         }
     832             : 
     833             :         enum{ NoErase=0, PerformErase=1 };
     834             : 
     835           0 :         void handleStartingEdge( SweepLineEvent&   rCurrEvent,
     836             :                                  ListOfEdges&      rActiveEdgeList,
     837             :                                  VectorOfPolygons& rPolygonPool,
     838             :                                  B2DPolyPolygon&   rRes)
     839             :         {
     840             :             // inject two new active edges for rect
     841             :             createActiveEdgesFromStartEvent( rActiveEdgeList,
     842             :                                              rPolygonPool,
     843           0 :                                              rCurrEvent );
     844             : 
     845           0 :             if( SweepLineEvent::PROCEED_DOWN == rCurrEvent.getEdgeDirection() )
     846             :                 processActiveEdgesTopDown<NoErase>(
     847           0 :                     rCurrEvent, rActiveEdgeList, rPolygonPool, rRes);
     848             :             else
     849             :                 processActiveEdgesBottomUp<NoErase>(
     850           0 :                     rCurrEvent, rActiveEdgeList, rPolygonPool, rRes);
     851           0 :         }
     852             : 
     853           0 :         void handleFinishingEdge( SweepLineEvent&   rCurrEvent,
     854             :                                   ListOfEdges&      rActiveEdgeList,
     855             :                                   VectorOfPolygons& rPolygonPool,
     856             :                                   B2DPolyPolygon&   rRes)
     857             :         {
     858           0 :             if( SweepLineEvent::PROCEED_DOWN == rCurrEvent.getEdgeDirection() )
     859             :                 processActiveEdgesTopDown<PerformErase>(
     860           0 :                     rCurrEvent, rActiveEdgeList, rPolygonPool, rRes);
     861             :             else
     862             :                 processActiveEdgesBottomUp<PerformErase>(
     863           0 :                     rCurrEvent, rActiveEdgeList, rPolygonPool, rRes);
     864           0 :         }
     865             : 
     866           0 :         inline void handleSweepLineEvent( SweepLineEvent&   rCurrEvent,
     867             :                                           ListOfEdges&      rActiveEdgeList,
     868             :                                           VectorOfPolygons& rPolygonPool,
     869             :                                           B2DPolyPolygon&   rRes)
     870             :         {
     871           0 :             if( SweepLineEvent::STARTING_EDGE == rCurrEvent.getEdgeType() )
     872           0 :                 handleStartingEdge(rCurrEvent,rActiveEdgeList,rPolygonPool,rRes);
     873             :             else
     874           0 :                 handleFinishingEdge(rCurrEvent,rActiveEdgeList,rPolygonPool,rRes);
     875           0 :         }
     876             :     }
     877             : 
     878             :     namespace tools
     879             :     {
     880           0 :         B2DPolyPolygon solveCrossovers(const std::vector<B2DRange>& rRanges,
     881             :                                        const std::vector<B2VectorOrientation>& rOrientations)
     882             :         {
     883             :             // sweep-line algorithm to generate a poly-polygon
     884             :             // from a bunch of rectangles
     885             :             // ===============================================
     886             : 
     887             :             // This algorithm uses the well-known sweep line
     888             :             // concept, explained in every good text book about
     889             :             // computational geometry.
     890             : 
     891             :             // We start with creating two structures for every
     892             :             // rectangle, one representing the left x coordinate,
     893             :             // one representing the right x coordinate (and both
     894             :             // referencing the original rect). These structs are
     895             :             // sorted with increasing x coordinates.
     896             : 
     897             :             // Then, we start processing the resulting list from
     898             :             // the beginning. Every entry in the list defines a
     899             :             // point in time of the line sweeping from left to
     900             :             // right across all rectangles.
     901           0 :             VectorOfEvents aSweepLineEvents;
     902             :             setupSweepLineEventListFromRanges( aSweepLineEvents,
     903             :                                                rRanges,
     904           0 :                                                rOrientations );
     905             : 
     906           0 :             B2DPolyPolygon   aRes;
     907           0 :             VectorOfPolygons aPolygonPool;
     908           0 :             ListOfEdges      aActiveEdgeList;
     909             : 
     910             :             // sometimes not enough, but a usable compromise
     911           0 :             aPolygonPool.reserve( rRanges.size() );
     912             : 
     913             :             std::for_each( aSweepLineEvents.begin(),
     914             :                            aSweepLineEvents.end(),
     915             :                            boost::bind(
     916             :                                &handleSweepLineEvent,
     917             :                                _1,
     918             :                                boost::ref(aActiveEdgeList),
     919             :                                boost::ref(aPolygonPool),
     920           0 :                                boost::ref(aRes)) );
     921             : 
     922           0 :             return aRes;
     923             :         }
     924             :     }
     925           3 : }
     926             : 
     927             : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */

Generated by: LCOV version 1.10