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