diff options
Diffstat (limited to 'basegfx/source/range/b2dmultirange.cxx')
| -rw-r--r-- | basegfx/source/range/b2dmultirange.cxx | 279 |
1 files changed, 279 insertions, 0 deletions
diff --git a/basegfx/source/range/b2dmultirange.cxx b/basegfx/source/range/b2dmultirange.cxx new file mode 100644 index 000000000000..3a47be3b7dc9 --- /dev/null +++ b/basegfx/source/range/b2dmultirange.cxx @@ -0,0 +1,279 @@ +/************************************************************************* + * + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * Copyright 2000, 2010 Oracle and/or its affiliates. + * + * OpenOffice.org - a multi-platform office productivity suite + * + * 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 |