summaryrefslogtreecommitdiff
path: root/basegfx/source/range
diff options
context:
space:
mode:
Diffstat (limited to 'basegfx/source/range')
-rw-r--r--basegfx/source/range/b2dmultirange.cxx282
-rw-r--r--basegfx/source/range/b2dpolyrange.cxx371
-rw-r--r--basegfx/source/range/b2drangeclipper.cxx950
-rw-r--r--basegfx/source/range/makefile.mk3
4 files changed, 1323 insertions, 283 deletions
diff --git a/basegfx/source/range/b2dmultirange.cxx b/basegfx/source/range/b2dmultirange.cxx
deleted file mode 100644
index 64c3cf5ab813..000000000000
--- a/basegfx/source/range/b2dmultirange.cxx
+++ /dev/null
@@ -1,282 +0,0 @@
-/*************************************************************************
- *
- * 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
- *
- * $RCSfile: b2dmultirange.cxx,v $
- * $Revision: 1.8 $
- *
- * This file is part of OpenOffice.org.
- *
- * OpenOffice.org is free software: you can redistribute it and/or modify
- * it under the terms of the GNU Lesser General Public License version 3
- * only, as published by the Free Software Foundation.
- *
- * OpenOffice.org is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU Lesser General Public License version 3 for more details
- * (a copy is included in the LICENSE file that accompanied this code).
- *
- * You should have received a copy of the GNU Lesser General Public License
- * version 3 along with OpenOffice.org. If not, see
- * <http://www.openoffice.org/license.html>
- * for a copy of the LGPLv3 License.
- *
- ************************************************************************/
-
-// MARKER(update_precomp.py): autogen include statement, do not remove
-#include "precompiled_basegfx.hxx"
-#include <basegfx/range/b2drange.hxx>
-#include <basegfx/tuple/b2dtuple.hxx>
-#include <basegfx/polygon/b2dpolypolygon.hxx>
-#include <basegfx/range/b2dmultirange.hxx>
-#include <basegfx/polygon/b2dpolygontools.hxx>
-#include <basegfx/polygon/b2dpolypolygontools.hxx>
-#include <basegfx/polygon/b2dpolypolygoncutter.hxx>
-#include <boost/bind.hpp>
-#include <boost/mem_fn.hpp>
-#include <algorithm>
-#include <vector>
-
-
-namespace basegfx
-{
- class ImplB2DMultiRange
- {
- public:
- ImplB2DMultiRange() :
- maBounds(),
- maRanges()
- {
- }
-
- explicit ImplB2DMultiRange( const B2DRange& rRange ) :
- maBounds(),
- maRanges( 1, rRange )
- {
- }
-
- bool isEmpty() const
- {
- // no ranges at all, or all ranges empty
- return maRanges.empty() ||
- ::std::count_if( maRanges.begin(),
- maRanges.end(),
- ::boost::mem_fn( &B2DRange::isEmpty ) )
- == static_cast<VectorOfRanges::difference_type>(maRanges.size());
- }
-
- void reset()
- {
- // swap in empty vector
- VectorOfRanges aTmp;
- maRanges.swap( aTmp );
-
- maBounds.reset();
- }
-
- template< typename ValueType > bool isInside( const ValueType& rValue ) const
- {
- if( !maBounds.isInside( rValue ) )
- return false;
-
- // cannot use ::boost::bind here, since isInside is overloaded.
- // It is currently not possible to resolve the overload
- // by considering one of the other template arguments.
- VectorOfRanges::const_iterator aCurr( maRanges.begin() );
- const VectorOfRanges::const_iterator aEnd ( maRanges.end() );
- while( aCurr != aEnd )
- if( aCurr->isInside( rValue ) )
- return true;
-
- return false;
- }
-
- bool overlaps( const B2DRange& rRange ) const
- {
- if( !maBounds.overlaps( rRange ) )
- return false;
-
- const VectorOfRanges::const_iterator aEnd( maRanges.end() );
- return ::std::find_if( maRanges.begin(),
- aEnd,
- ::boost::bind<bool>( ::boost::mem_fn( &B2DRange::overlaps ),
- _1,
- rRange ) ) != aEnd;
- }
-
- void addRange( const B2DRange& rRange )
- {
- maRanges.push_back( rRange );
- maBounds.expand( rRange );
- }
-
- B2DRange getBounds() const
- {
- return maBounds;
- }
-
- B2DPolyPolygon getPolyPolygon() const
- {
- B2DPolyPolygon aRes;
-
- // Make range vector unique ( have to avoid duplicate
- // rectangles. The polygon clipper will return an empty
- // result in this case).
- VectorOfRanges aUniqueRanges;
- aUniqueRanges.reserve( maRanges.size() );
-
- VectorOfRanges::const_iterator aCurr( maRanges.begin() );
- const VectorOfRanges::const_iterator aEnd ( maRanges.end() );
- while( aCurr != aEnd )
- {
- // TODO(F3): It's plain wasted resources to apply a
- // general clipping algorithm to the problem at
- // hand. Go for a dedicated, scan-line-based approach.
- VectorOfRanges::const_iterator aCurrScan( aCurr+1 );
- VectorOfRanges::const_iterator aFound( aEnd );
- while( aCurrScan != aEnd )
- {
- if( aCurrScan->equal( *aCurr ) ||
- aCurrScan->isInside( *aCurr ) )
- {
- // current probe is equal to aCurr, or
- // completely contains aCurr. Thus, stop
- // searching, because aCurr is definitely not
- // a member of the unique rect list
- aFound = aCurrScan;
- break;
- }
-
- ++aCurrScan;
- }
-
- if( aFound == aEnd )
- {
- // check whether aCurr is fully contained in one
- // of the already added rects. If yes, we can skip
- // it.
- bool bUnique( true );
- VectorOfRanges::const_iterator aCurrUnique( aUniqueRanges.begin() );
- VectorOfRanges::const_iterator aEndUnique ( aUniqueRanges.end() );
- while( aCurrUnique != aEndUnique )
- {
- if( aCurrUnique->isInside( *aCurr ) )
- {
- // fully contained, no need to add
- bUnique = false;
- break;
- }
-
- ++aCurrUnique;
- }
-
- if( bUnique )
- aUniqueRanges.push_back( *aCurr );
- }
-
- ++aCurr;
- }
-
- VectorOfRanges::const_iterator aCurrUnique( aUniqueRanges.begin() );
- const VectorOfRanges::const_iterator aEndUnique ( aUniqueRanges.end() );
- while( aCurrUnique != aEndUnique )
- {
- // simply merge all unique parts (OR)
- aRes.append( tools::createPolygonFromRect( *aCurrUnique++ ) );
- }
-
- // remove redundant intersections. Note: since all added
- // rectangles are positively oriented, this method cannot
- // generate any holes.
- aRes = basegfx::tools::solveCrossovers(aRes);
- aRes = basegfx::tools::stripNeutralPolygons(aRes);
- aRes = basegfx::tools::stripDispensablePolygons(aRes, false);
-
- return aRes;
- }
-
- private:
- typedef ::std::vector< B2DRange > VectorOfRanges;
-
- B2DRange maBounds;
- VectorOfRanges maRanges;
- };
-
-
- // ====================================================================
-
-
- B2DMultiRange::B2DMultiRange() :
- mpImpl()
- {
- }
-
- B2DMultiRange::B2DMultiRange( const B2DRange& rRange ) :
- mpImpl( ImplB2DMultiRange( rRange ) )
- {
- }
-
- B2DMultiRange::~B2DMultiRange()
- {
- // otherwise, ImplB2DMultiRange would be an incomplete type
- }
-
- B2DMultiRange::B2DMultiRange( const B2DMultiRange& rSrc ) :
- mpImpl( rSrc.mpImpl )
- {
- }
-
- B2DMultiRange& B2DMultiRange::operator=( const B2DMultiRange& rSrc )
- {
- mpImpl = rSrc.mpImpl;
- return *this;
- }
-
- bool B2DMultiRange::isEmpty() const
- {
- return mpImpl->isEmpty();
- }
-
- void B2DMultiRange::reset()
- {
- mpImpl->reset();
- }
-
- bool B2DMultiRange::isInside( const B2DTuple& rTuple ) const
- {
- return mpImpl->isInside( rTuple );
- }
-
- bool B2DMultiRange::isInside( const B2DRange& rRange ) const
- {
- return mpImpl->isInside( rRange );
- }
-
- bool B2DMultiRange::overlaps( const B2DRange& rRange ) const
- {
- return mpImpl->overlaps( rRange );
- }
-
- void B2DMultiRange::addRange( const B2DRange& rRange )
- {
- mpImpl->addRange( rRange );
- }
-
- B2DRange B2DMultiRange::getBounds() const
- {
- return mpImpl->getBounds();
- }
-
- B2DPolyPolygon B2DMultiRange::getPolyPolygon() const
- {
- return mpImpl->getPolyPolygon();
- }
-
-} // end of namespace basegfx
-
-// eof
diff --git a/basegfx/source/range/b2dpolyrange.cxx b/basegfx/source/range/b2dpolyrange.cxx
new file mode 100644
index 000000000000..c4969b38712c
--- /dev/null
+++ b/basegfx/source/range/b2dpolyrange.cxx
@@ -0,0 +1,371 @@
+/*************************************************************************
+ *
+ * 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
+ *
+ * $RCSfile: b2dmultirange.cxx,v $
+ * $Revision: 1.8 $
+ *
+ * This file is part of OpenOffice.org.
+ *
+ * OpenOffice.org is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License version 3
+ * only, as published by the Free Software Foundation.
+ *
+ * OpenOffice.org is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU Lesser General Public License version 3 for more details
+ * (a copy is included in the LICENSE file that accompanied this code).
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * version 3 along with OpenOffice.org. If not, see
+ * <http://www.openoffice.org/license.html>
+ * for a copy of the LGPLv3 License.
+ *
+ ************************************************************************/
+
+// MARKER(update_precomp.py): autogen include statement, do not remove
+#include "precompiled_basegfx.hxx"
+#include <basegfx/range/b2dpolyrange.hxx>
+
+#include <basegfx/range/b2drange.hxx>
+#include <basegfx/range/b2drangeclipper.hxx>
+#include <basegfx/tuple/b2dtuple.hxx>
+#include <basegfx/polygon/b2dpolypolygon.hxx>
+
+#include <boost/bind.hpp>
+#include <boost/tuple/tuple.hpp>
+#include <algorithm>
+#include <vector>
+
+static basegfx::B2VectorOrientation flipOrientation(
+ basegfx::B2VectorOrientation eOrient)
+{
+ return eOrient == basegfx::ORIENTATION_POSITIVE ?
+ basegfx::ORIENTATION_NEGATIVE : basegfx::ORIENTATION_POSITIVE;
+}
+
+namespace basegfx
+{
+ class ImplB2DPolyRange
+ {
+ void updateBounds()
+ {
+ maBounds.reset();
+ std::for_each(maRanges.begin(),
+ maRanges.end(),
+ boost::bind(
+ (void (B2DRange::*)(const B2DRange&))(
+ &B2DRange::expand),
+ boost::ref(maBounds),
+ _1));
+ }
+
+ public:
+ ImplB2DPolyRange() :
+ maBounds(),
+ maRanges(),
+ maOrient()
+ {}
+
+ explicit ImplB2DPolyRange( const B2DPolyRange::ElementType& rElem ) :
+ maBounds( boost::get<0>(rElem) ),
+ maRanges( 1, boost::get<0>(rElem) ),
+ maOrient( 1, boost::get<1>(rElem) )
+ {}
+
+ explicit ImplB2DPolyRange( const B2DRange& rRange, B2VectorOrientation eOrient ) :
+ maBounds( rRange ),
+ maRanges( 1, rRange ),
+ maOrient( 1, eOrient )
+ {}
+
+ bool operator==(const ImplB2DPolyRange& rRHS) const
+ {
+ return maRanges == rRHS.maRanges && maOrient == rRHS.maOrient;
+ }
+
+ sal_uInt32 count() const
+ {
+ return maRanges.size();
+ }
+
+ B2DPolyRange::ElementType getElement(sal_uInt32 nIndex) const
+ {
+ return boost::make_tuple(maRanges[nIndex],
+ maOrient[nIndex]);
+ }
+
+ void setElement(sal_uInt32 nIndex, const B2DPolyRange::ElementType& rElement )
+ {
+ maRanges[nIndex] = boost::get<0>(rElement);
+ maOrient[nIndex] = boost::get<1>(rElement);
+ updateBounds();
+ }
+
+ void setElement(sal_uInt32 nIndex, const B2DRange& rRange, B2VectorOrientation eOrient )
+ {
+ maRanges[nIndex] = rRange;
+ maOrient[nIndex] = eOrient;
+ updateBounds();
+ }
+
+ void insertElement(sal_uInt32 nIndex, const B2DPolyRange::ElementType& rElement, sal_uInt32 nCount)
+ {
+ maRanges.insert(maRanges.begin()+nIndex, nCount, boost::get<0>(rElement));
+ maOrient.insert(maOrient.begin()+nIndex, nCount, boost::get<1>(rElement));
+ maBounds.expand(boost::get<0>(rElement));
+ }
+
+ void insertElement(sal_uInt32 nIndex, const B2DRange& rRange, B2VectorOrientation eOrient, sal_uInt32 nCount)
+ {
+ maRanges.insert(maRanges.begin()+nIndex, nCount, rRange);
+ maOrient.insert(maOrient.begin()+nIndex, nCount, eOrient);
+ maBounds.expand(rRange);
+ }
+
+ void appendElement(const B2DPolyRange::ElementType& rElement, sal_uInt32 nCount)
+ {
+ maRanges.insert(maRanges.end(), nCount, boost::get<0>(rElement));
+ maOrient.insert(maOrient.end(), nCount, boost::get<1>(rElement));
+ maBounds.expand(boost::get<0>(rElement));
+ }
+
+ void appendElement(const B2DRange& rRange, B2VectorOrientation eOrient, sal_uInt32 nCount)
+ {
+ maRanges.insert(maRanges.end(), nCount, rRange);
+ maOrient.insert(maOrient.end(), nCount, eOrient);
+ maBounds.expand(rRange);
+ }
+
+ void insertPolyRange(sal_uInt32 nIndex, const ImplB2DPolyRange& rPolyRange)
+ {
+ maRanges.insert(maRanges.begin()+nIndex, rPolyRange.maRanges.begin(), rPolyRange.maRanges.end());
+ maOrient.insert(maOrient.begin()+nIndex, rPolyRange.maOrient.begin(), rPolyRange.maOrient.end());
+ updateBounds();
+ }
+
+ void appendPolyRange(const ImplB2DPolyRange& rPolyRange)
+ {
+ maRanges.insert(maRanges.end(),
+ rPolyRange.maRanges.begin(),
+ rPolyRange.maRanges.end());
+ maOrient.insert(maOrient.end(),
+ rPolyRange.maOrient.begin(),
+ rPolyRange.maOrient.end());
+ updateBounds();
+ }
+
+ void remove(sal_uInt32 nIndex, sal_uInt32 nCount)
+ {
+ maRanges.erase(maRanges.begin()+nIndex,maRanges.begin()+nIndex+nCount);
+ maOrient.erase(maOrient.begin()+nIndex,maOrient.begin()+nIndex+nCount);
+ updateBounds();
+ }
+
+ void clear()
+ {
+ std::vector<B2DRange> aTmpRanges;
+ std::vector<B2VectorOrientation> aTmpOrient;
+
+ maRanges.swap(aTmpRanges);
+ maOrient.swap(aTmpOrient);
+
+ maBounds.reset();
+ }
+
+ void flip()
+ {
+ std::for_each(maOrient.begin(),
+ maOrient.end(),
+ boost::bind(
+ &flipOrientation,
+ _1));
+ }
+
+ B2DRange getBounds() const
+ {
+ return maBounds;
+ }
+
+ template< typename ValueType > bool isInside( const ValueType& rValue ) const
+ {
+ if( !maBounds.isInside( rValue ) )
+ return false;
+
+ // cannot use boost::bind here, since isInside is overloaded.
+ // It is currently not possible to resolve the overload
+ // by considering one of the other template arguments.
+ std::vector<B2DRange>::const_iterator aCurr( maRanges.begin() );
+ const std::vector<B2DRange>::const_iterator aEnd ( maRanges.end() );
+ while( aCurr != aEnd )
+ if( aCurr->isInside( rValue ) )
+ return true;
+
+ return false;
+ }
+
+ bool overlaps( const B2DRange& rRange ) const
+ {
+ if( !maBounds.overlaps( rRange ) )
+ return false;
+
+ const std::vector<B2DRange>::const_iterator aEnd( maRanges.end() );
+ return std::find_if( maRanges.begin(),
+ aEnd,
+ boost::bind<bool>( boost::mem_fn( &B2DRange::overlaps ),
+ _1,
+ boost::cref(rRange) ) ) != aEnd;
+ }
+
+ B2DPolyPolygon solveCrossovers() const
+ {
+ return tools::solveCrossovers(maRanges,maOrient);
+ }
+
+ private:
+ B2DRange maBounds;
+ std::vector<B2DRange> maRanges;
+ std::vector<B2VectorOrientation> maOrient;
+ };
+
+ B2DPolyRange::B2DPolyRange() :
+ mpImpl()
+ {}
+
+ B2DPolyRange::~B2DPolyRange()
+ {}
+
+ B2DPolyRange::B2DPolyRange( const ElementType& rElem ) :
+ mpImpl( ImplB2DPolyRange( rElem ) )
+ {}
+
+ B2DPolyRange::B2DPolyRange( const B2DRange& rRange, B2VectorOrientation eOrient ) :
+ mpImpl( ImplB2DPolyRange( rRange, eOrient ) )
+ {}
+
+ B2DPolyRange::B2DPolyRange( const B2DPolyRange& rRange ) :
+ mpImpl( rRange.mpImpl )
+ {}
+
+ B2DPolyRange& B2DPolyRange::operator=( const B2DPolyRange& rRange )
+ {
+ mpImpl = rRange.mpImpl;
+ return *this;
+ }
+
+ void B2DPolyRange::makeUnique()
+ {
+ mpImpl.make_unique();
+ }
+
+ bool B2DPolyRange::operator==(const B2DPolyRange& rRange) const
+ {
+ if(mpImpl.same_object(rRange.mpImpl))
+ return true;
+
+ return ((*mpImpl) == (*rRange.mpImpl));
+ }
+
+ bool B2DPolyRange::operator!=(const B2DPolyRange& rRange) const
+ {
+ return !(*this == rRange);
+ }
+
+ sal_uInt32 B2DPolyRange::count() const
+ {
+ return mpImpl->count();
+ }
+
+ B2DPolyRange::ElementType B2DPolyRange::getElement(sal_uInt32 nIndex) const
+ {
+ return mpImpl->getElement(nIndex);
+ }
+
+ void B2DPolyRange::setElement(sal_uInt32 nIndex, const ElementType& rElement )
+ {
+ mpImpl->setElement(nIndex, rElement);
+ }
+
+ void B2DPolyRange::setElement(sal_uInt32 nIndex, const B2DRange& rRange, B2VectorOrientation eOrient )
+ {
+ mpImpl->setElement(nIndex, rRange, eOrient );
+ }
+
+ void B2DPolyRange::insertElement(sal_uInt32 nIndex, const ElementType& rElement, sal_uInt32 nCount)
+ {
+ mpImpl->insertElement(nIndex, rElement, nCount );
+ }
+
+ void B2DPolyRange::insertElement(sal_uInt32 nIndex, const B2DRange& rRange, B2VectorOrientation eOrient, sal_uInt32 nCount)
+ {
+ mpImpl->insertElement(nIndex, rRange, eOrient, nCount );
+ }
+
+ void B2DPolyRange::appendElement(const ElementType& rElement, sal_uInt32 nCount)
+ {
+ mpImpl->appendElement(rElement, nCount);
+ }
+
+ void B2DPolyRange::appendElement(const B2DRange& rRange, B2VectorOrientation eOrient, sal_uInt32 nCount)
+ {
+ mpImpl->appendElement(rRange, eOrient, nCount );
+ }
+
+ void B2DPolyRange::insertPolyRange(sal_uInt32 nIndex, const B2DPolyRange& rRange)
+ {
+ mpImpl->insertPolyRange(nIndex, *rRange.mpImpl);
+ }
+
+ void B2DPolyRange::appendPolyRange(const B2DPolyRange& rRange)
+ {
+ mpImpl->appendPolyRange(*rRange.mpImpl);
+ }
+
+ void B2DPolyRange::remove(sal_uInt32 nIndex, sal_uInt32 nCount)
+ {
+ mpImpl->remove(nIndex, nCount);
+ }
+
+ void B2DPolyRange::clear()
+ {
+ mpImpl->clear();
+ }
+
+ void B2DPolyRange::flip()
+ {
+ mpImpl->flip();
+ }
+
+ B2DRange B2DPolyRange::getBounds() const
+ {
+ return mpImpl->getBounds();
+ }
+
+ bool B2DPolyRange::isInside( const B2DTuple& rTuple ) const
+ {
+ return mpImpl->isInside(rTuple);
+ }
+
+ bool B2DPolyRange::isInside( const B2DRange& rRange ) const
+ {
+ return mpImpl->isInside(rRange);
+ }
+
+ bool B2DPolyRange::overlaps( const B2DRange& rRange ) const
+ {
+ return mpImpl->overlaps(rRange);
+ }
+
+ B2DPolyPolygon B2DPolyRange::solveCrossovers() const
+ {
+ return mpImpl->solveCrossovers();
+ }
+
+} // end of namespace basegfx
+
+// eof
diff --git a/basegfx/source/range/b2drangeclipper.cxx b/basegfx/source/range/b2drangeclipper.cxx
new file mode 100644
index 000000000000..524479b4fde0
--- /dev/null
+++ b/basegfx/source/range/b2drangeclipper.cxx
@@ -0,0 +1,950 @@
+/*************************************************************************
+ *
+ * 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
+ *
+ * $RCSfile: b2dmultirange.cxx,v $
+ * $Revision: 1.8 $
+ *
+ * This file is part of OpenOffice.org.
+ *
+ * OpenOffice.org is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License version 3
+ * only, as published by the Free Software Foundation.
+ *
+ * OpenOffice.org is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU Lesser General Public License version 3 for more details
+ * (a copy is included in the LICENSE file that accompanied this code).
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * version 3 along with OpenOffice.org. If not, see
+ * <http://www.openoffice.org/license.html>
+ * for a copy of the LGPLv3 License.
+ *
+ ************************************************************************/
+
+// MARKER(update_precomp.py): autogen include statement, do not remove
+#include "precompiled_basegfx.hxx"
+
+#include <rtl/math.hxx>
+
+#include <basegfx/tuple/b2dtuple.hxx>
+#include <basegfx/range/b2drange.hxx>
+#include <basegfx/range/b2dpolyrange.hxx>
+#include <basegfx/polygon/b2dpolypolygon.hxx>
+#include <basegfx/polygon/b2dpolygontools.hxx>
+#include <basegfx/polygon/b2dpolypolygontools.hxx>
+
+#include <o3tl/vector_pool.hxx>
+#include <boost/bind.hpp>
+#include <boost/utility.hpp>
+
+#include <algorithm>
+#include <deque>
+#include <list>
+
+
+namespace basegfx
+{
+ namespace
+ {
+ // Generating a poly-polygon from a bunch of rectangles
+ //
+ // Helper functionality for sweep-line algorithm
+ // ====================================================
+
+ typedef std::vector<B2DRange> VectorOfRanges;
+
+ class ImplPolygon;
+ typedef o3tl::vector_pool<ImplPolygon> VectorOfPolygons;
+
+
+ /** This class represents an active edge
+
+ As the sweep line traverses across the overall area,
+ rectangle edges parallel to it generate events, and
+ rectangle edges orthogonal to it generate active
+ edges. This class represents the latter.
+ */
+ class ActiveEdge
+ {
+ public:
+ /** The two possible active rectangle edges differ by one
+ coordinate value - the upper edge has the lower, the
+ lower edge the higher value.
+ */
+ enum EdgeType {
+ /// edge with lower coordinate value
+ UPPER=0,
+ /// edge with higher coordinate value
+ LOWER=1
+ };
+
+ enum EdgeDirection {
+ /// edge proceeds to the left
+ PROCEED_LEFT=0,
+ /// edge proceeds to the right
+ PROCEED_RIGHT=1
+ };
+
+ /** Create active edge
+
+ @param rRect
+ Rectangle this edge is part of
+
+ @param fInvariantCoord
+ The invariant ccordinate value of this edge
+
+ @param eEdgeType
+ Is fInvariantCoord the lower or the higher value, for
+ this rect?
+ */
+ ActiveEdge( const B2DRectangle& rRect,
+ const double& fInvariantCoord,
+ std::ptrdiff_t nPolyIdx,
+ EdgeType eEdgeType,
+ EdgeDirection eEdgeDirection ) :
+ mfInvariantCoord(fInvariantCoord),
+ mpAssociatedRect( &rRect ),
+ mnPolygonIdx( nPolyIdx ),
+ meEdgeType( eEdgeType ),
+ meEdgeDirection( eEdgeDirection )
+ {}
+
+ 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; }
+
+ /// For STL sort
+ bool operator<( const ActiveEdge& rRHS ) const { return mfInvariantCoord < rRHS.mfInvariantCoord; }
+
+ private:
+ /** The invariant coordinate value of this edge (e.g. the
+ common y value, for a horizontal edge)
+ */
+ double mfInvariantCoord;
+
+ /** Associated rectangle
+
+ This on the one hand saves some storage space (the
+ vector of rectangles is persistent, anyway), and on
+ the other hand provides an identifier to match active
+ edges and x events (see below)
+
+ Ptr because class needs to be assignable
+ */
+ const B2DRectangle* mpAssociatedRect;
+
+ /** Index of the polygon this edge is currently involved
+ with.
+
+ Note that this can change for some kinds of edge
+ intersection, as the algorithm tends to swap
+ associated polygons there.
+
+ -1 denotes no assigned polygon
+ */
+ std::ptrdiff_t mnPolygonIdx;
+
+ /// 'upper' or 'lower' edge of original rectangle.
+ EdgeType meEdgeType;
+
+ /// 'left' or 'right'
+ EdgeDirection meEdgeDirection;
+ };
+
+ // Needs to be list - various places hold ptrs to elements
+ typedef std::list< ActiveEdge > ListOfEdges;
+
+
+ /** 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
+ edges. This class represents the former.
+
+ The class defines an element of the sweep line list. The
+ sweep line's position jumps in steps defined by the
+ coordinates of the sorted SweepLineEvent entries.
+ */
+ class SweepLineEvent
+ {
+ public:
+ /** The two possible sweep line rectangle edges differ by
+ one coordinate value - the starting edge has the
+ lower, the finishing edge the higher value.
+ */
+ enum EdgeType {
+ /// edge with lower coordinate value
+ STARTING_EDGE=0,
+ /// edge with higher coordinate value
+ FINISHING_EDGE=1
+ };
+
+ /** The two possible sweep line directions
+ */
+ enum EdgeDirection {
+ PROCEED_UP=0,
+ PROCEED_DOWN=1
+ };
+
+ /** Create sweep line event
+
+ @param fPos
+ Coordinate position of the event
+
+ @param rRect
+ Rectangle this event is generated for.
+
+ @param eEdgeType
+ Is fPos the lower or the higher value, for the
+ rectangle this event is generated for?
+ */
+ SweepLineEvent( double fPos,
+ const B2DRectangle& rRect,
+ EdgeType eEdgeType,
+ EdgeDirection eDirection) :
+ mfPos( fPos ),
+ mpAssociatedRect( &rRect ),
+ meEdgeType( eEdgeType ),
+ meEdgeDirection( eDirection )
+ {}
+
+ double getPos() const { return mfPos; }
+ const B2DRectangle& getRect() const { return *mpAssociatedRect; }
+ 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;
+
+ /** Rectangle this event is generated for
+
+ This on the one hand saves some storage space (the
+ vector of rectangles is persistent, anyway), and on
+ the other hand provides an identifier to match active
+ edges and events (see below)
+
+ Ptr because class needs to be assignable
+ */
+ const B2DRectangle* mpAssociatedRect;
+
+ /// 'upper' or 'lower' edge of original rectangle.
+ EdgeType meEdgeType;
+
+ /// 'up' or 'down'
+ EdgeDirection meEdgeDirection;
+ };
+
+ typedef std::vector< SweepLineEvent > VectorOfEvents;
+
+
+ /** 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
+ implemented here.
+ */
+ class ImplPolygon
+ {
+ public:
+ /** Create polygon
+ */
+ ImplPolygon() :
+ mpLeadingRightEdge(NULL),
+ mnIdx(-1),
+ maPoints(),
+ mbIsFinished(false)
+ {
+ // completely ad-hoc. but what the hell.
+ maPoints.reserve(11);
+ }
+
+ void setPolygonPoolIndex( std::ptrdiff_t nIdx ) { mnIdx = nIdx; }
+ bool isFinished() const { return mbIsFinished; }
+
+ /// Add point to the end of the existing points
+ void append( const B2DPoint& rPoint )
+ {
+ OSL_PRECOND( maPoints.empty() ||
+ maPoints.back().getX() == rPoint.getX() ||
+ maPoints.back().getY() == rPoint.getY(),
+ "ImplPolygon::append(): added point violates 90 degree line angle constraint!" );
+
+ if( maPoints.empty() ||
+ maPoints.back() != rPoint )
+ {
+ // avoid duplicate points
+ maPoints.push_back( rPoint );
+ }
+ }
+
+ /** Perform the intersection of this polygon with an
+ active edge.
+
+ @param rEvent
+ The vertical line event that generated the
+ intersection
+
+ @param rActiveEdge
+ The active edge that generated the intersection
+
+ @param rPolygonPool
+ Polygon pool, we sometimes need to allocate a new one
+
+ @param bIsFinishingEdge
+ True, when this is hitting the last edge of the
+ vertical sweep - every vertical sweep starts and ends
+ with upper and lower edge of the _same_ rectangle.
+
+ @return the new current polygon (that's the one
+ processing must proceed with, when going through the
+ list of upcoming active edges).
+ */
+ std::ptrdiff_t intersect( SweepLineEvent& rEvent,
+ ActiveEdge& rActiveEdge,
+ VectorOfPolygons& rPolygonPool,
+ B2DPolyPolygon& rRes,
+ bool isFinishingEdge )
+ {
+ OSL_PRECOND( !isFinished(),
+ "ImplPolygon::intersect(): called on already finished polygon!" );
+ OSL_PRECOND( !isFinishingEdge
+ || (isFinishingEdge && &rEvent.getRect() == &rActiveEdge.getRect()),
+ "ImplPolygon::intersect(): inconsistent ending!" );
+
+ const B2DPoint aIntersectionPoint( rEvent.getPos(),
+ rActiveEdge.getInvariantCoord() );
+
+ // intersection point, goes to our polygon
+ // unconditionally
+ append(aIntersectionPoint);
+
+ const bool isSweepLineEnteringRect(
+ rEvent.getEdgeType() == SweepLineEvent::STARTING_EDGE);
+ if( isFinishingEdge )
+ {
+ if( isSweepLineEnteringRect )
+ handleFinalOwnRightEdge(rActiveEdge);
+ else
+ handleFinalOwnLeftEdge(rActiveEdge,
+ rPolygonPool,
+ rRes);
+
+ // we're done with this rect & sweep line
+ return -1;
+ }
+ else if( metOwnEdge(rEvent,rActiveEdge) )
+ {
+ handleInitialOwnEdge(rEvent, rActiveEdge);
+
+ // point already added, all init done, continue
+ // with same poly
+ return mnIdx;
+ }
+ else
+ {
+ OSL_ENSURE( rActiveEdge.getTargetPolygonIndex() != -1,
+ "ImplPolygon::intersect(): non-trivial intersection hit empty polygon!" );
+
+ const bool isHittingLeftEdge(
+ rActiveEdge.getEdgeDirection() == ActiveEdge::PROCEED_LEFT);
+
+ if( isHittingLeftEdge )
+ return handleComplexLeftEdge(rActiveEdge,
+ aIntersectionPoint,
+ rPolygonPool,
+ rRes);
+ else
+ return handleComplexRightEdge(rActiveEdge,
+ aIntersectionPoint,
+ rPolygonPool);
+ }
+ }
+
+ private:
+ std::ptrdiff_t getPolygonPoolIndex() const { return mnIdx; }
+
+ void handleInitialOwnEdge(SweepLineEvent& rEvent,
+ ActiveEdge& rActiveEdge)
+ {
+ const bool isActiveEdgeProceedLeft(
+ rActiveEdge.getEdgeDirection() == ActiveEdge::PROCEED_LEFT);
+ const bool isSweepLineEnteringRect(
+ rEvent.getEdgeType() == SweepLineEvent::STARTING_EDGE);
+ (void)isActiveEdgeProceedLeft;
+ (void)isSweepLineEnteringRect;
+
+ OSL_ENSURE( isSweepLineEnteringRect == isActiveEdgeProceedLeft,
+ "ImplPolygon::intersect(): sweep initial own edge hit: wrong polygon order" );
+
+ OSL_ENSURE( isSweepLineEnteringRect ||
+ mpLeadingRightEdge == &rActiveEdge,
+ "ImplPolygon::intersect(): sweep initial own edge hit: wrong leading edge" );
+ }
+
+ void handleFinalOwnRightEdge(ActiveEdge& rActiveEdge)
+ {
+ OSL_ENSURE( rActiveEdge.getEdgeDirection() == ActiveEdge::PROCEED_RIGHT,
+ "ImplPolygon::handleInitialOwnRightEdge(): start edge wrong polygon order" );
+
+ rActiveEdge.setTargetPolygonIndex(mnIdx);
+ mpLeadingRightEdge = &rActiveEdge;
+ }
+
+ void handleFinalOwnLeftEdge(ActiveEdge& rActiveEdge,
+ VectorOfPolygons& rPolygonPool,
+ B2DPolyPolygon& rRes)
+ {
+ OSL_ENSURE( rActiveEdge.getEdgeDirection() == ActiveEdge::PROCEED_LEFT,
+ "ImplPolygon::handleFinalOwnLeftEdge(): end edge wrong polygon order" );
+
+ const bool isHittingOurTail(
+ rActiveEdge.getTargetPolygonIndex() == mnIdx);
+
+ if( isHittingOurTail )
+ finish(rRes); // just finish. no fuss.
+ else
+ {
+ // temp poly hits final left edge
+ const std::ptrdiff_t nTmpIdx=rActiveEdge.getTargetPolygonIndex();
+ ImplPolygon& rTmp=rPolygonPool.get(nTmpIdx);
+
+ // active edge's polygon has points
+ // already. ours need to go in front of them.
+ maPoints.insert(maPoints.end(),
+ rTmp.maPoints.begin(),
+ rTmp.maPoints.end());
+
+ // adjust leading edges, we're switching the polygon
+ ActiveEdge* const pFarEdge=rTmp.mpLeadingRightEdge;
+
+ mpLeadingRightEdge = pFarEdge;
+ pFarEdge->setTargetPolygonIndex(mnIdx);
+
+ // nTmpIdx is an empty shell, get rid of it
+ rPolygonPool.free(nTmpIdx);
+ }
+ }
+
+ std::ptrdiff_t handleComplexLeftEdge(ActiveEdge& rActiveEdge,
+ const B2DPoint& rIntersectionPoint,
+ VectorOfPolygons& rPolygonPool,
+ B2DPolyPolygon& rRes)
+ {
+ const bool isHittingOurTail(
+ rActiveEdge.getTargetPolygonIndex() == mnIdx);
+ if( isHittingOurTail )
+ {
+ finish(rRes);
+
+ // so "this" is done - need new polygon to collect
+ // further points
+ const std::ptrdiff_t nIdxNewPolygon=rPolygonPool.alloc();
+ rPolygonPool.get(nIdxNewPolygon).setPolygonPoolIndex(nIdxNewPolygon);
+ rPolygonPool.get(nIdxNewPolygon).append(rIntersectionPoint);
+
+ rActiveEdge.setTargetPolygonIndex(nIdxNewPolygon);
+
+ return nIdxNewPolygon;
+ }
+ else
+ {
+ const std::ptrdiff_t nTmpIdx=rActiveEdge.getTargetPolygonIndex();
+ ImplPolygon& rTmp=rPolygonPool.get(nTmpIdx);
+
+ // active edge's polygon has points
+ // already. ours need to go in front of them.
+ maPoints.insert(maPoints.end(),
+ rTmp.maPoints.begin(),
+ rTmp.maPoints.end());
+
+ rTmp.maPoints.clear();
+ rTmp.append(rIntersectionPoint);
+
+ // adjust leading edges, we're switching the polygon
+ ActiveEdge* const pFarEdge=rTmp.mpLeadingRightEdge;
+ ActiveEdge* const pNearEdge=&rActiveEdge;
+
+ rTmp.mpLeadingRightEdge = NULL;
+ pNearEdge->setTargetPolygonIndex(nTmpIdx);
+
+ mpLeadingRightEdge = pFarEdge;
+ pFarEdge->setTargetPolygonIndex(mnIdx);
+
+ return nTmpIdx;
+ }
+ }
+
+ std::ptrdiff_t handleComplexRightEdge(ActiveEdge& rActiveEdge,
+ const B2DPoint& rIntersectionPoint,
+ VectorOfPolygons& rPolygonPool)
+ {
+ const std::ptrdiff_t nTmpIdx=rActiveEdge.getTargetPolygonIndex();
+ ImplPolygon& rTmp=rPolygonPool.get(nTmpIdx);
+
+ rTmp.append(rIntersectionPoint);
+
+ rActiveEdge.setTargetPolygonIndex(mnIdx);
+ mpLeadingRightEdge = &rActiveEdge;
+
+ rTmp.mpLeadingRightEdge = NULL;
+
+ return nTmpIdx;
+ }
+
+ /// True when sweep line hits our own active edge
+ bool metOwnEdge(const SweepLineEvent& rEvent,
+ ActiveEdge& rActiveEdge)
+ {
+ const bool bHitOwnEdge=&rEvent.getRect() == &rActiveEdge.getRect();
+ return bHitOwnEdge;
+ }
+
+ /// Retrieve B2DPolygon from this object
+ B2DPolygon getPolygon() const
+ {
+ B2DPolygon aRes;
+ std::for_each( maPoints.begin(),
+ maPoints.end(),
+ boost::bind(
+ &B2DPolygon::append,
+ boost::ref(aRes),
+ _1,
+ 1 ) );
+ aRes.setClosed( true );
+ return aRes;
+ }
+
+ /** Finish this polygon, push to result set.
+ */
+ 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;
+
+ rRes.append(getPolygon());
+ }
+
+ /** Refers to the current leading edge element of this
+ polygon, or NULL. The leading edge denotes the 'front'
+ of the polygon vertex sequence, i.e. the coordinates
+ at the polygon's leading edge are returned from
+ maPoints.front()
+ */
+ ActiveEdge* mpLeadingRightEdge;
+
+ /// current index into vector pool
+ std::ptrdiff_t mnIdx;
+
+ /// Container for the actual polygon points
+ std::vector<B2DPoint> maPoints;
+
+ /// When true, this polygon is 'done', i.e. nothing must be added anymore.
+ bool mbIsFinished;
+ };
+
+ /** Init sweep line event list
+
+ This method fills the event list with the sweep line
+ events generated from the input rectangles, and sorts them
+ with increasing x.
+ */
+ void setupSweepLineEventListFromRanges( VectorOfEvents& o_rEventVector,
+ const std::vector<B2DRange>& rRanges,
+ const std::vector<B2VectorOrientation>& rOrientations )
+ {
+ // we need exactly 2*rectVec.size() events: one for the
+ // left, and one for the right edge of each rectangle
+ o_rEventVector.clear();
+ o_rEventVector.reserve( 2*rRanges.size() );
+
+ // generate events
+ // ===============
+
+ // first pass: add all left edges in increasing order
+ std::vector<B2DRange>::const_iterator aCurrRect=rRanges.begin();
+ std::vector<B2VectorOrientation>::const_iterator aCurrOrientation=rOrientations.begin();
+ const std::vector<B2DRange>::const_iterator aEnd=rRanges.end();
+ const std::vector<B2VectorOrientation>::const_iterator aEndOrientation=rOrientations.end();
+ while( aCurrRect != aEnd && aCurrOrientation != aEndOrientation )
+ {
+ const B2DRectangle& rCurrRect( *aCurrRect++ );
+
+ o_rEventVector.push_back(
+ SweepLineEvent( rCurrRect.getMinX(),
+ rCurrRect,
+ SweepLineEvent::STARTING_EDGE,
+ (*aCurrOrientation++) == ORIENTATION_POSITIVE ?
+ SweepLineEvent::PROCEED_UP : SweepLineEvent::PROCEED_DOWN) );
+ }
+
+ // second pass: add all right edges in reversed order
+ std::vector<B2DRange>::const_reverse_iterator aCurrRectR=rRanges.rbegin();
+ std::vector<B2VectorOrientation>::const_reverse_iterator aCurrOrientationR=rOrientations.rbegin();
+ const std::vector<B2DRange>::const_reverse_iterator aEndR=rRanges.rend();
+ const std::vector<B2VectorOrientation>::const_reverse_iterator aEndOrientationR=rOrientations.rend();
+ while( aCurrRectR != aEndR )
+ {
+ const B2DRectangle& rCurrRect( *aCurrRectR++ );
+
+ o_rEventVector.push_back(
+ SweepLineEvent( rCurrRect.getMaxX(),
+ rCurrRect,
+ SweepLineEvent::FINISHING_EDGE,
+ (*aCurrOrientationR++) == ORIENTATION_POSITIVE ?
+ SweepLineEvent::PROCEED_DOWN : SweepLineEvent::PROCEED_UP ) );
+ }
+
+ // sort events
+ // ===========
+
+ // since we use stable_sort, the order of events with the
+ // same x value will not change. The elaborate two-pass
+ // add above thus ensures, that for each two rectangles
+ // with similar left and right x coordinates, the
+ // rectangle whose left event comes first will have its
+ // right event come last. This is advantageous for the
+ // clip algorithm below, see handleRightEdgeCrossing().
+
+ // TODO(P3): Use radix sort (from
+ // b2dpolypolygonrasterconverter, or have your own
+ // templatized version).
+ std::stable_sort( o_rEventVector.begin(),
+ o_rEventVector.end() );
+ }
+
+ /** Insert two active edge segments for the given rectangle.
+
+ This method creates two active edge segments from the
+ given rect, and inserts them into the active edge list,
+ such that this stays sorted (if it was before).
+
+ @param io_rEdgeList
+ Active edge list to insert into
+
+ @param io_rPolygons
+ Vector of polygons. Each rectangle added creates one
+ tentative result polygon in this vector, and the edge list
+ entries holds a reference to that polygon (this _requires_
+ that the polygon vector does not reallocate, i.e. it must
+ have at least the maximal number of rectangles reserved)
+
+ @param o_CurrentPolygon
+ The then-current polygon when processing this sweep line
+ event
+
+ @param rCurrEvent
+ The actual event that caused this call
+ */
+ void createActiveEdgesFromStartEvent( ListOfEdges& io_rEdgeList,
+ VectorOfPolygons& io_rPolygonPool,
+ SweepLineEvent& rCurrEvent )
+ {
+ ListOfEdges aNewEdges;
+ const B2DRectangle& rRect=rCurrEvent.getRect();
+ const bool bGoesDown=rCurrEvent.getEdgeDirection() == SweepLineEvent::PROCEED_DOWN;
+
+ // start event - new rect starts here, needs polygon to
+ // collect points into
+ const std::ptrdiff_t nIdxPolygon=io_rPolygonPool.alloc();
+ io_rPolygonPool.get(nIdxPolygon).setPolygonPoolIndex(nIdxPolygon);
+
+ // upper edge
+ 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(
+ rRect,
+ rRect.getMaxY(),
+ bGoesDown ? -1 : nIdxPolygon,
+ ActiveEdge::LOWER,
+ bGoesDown ? ActiveEdge::PROCEED_RIGHT : ActiveEdge::PROCEED_LEFT ) );
+
+ // furthermore, have to respect a special tie-breaking
+ // rule here, for edges which share the same y value:
+ // newly added upper edges must be inserted _before_ any
+ // other edge with the same y value, and newly added lower
+ // edges must be _after_ all other edges with the same
+ // y. This ensures that the left vertical edge processing
+ // below encounters the upper edge of the current rect
+ // first, and the lower edge last, which automatically
+ // 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 ListOfEdges::iterator aEnd ( io_rEdgeList.end() );
+ while( aCurr != aEnd )
+ {
+ const double nCurrY( aCurr->getInvariantCoord() );
+
+ 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,
+ aNewEdges,
+ aNewEdges.begin() );
+ }
+
+ if( nCurrY > nMaxY )
+ {
+ // insert lower edge _before_ aCurr. Thus, it will
+ // be the last entry for a range of equal y values
+ // (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,
+ aNewEdges,
+ aNewEdges.begin() );
+ // done with insertion, can early-exit here.
+ return;
+ }
+
+ ++aCurr;
+ }
+
+ // append remainder of aNewList (might still contain 2 or
+ // 1 elements, depending of the contents of io_rEdgeList).
+ io_rEdgeList.splice( aCurr,
+ aNewEdges );
+ }
+
+ inline bool isSameRect(ActiveEdge& rEdge,
+ const basegfx::B2DRange& rRect)
+ {
+ return &rEdge.getRect() == &rRect;
+ }
+
+ // wow what a hack. necessary because stl's list::erase does
+ // not eat reverse_iterator
+ template<typename Cont, typename Iter> Iter eraseFromList(Cont&, Iter);
+ template<> inline ListOfEdges::iterator eraseFromList(
+ ListOfEdges& rList, ListOfEdges::iterator aIter)
+ {
+ return rList.erase(aIter);
+ }
+ template<> inline ListOfEdges::reverse_iterator eraseFromList(
+ ListOfEdges& rList, ListOfEdges::reverse_iterator aIter)
+ {
+ return ListOfEdges::reverse_iterator(
+ rList.erase(boost::prior(aIter.base())));
+ }
+
+ template<int bPerformErase,
+ typename Iterator> inline void processActiveEdges(
+ Iterator first,
+ Iterator last,
+ ListOfEdges& rActiveEdgeList,
+ SweepLineEvent& rCurrEvent,
+ VectorOfPolygons& rPolygonPool,
+ B2DPolyPolygon& rRes )
+ {
+ const basegfx::B2DRange& rCurrRect=rCurrEvent.getRect();
+
+ // fast-forward to rCurrEvent's first active edge (holds
+ // for both starting and finishing sweep line events, a
+ // rect is regarded _outside_ any rects whose events have
+ // started earlier
+ first = std::find_if(first, last,
+ boost::bind(
+ &isSameRect,
+ _1,
+ boost::cref(rCurrRect)));
+
+ if(first == last)
+ return;
+
+ int nCount=0;
+ std::ptrdiff_t nCurrPolyIdx=-1;
+ while(first != last)
+ {
+ if( nCurrPolyIdx == -1 )
+ nCurrPolyIdx=first->getTargetPolygonIndex();
+
+ OSL_ASSERT(nCurrPolyIdx != -1);
+
+ // second encounter of my rect -> second edge
+ // encountered, done
+ const bool bExit=
+ nCount &&
+ isSameRect(*first,
+ rCurrRect);
+
+ // deal with current active edge
+ nCurrPolyIdx =
+ rPolygonPool.get(nCurrPolyIdx).intersect(
+ rCurrEvent,
+ *first,
+ rPolygonPool,
+ rRes,
+ bExit);
+
+ // prune upper & lower active edges, if requested
+ if( bPerformErase && (bExit || !nCount) )
+ first = eraseFromList(rActiveEdgeList,first);
+ else
+ ++first;
+
+ // delayed exit, had to prune first
+ if( bExit )
+ return;
+
+ ++nCount;
+ }
+ }
+
+ template<int bPerformErase> inline void processActiveEdgesTopDown(
+ SweepLineEvent& rCurrEvent,
+ ListOfEdges& rActiveEdgeList,
+ VectorOfPolygons& rPolygonPool,
+ B2DPolyPolygon& rRes )
+ {
+ processActiveEdges<bPerformErase>(
+ rActiveEdgeList. begin(),
+ rActiveEdgeList. end(),
+ rActiveEdgeList,
+ rCurrEvent,
+ rPolygonPool,
+ rRes);
+ }
+
+ template<int bPerformErase> inline void processActiveEdgesBottomUp(
+ SweepLineEvent& rCurrEvent,
+ ListOfEdges& rActiveEdgeList,
+ VectorOfPolygons& rPolygonPool,
+ B2DPolyPolygon& rRes )
+ {
+ processActiveEdges<bPerformErase>(
+ rActiveEdgeList. rbegin(),
+ rActiveEdgeList. rend(),
+ rActiveEdgeList,
+ rCurrEvent,
+ rPolygonPool,
+ rRes);
+ }
+
+ enum{ NoErase=0, PerformErase=1 };
+
+ void handleStartingEdge( SweepLineEvent& rCurrEvent,
+ ListOfEdges& rActiveEdgeList,
+ VectorOfPolygons& rPolygonPool,
+ B2DPolyPolygon& rRes)
+ {
+ // inject two new active edges for rect
+ createActiveEdgesFromStartEvent( rActiveEdgeList,
+ rPolygonPool,
+ rCurrEvent );
+
+ if( SweepLineEvent::PROCEED_DOWN == rCurrEvent.getEdgeDirection() )
+ processActiveEdgesTopDown<NoErase>(
+ rCurrEvent, rActiveEdgeList, rPolygonPool, rRes);
+ else
+ processActiveEdgesBottomUp<NoErase>(
+ rCurrEvent, rActiveEdgeList, rPolygonPool, rRes);
+ }
+
+ void handleFinishingEdge( SweepLineEvent& rCurrEvent,
+ ListOfEdges& rActiveEdgeList,
+ VectorOfPolygons& rPolygonPool,
+ B2DPolyPolygon& rRes)
+ {
+ if( SweepLineEvent::PROCEED_DOWN == rCurrEvent.getEdgeDirection() )
+ processActiveEdgesTopDown<PerformErase>(
+ rCurrEvent, rActiveEdgeList, rPolygonPool, rRes);
+ else
+ processActiveEdgesBottomUp<PerformErase>(
+ rCurrEvent, rActiveEdgeList, rPolygonPool, rRes);
+ }
+
+ inline void handleSweepLineEvent( SweepLineEvent& rCurrEvent,
+ ListOfEdges& rActiveEdgeList,
+ VectorOfPolygons& rPolygonPool,
+ B2DPolyPolygon& rRes)
+ {
+ if( SweepLineEvent::STARTING_EDGE == rCurrEvent.getEdgeType() )
+ handleStartingEdge(rCurrEvent,rActiveEdgeList,rPolygonPool,rRes);
+ else
+ handleFinishingEdge(rCurrEvent,rActiveEdgeList,rPolygonPool,rRes);
+ }
+ }
+
+ namespace tools
+ {
+ B2DPolyPolygon solveCrossovers(const std::vector<B2DRange>& rRanges,
+ const std::vector<B2VectorOrientation>& rOrientations)
+ {
+ // sweep-line algorithm to generate a poly-polygon
+ // from a bunch of rectangles
+ // ===============================================
+ //
+ // This algorithm uses the well-known sweep line
+ // concept, explained in every good text book about
+ // 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
+ // referencing the original rect). These structs are
+ // sorted with increasing x coordinates.
+ //
+ // Then, we start processing the resulting list from
+ // the beginning. Every entry in the list defines a
+ // point in time of the line sweeping from left to
+ // right across all rectangles.
+ VectorOfEvents aSweepLineEvents;
+ setupSweepLineEventListFromRanges( aSweepLineEvents,
+ rRanges,
+ rOrientations );
+
+ B2DPolyPolygon aRes;
+ VectorOfPolygons aPolygonPool;
+ ListOfEdges aActiveEdgeList;
+
+ // sometimes not enough, but a usable compromise
+ aPolygonPool.reserve( rRanges.size() );
+
+ std::for_each( aSweepLineEvents.begin(),
+ aSweepLineEvents.end(),
+ boost::bind(
+ &handleSweepLineEvent,
+ _1,
+ boost::ref(aActiveEdgeList),
+ boost::ref(aPolygonPool),
+ boost::ref(aRes)) );
+
+ return aRes;
+ }
+ }
+}
+
diff --git a/basegfx/source/range/makefile.mk b/basegfx/source/range/makefile.mk
index 678bb16a9312..3dcf552fc420 100644
--- a/basegfx/source/range/makefile.mk
+++ b/basegfx/source/range/makefile.mk
@@ -47,7 +47,8 @@ SLOFILES= \
$(SLO)$/b1drange.obj \
$(SLO)$/b2drange.obj \
$(SLO)$/b2xrange.obj \
- $(SLO)$/b2dmultirange.obj \
+ $(SLO)$/b2dpolyrange.obj \
+ $(SLO)$/b2drangeclipper.obj \
$(SLO)$/b3drange.obj
# --- Targets ----------------------------------
generated by cgit (git 2.34.1) at 2025-01-10 20:57:38 +0000