basegfx/source/range/b2dmultirange.cxx

   1 /*************************************************************************
   2  *
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * Copyright 2008 by Sun Microsystems, Inc.
   6  *
   7  * OpenOffice.org - a multi-platform office productivity suite
   8  *
   9  * $RCSfile: b2dmultirange.cxx,v $
  10  * $Revision: 1.8 $
  11  *
  12  * This file is part of OpenOffice.org.
  13  *
  14  * OpenOffice.org is free software: you can redistribute it and/or modify
  15  * it under the terms of the GNU Lesser General Public License version 3
  16  * only, as published by the Free Software Foundation.
  17  *
  18  * OpenOffice.org is distributed in the hope that it will be useful,
  19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  21  * GNU Lesser General Public License version 3 for more details
  22  * (a copy is included in the LICENSE file that accompanied this code).
  23  *
  24  * You should have received a copy of the GNU Lesser General Public License
  25  * version 3 along with OpenOffice.org.  If not, see
  26  * <http://www.openoffice.org/license.html>
  27  * for a copy of the LGPLv3 License.
  28  *
  29  ************************************************************************/
  30
  31 // MARKER(update_precomp.py): autogen include statement, do not remove
  32 #include "precompiled_basegfx.hxx"
  33 #include <basegfx/range/b2drange.hxx>
  34 #include <basegfx/tuple/b2dtuple.hxx>
  35 #include <basegfx/polygon/b2dpolypolygon.hxx>
  36 #include <basegfx/range/b2dmultirange.hxx>
  37 #include <basegfx/polygon/b2dpolygontools.hxx>
  38 #include <basegfx/polygon/b2dpolypolygontools.hxx>
  39 #include <basegfx/polygon/b2dpolypolygoncutter.hxx>
  40 #include <boost/bind.hpp>
  41 #include <boost/mem_fn.hpp>
  42 #include <algorithm>
  43 #include <vector>
  44
  45
  46 namespace basegfx
  47 {
  48     class ImplB2DMultiRange
  49     {
  50     public:
  51         ImplB2DMultiRange() :
  52             maBounds(),
  53             maRanges()
  54         {
  55         }
  56
  57         explicit ImplB2DMultiRange( const B2DRange& rRange ) :
  58             maBounds(),
  59             maRanges( 1, rRange )
  60         {
  61         }
  62
  63         bool isEmpty() const
  64         {
  65             // no ranges at all, or all ranges empty
  66             return maRanges.empty() ||
  67                 ::std::count_if( maRanges.begin(),
  68                                  maRanges.end(),
  69                                  ::boost::mem_fn( &B2DRange::isEmpty ) )
  70                 == static_cast<VectorOfRanges::difference_type>(maRanges.size());
  71         }
  72
  73         void reset()
  74         {
  75             // swap in empty vector
  76             VectorOfRanges aTmp;
  77             maRanges.swap( aTmp );
  78
  79             maBounds.reset();
  80         }
  81
  82         template< typename ValueType > bool isInside( const ValueType& rValue ) const
  83         {
  84             if( !maBounds.isInside( rValue ) )
  85                 return false;
  86
  87             // cannot use ::boost::bind here, since isInside is overloaded.
  88             // It is currently not possible to resolve the overload
  89             // by considering one of the other template arguments.
  90             VectorOfRanges::const_iterator               aCurr( maRanges.begin() );
  91             const VectorOfRanges::const_iterator aEnd ( maRanges.end() );
  92             while( aCurr != aEnd )
  93                 if( aCurr->isInside( rValue ) )
  94                     return true;
  95
  96             return false;
  97         }
  98
  99         bool overlaps( const B2DRange& rRange ) const
 100         {
 101             if( !maBounds.overlaps( rRange ) )
 102                 return false;
 103
 104             const VectorOfRanges::const_iterator aEnd( maRanges.end() );
 105             return ::std::find_if( maRanges.begin(),
 106                                    aEnd,
 107                                    ::boost::bind<bool>( ::boost::mem_fn( &B2DRange::overlaps ),
 108                                                         _1,
 109                                                         rRange ) ) != aEnd;
 110         }
 111
 112         void addRange( const B2DRange& rRange )
 113         {
 114             maRanges.push_back( rRange );
 115             maBounds.expand( rRange );
 116         }
 117
 118         B2DRange getBounds() const
 119         {
 120             return maBounds;
 121         }
 122
 123         B2DPolyPolygon getPolyPolygon() const
 124         {
 125             B2DPolyPolygon aRes;
 126
 127             // Make range vector unique ( have to avoid duplicate
 128             // rectangles. The polygon clipper will return an empty
 129             // result in this case).
 130             VectorOfRanges      aUniqueRanges;
 131             aUniqueRanges.reserve( maRanges.size() );
 132
 133             VectorOfRanges::const_iterator               aCurr( maRanges.begin() );
 134             const VectorOfRanges::const_iterator aEnd ( maRanges.end() );
 135             while( aCurr != aEnd )
 136             {
 137                 // TODO(F3): It's plain wasted resources to apply a
 138                 // general clipping algorithm to the problem at
 139                 // hand. Go for a dedicated, scan-line-based approach.
 140                 VectorOfRanges::const_iterator aCurrScan( aCurr+1 );
 141                 VectorOfRanges::const_iterator aFound( aEnd );
 142                 while( aCurrScan != aEnd )
 143                 {
 144                     if( aCurrScan->equal( *aCurr ) ||
 145                         aCurrScan->isInside( *aCurr ) )
 146                     {
 147                         // current probe is equal to aCurr, or
 148                         // completely contains aCurr. Thus, stop
 149                         // searching, because aCurr is definitely not
 150                         // a member of the unique rect list
 151                         aFound = aCurrScan;
 152                         break;
 153                     }
 154
 155                     ++aCurrScan;
 156                 }
 157
 158                 if( aFound == aEnd )
 159                 {
 160                     // check whether aCurr is fully contained in one
 161                     // of the already added rects. If yes, we can skip
 162                     // it.
 163                     bool bUnique( true );
 164                     VectorOfRanges::const_iterator aCurrUnique( aUniqueRanges.begin() );
 165                     VectorOfRanges::const_iterator aEndUnique ( aUniqueRanges.end() );
 166                     while( aCurrUnique != aEndUnique )
 167                     {
 168                         if( aCurrUnique->isInside( *aCurr ) )
 169                         {
 170                             // fully contained, no need to add
 171                             bUnique = false;
 172                             break;
 173                         }
 174
 175                         ++aCurrUnique;
 176                     }
 177
 178                     if( bUnique )
 179                         aUniqueRanges.push_back( *aCurr );
 180                 }
 181
 182                 ++aCurr;
 183             }
 184
 185             VectorOfRanges::const_iterator               aCurrUnique( aUniqueRanges.begin() );
 186             const VectorOfRanges::const_iterator aEndUnique ( aUniqueRanges.end() );
 187             while( aCurrUnique != aEndUnique )
 188             {
 189                 // simply merge all unique parts (OR)
 190                 aRes.append( tools::createPolygonFromRect( *aCurrUnique++ ) );
 191             }
 192
 193             // remove redundant intersections. Note: since all added
 194             // rectangles are positively oriented, this method cannot
 195             // generate any holes.
 196             aRes = basegfx::tools::solveCrossovers(aRes);
 197             aRes = basegfx::tools::stripNeutralPolygons(aRes);
 198             aRes = basegfx::tools::stripDispensablePolygons(aRes, false);
 199
 200             return aRes;
 201         }
 202
 203     private:
 204         typedef ::std::vector< B2DRange >       VectorOfRanges;
 205
 206         B2DRange                maBounds;
 207         VectorOfRanges  maRanges;
 208     };
 209
 210
 211     // ====================================================================
 212
 213
 214     B2DMultiRange::B2DMultiRange() :
 215         mpImpl()
 216     {
 217     }
 218
 219     B2DMultiRange::B2DMultiRange( const B2DRange& rRange ) :
 220         mpImpl( ImplB2DMultiRange( rRange ) )
 221     {
 222     }
 223
 224     B2DMultiRange::~B2DMultiRange()
 225     {
 226         // otherwise, ImplB2DMultiRange would be an incomplete type
 227     }
 228
 229     B2DMultiRange::B2DMultiRange( const B2DMultiRange& rSrc ) :
 230         mpImpl( rSrc.mpImpl )
 231     {
 232     }
 233
 234     B2DMultiRange& B2DMultiRange::operator=( const B2DMultiRange& rSrc )
 235     {
 236         mpImpl = rSrc.mpImpl;
 237         return *this;
 238     }
 239
 240     bool B2DMultiRange::isEmpty() const
 241     {
 242         return mpImpl->isEmpty();
 243     }
 244
 245     void B2DMultiRange::reset()
 246     {
 247         mpImpl->reset();
 248     }
 249
 250     bool B2DMultiRange::isInside( const B2DTuple& rTuple ) const
 251     {
 252         return mpImpl->isInside( rTuple );
 253     }
 254
 255     bool B2DMultiRange::isInside( const B2DRange& rRange ) const
 256     {
 257         return mpImpl->isInside( rRange );
 258     }
 259
 260     bool B2DMultiRange::overlaps( const B2DRange& rRange ) const
 261     {
 262         return mpImpl->overlaps( rRange );
 263     }
 264
 265     void B2DMultiRange::addRange( const B2DRange& rRange )
 266     {
 267         mpImpl->addRange( rRange );
 268     }
 269
 270     B2DRange B2DMultiRange::getBounds() const
 271     {
 272         return mpImpl->getBounds();
 273     }
 274
 275     B2DPolyPolygon B2DMultiRange::getPolyPolygon() const
 276     {
 277         return mpImpl->getPolyPolygon();
 278     }
 279
 280 } // end of namespace basegfx
 281
 282 // eof