summaryrefslogtreecommitdiff
path: root/basegfx/source/range/b2drangeclipper.cxx
diff options
context:
space:
mode:
Diffstat (limited to 'basegfx/source/range/b2drangeclipper.cxx')
-rw-r--r--basegfx/source/range/b2drangeclipper.cxx140
1 files changed, 70 insertions, 70 deletions
diff --git a/basegfx/source/range/b2drangeclipper.cxx b/basegfx/source/range/b2drangeclipper.cxx
index 6546b6a13c09..235c09f0b129 100644
--- a/basegfx/source/range/b2drangeclipper.cxx
+++ b/basegfx/source/range/b2drangeclipper.cxx
@@ -2,7 +2,7 @@
/*************************************************************************
*
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
- *
+ *
* Copyright 2008 by Sun Microsystems, Inc.
*
* OpenOffice.org - a multi-platform office productivity suite
@@ -54,8 +54,8 @@ namespace basegfx
{
namespace
{
- // Generating a poly-polygon from a bunch of rectangles
- //
+ // Generating a poly-polygon from a bunch of rectangles
+ //
// Helper functionality for sweep-line algorithm
// ====================================================
@@ -93,13 +93,13 @@ namespace basegfx
PROCEED_RIGHT=1
};
- /** Create active edge
+ /** Create active edge
@param rRect
Rectangle this edge is part of
@param fInvariantCoord
- The invariant ccordinate value of this edge
+ The invariant ccordinate value of this edge
@param eEdgeType
Is fInvariantCoord the lower or the higher value, for
@@ -117,12 +117,12 @@ namespace basegfx
meEdgeDirection( eEdgeDirection )
{}
- double getInvariantCoord() const { return mfInvariantCoord; }
+ double getInvariantCoord() const { return mfInvariantCoord; }
const B2DRectangle& getRect() const { return *mpAssociatedRect; }
- std::ptrdiff_t getTargetPolygonIndex() const { return mnPolygonIdx; }
- void setTargetPolygonIndex( std::ptrdiff_t nIdx ) { mnPolygonIdx = nIdx; }
- EdgeType getEdgeType() const { return meEdgeType; }
- EdgeDirection getEdgeDirection() const { return meEdgeDirection; }
+ std::ptrdiff_t getTargetPolygonIndex() const { return mnPolygonIdx; }
+ void setTargetPolygonIndex( std::ptrdiff_t nIdx ) { mnPolygonIdx = nIdx; }
+ EdgeType getEdgeType() const { return meEdgeType; }
+ EdgeDirection getEdgeDirection() const { return meEdgeDirection; }
/// For STL sort
bool operator<( const ActiveEdge& rRHS ) const { return mfInvariantCoord < rRHS.mfInvariantCoord; }
@@ -156,7 +156,7 @@ namespace basegfx
std::ptrdiff_t mnPolygonIdx;
/// 'upper' or 'lower' edge of original rectangle.
- EdgeType meEdgeType;
+ EdgeType meEdgeType;
/// 'left' or 'right'
EdgeDirection meEdgeDirection;
@@ -167,7 +167,7 @@ namespace basegfx
/** Element of the sweep line event list
-
+
As the sweep line traverses across the overall area,
rectangle edges parallel to it generate events, and
rectangle edges orthogonal to it generate active
@@ -210,9 +210,9 @@ namespace basegfx
Is fPos the lower or the higher value, for the
rectangle this event is generated for?
*/
- SweepLineEvent( double fPos,
+ SweepLineEvent( double fPos,
const B2DRectangle& rRect,
- EdgeType eEdgeType,
+ EdgeType eEdgeType,
EdgeDirection eDirection) :
mfPos( fPos ),
mpAssociatedRect( &rRect ),
@@ -220,17 +220,17 @@ namespace basegfx
meEdgeDirection( eDirection )
{}
- double getPos() const { return mfPos; }
+ double getPos() const { return mfPos; }
const B2DRectangle& getRect() const { return *mpAssociatedRect; }
- EdgeType getEdgeType() const { return meEdgeType; }
- EdgeDirection getEdgeDirection() const { return meEdgeDirection; }
+ EdgeType getEdgeType() const { return meEdgeType; }
+ EdgeDirection getEdgeDirection() const { return meEdgeDirection; }
/// For STL sort
bool operator<( const SweepLineEvent& rRHS ) const { return mfPos < rRHS.mfPos; }
private:
/// position of the event, in the direction of the line sweep
- double mfPos;
+ double mfPos;
/** Rectangle this event is generated for
@@ -244,7 +244,7 @@ namespace basegfx
const B2DRectangle* mpAssociatedRect;
/// 'upper' or 'lower' edge of original rectangle.
- EdgeType meEdgeType;
+ EdgeType meEdgeType;
/// 'up' or 'down'
EdgeDirection meEdgeDirection;
@@ -254,7 +254,7 @@ namespace basegfx
/** Smart point container for B2DMultiRange::getPolyPolygon()
-
+
This class provides methods needed only here, and is used
as a place to store some additional information per
polygon. Also, most of the intersection logic is
@@ -265,7 +265,7 @@ namespace basegfx
public:
/** Create polygon
*/
- ImplPolygon() :
+ ImplPolygon() :
mpLeadingRightEdge(NULL),
mnIdx(-1),
maPoints(),
@@ -279,8 +279,8 @@ namespace basegfx
bool isFinished() const { return mbIsFinished; }
/// Add point to the end of the existing points
- void append( const B2DPoint& rPoint )
- {
+ void append( const B2DPoint& rPoint )
+ {
OSL_PRECOND( maPoints.empty() ||
maPoints.back().getX() == rPoint.getX() ||
maPoints.back().getY() == rPoint.getY(),
@@ -290,7 +290,7 @@ namespace basegfx
maPoints.back() != rPoint )
{
// avoid duplicate points
- maPoints.push_back( rPoint );
+ maPoints.push_back( rPoint );
}
}
@@ -317,25 +317,25 @@ namespace basegfx
list of upcoming active edges).
*/
std::ptrdiff_t intersect( SweepLineEvent& rEvent,
- ActiveEdge& rActiveEdge,
+ ActiveEdge& rActiveEdge,
VectorOfPolygons& rPolygonPool,
B2DPolyPolygon& rRes,
bool isFinishingEdge )
{
OSL_PRECOND( !isFinished(),
"ImplPolygon::intersect(): called on already finished polygon!" );
- OSL_PRECOND( !isFinishingEdge
+ OSL_PRECOND( !isFinishingEdge
|| (isFinishingEdge && &rEvent.getRect() == &rActiveEdge.getRect()),
"ImplPolygon::intersect(): inconsistent ending!" );
- const B2DPoint aIntersectionPoint( rEvent.getPos(),
+ const B2DPoint aIntersectionPoint( rEvent.getPos(),
rActiveEdge.getInvariantCoord() );
// intersection point, goes to our polygon
// unconditionally
append(aIntersectionPoint);
- const bool isSweepLineEnteringRect(
+ const bool isSweepLineEnteringRect(
rEvent.getEdgeType() == SweepLineEvent::STARTING_EDGE);
if( isFinishingEdge )
{
@@ -361,8 +361,8 @@ namespace basegfx
{
OSL_ENSURE( rActiveEdge.getTargetPolygonIndex() != -1,
"ImplPolygon::intersect(): non-trivial intersection hit empty polygon!" );
-
- const bool isHittingLeftEdge(
+
+ const bool isHittingLeftEdge(
rActiveEdge.getEdgeDirection() == ActiveEdge::PROCEED_LEFT);
if( isHittingLeftEdge )
@@ -376,7 +376,7 @@ namespace basegfx
rPolygonPool);
}
}
-
+
private:
std::ptrdiff_t getPolygonPoolIndex() const { return mnIdx; }
@@ -385,7 +385,7 @@ namespace basegfx
{
const bool isActiveEdgeProceedLeft(
rActiveEdge.getEdgeDirection() == ActiveEdge::PROCEED_LEFT);
- const bool isSweepLineEnteringRect(
+ const bool isSweepLineEnteringRect(
rEvent.getEdgeType() == SweepLineEvent::STARTING_EDGE);
(void)isActiveEdgeProceedLeft;
(void)isSweepLineEnteringRect;
@@ -402,7 +402,7 @@ namespace basegfx
{
OSL_ENSURE( rActiveEdge.getEdgeDirection() == ActiveEdge::PROCEED_RIGHT,
"ImplPolygon::handleInitialOwnRightEdge(): start edge wrong polygon order" );
-
+
rActiveEdge.setTargetPolygonIndex(mnIdx);
mpLeadingRightEdge = &rActiveEdge;
}
@@ -442,7 +442,7 @@ namespace basegfx
}
}
- std::ptrdiff_t handleComplexLeftEdge(ActiveEdge& rActiveEdge,
+ std::ptrdiff_t handleComplexLeftEdge(ActiveEdge& rActiveEdge,
const B2DPoint& rIntersectionPoint,
VectorOfPolygons& rPolygonPool,
B2DPolyPolygon& rRes)
@@ -491,7 +491,7 @@ namespace basegfx
}
}
- std::ptrdiff_t handleComplexRightEdge(ActiveEdge& rActiveEdge,
+ std::ptrdiff_t handleComplexRightEdge(ActiveEdge& rActiveEdge,
const B2DPoint& rIntersectionPoint,
VectorOfPolygons& rPolygonPool)
{
@@ -499,10 +499,10 @@ namespace basegfx
ImplPolygon& rTmp=rPolygonPool.get(nTmpIdx);
rTmp.append(rIntersectionPoint);
-
+
rActiveEdge.setTargetPolygonIndex(mnIdx);
mpLeadingRightEdge = &rActiveEdge;
-
+
rTmp.mpLeadingRightEdge = NULL;
return nTmpIdx;
@@ -510,7 +510,7 @@ namespace basegfx
/// True when sweep line hits our own active edge
bool metOwnEdge(const SweepLineEvent& rEvent,
- ActiveEdge& rActiveEdge)
+ ActiveEdge& rActiveEdge)
{
const bool bHitOwnEdge=&rEvent.getRect() == &rActiveEdge.getRect();
return bHitOwnEdge;
@@ -522,7 +522,7 @@ namespace basegfx
B2DPolygon aRes;
std::for_each( maPoints.begin(),
maPoints.end(),
- boost::bind(
+ boost::bind(
&B2DPolygon::append,
boost::ref(aRes),
_1,
@@ -533,13 +533,13 @@ namespace basegfx
/** Finish this polygon, push to result set.
*/
- void finish(B2DPolyPolygon& rRes)
- {
+ void finish(B2DPolyPolygon& rRes)
+ {
OSL_PRECOND( maPoints.empty() ||
maPoints.front().getX() == maPoints.back().getX() ||
maPoints.front().getY() == maPoints.back().getY(),
"ImplPolygon::finish(): first and last point violate 90 degree line angle constraint!" );
-
+
mbIsFinished = true;
mpLeadingRightEdge = NULL;
@@ -561,7 +561,7 @@ namespace basegfx
std::vector<B2DPoint> maPoints;
/// When true, this polygon is 'done', i.e. nothing must be added anymore.
- bool mbIsFinished;
+ bool mbIsFinished;
};
/** Init sweep line event list
@@ -591,7 +591,7 @@ namespace basegfx
{
const B2DRectangle& rCurrRect( *aCurrRect++ );
- o_rEventVector.push_back(
+ o_rEventVector.push_back(
SweepLineEvent( rCurrRect.getMinX(),
rCurrRect,
SweepLineEvent::STARTING_EDGE,
@@ -608,7 +608,7 @@ namespace basegfx
{
const B2DRectangle& rCurrRect( *aCurrRectR++ );
- o_rEventVector.push_back(
+ o_rEventVector.push_back(
SweepLineEvent( rCurrRect.getMaxX(),
rCurrRect,
SweepLineEvent::FINISHING_EDGE,
@@ -657,8 +657,8 @@ namespace basegfx
@param rCurrEvent
The actual event that caused this call
*/
- void createActiveEdgesFromStartEvent( ListOfEdges& io_rEdgeList,
- VectorOfPolygons& io_rPolygonPool,
+ void createActiveEdgesFromStartEvent( ListOfEdges& io_rEdgeList,
+ VectorOfPolygons& io_rPolygonPool,
SweepLineEvent& rCurrEvent )
{
ListOfEdges aNewEdges;
@@ -671,16 +671,16 @@ namespace basegfx
io_rPolygonPool.get(nIdxPolygon).setPolygonPoolIndex(nIdxPolygon);
// upper edge
- aNewEdges.push_back(
- ActiveEdge(
+ aNewEdges.push_back(
+ ActiveEdge(
rRect,
rRect.getMinY(),
bGoesDown ? nIdxPolygon : -1,
ActiveEdge::UPPER,
bGoesDown ? ActiveEdge::PROCEED_LEFT : ActiveEdge::PROCEED_RIGHT) );
// lower edge
- aNewEdges.push_back(
- ActiveEdge(
+ aNewEdges.push_back(
+ ActiveEdge(
rRect,
rRect.getMaxY(),
bGoesDown ? -1 : nIdxPolygon,
@@ -698,22 +698,22 @@ namespace basegfx
// starts and finishes this rect correctly (as only then,
// the polygon will have their associated active edges
// set).
- const double nMinY( rRect.getMinY() );
- const double nMaxY( rRect.getMaxY() );
- ListOfEdges::iterator aCurr( io_rEdgeList.begin() );
+ const double nMinY( rRect.getMinY() );
+ const double nMaxY( rRect.getMaxY() );
+ ListOfEdges::iterator aCurr( io_rEdgeList.begin() );
const ListOfEdges::iterator aEnd ( io_rEdgeList.end() );
while( aCurr != aEnd )
{
const double nCurrY( aCurr->getInvariantCoord() );
- if( nCurrY >= nMinY &&
+ if( nCurrY >= nMinY &&
aNewEdges.size() == 2 ) // only add, if not yet done.
{
// insert upper edge _before_ aCurr. Thus, it will
// be the first entry for a range of equal y
// values. Using splice here, since we hold
// references to the moved list element!
- io_rEdgeList.splice( aCurr,
+ io_rEdgeList.splice( aCurr,
aNewEdges,
aNewEdges.begin() );
}
@@ -725,7 +725,7 @@ namespace basegfx
// (aCurr is the first entry strictly larger than
// nMaxY). Using splice here, since we hold
// references to the moved list element!
- io_rEdgeList.splice( aCurr,
+ io_rEdgeList.splice( aCurr,
aNewEdges,
aNewEdges.begin() );
// done with insertion, can early-exit here.
@@ -798,13 +798,13 @@ namespace basegfx
// second encounter of my rect -> second edge
// encountered, done
const bool bExit=
- nCount &&
+ nCount &&
isSameRect(*first,
rCurrRect);
// deal with current active edge
- nCurrPolyIdx =
- rPolygonPool.get(nCurrPolyIdx).intersect(
+ nCurrPolyIdx =
+ rPolygonPool.get(nCurrPolyIdx).intersect(
rCurrEvent,
*first,
rPolygonPool,
@@ -825,29 +825,29 @@ namespace basegfx
}
}
- template<int bPerformErase> inline void processActiveEdgesTopDown(
+ template<int bPerformErase> inline void processActiveEdgesTopDown(
SweepLineEvent& rCurrEvent,
ListOfEdges& rActiveEdgeList,
VectorOfPolygons& rPolygonPool,
B2DPolyPolygon& rRes )
{
processActiveEdges<bPerformErase>(
- rActiveEdgeList. begin(),
- rActiveEdgeList. end(),
+ rActiveEdgeList. begin(),
+ rActiveEdgeList. end(),
rActiveEdgeList,
rCurrEvent,
rPolygonPool,
rRes);
}
- template<int bPerformErase> inline void processActiveEdgesBottomUp(
+ template<int bPerformErase> inline void processActiveEdgesBottomUp(
SweepLineEvent& rCurrEvent,
ListOfEdges& rActiveEdgeList,
VectorOfPolygons& rPolygonPool,
B2DPolyPolygon& rRes )
{
processActiveEdges<bPerformErase>(
- rActiveEdgeList. rbegin(),
+ rActiveEdgeList. rbegin(),
rActiveEdgeList. rend(),
rActiveEdgeList,
rCurrEvent,
@@ -866,7 +866,7 @@ namespace basegfx
createActiveEdgesFromStartEvent( rActiveEdgeList,
rPolygonPool,
rCurrEvent );
-
+
if( SweepLineEvent::PROCEED_DOWN == rCurrEvent.getEdgeDirection() )
processActiveEdgesTopDown<NoErase>(
rCurrEvent, rActiveEdgeList, rPolygonPool, rRes);
@@ -902,7 +902,7 @@ namespace basegfx
namespace tools
{
- B2DPolyPolygon solveCrossovers(const std::vector<B2DRange>& rRanges,
+ B2DPolyPolygon solveCrossovers(const std::vector<B2DRange>& rRanges,
const std::vector<B2VectorOrientation>& rOrientations)
{
// sweep-line algorithm to generate a poly-polygon
@@ -911,8 +911,8 @@ namespace basegfx
//
// This algorithm uses the well-known sweep line
// concept, explained in every good text book about
- // computational geometry.
- //
+ // computational geometry.
+ //
// We start with creating two structures for every
// rectangle, one representing the left x coordinate,
// one representing the right x coordinate (and both
@@ -930,7 +930,7 @@ namespace basegfx
B2DPolyPolygon aRes;
VectorOfPolygons aPolygonPool;
- ListOfEdges aActiveEdgeList;
+ ListOfEdges aActiveEdgeList;
// sometimes not enough, but a usable compromise
aPolygonPool.reserve( rRanges.size() );
generated by cgit v1.2.3 (git 2.39.1) at 2024-04-19 19:17:13 +0000