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

Generated by: LCOV version 1.10