sw/source/core/bastyp/swregion.cxx

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
   2 /*
   3  * This file is part of the LibreOffice project.
   4  *
   5  * This Source Code Form is subject to the terms of the Mozilla Public
   6  * License, v. 2.0. If a copy of the MPL was not distributed with this
   7  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
   8  *
   9  * This file incorporates work covered by the following license notice:
  10  *
  11  *   Licensed to the Apache Software Foundation (ASF) under one or more
  12  *   contributor license agreements. See the NOTICE file distributed
  13  *   with this work for additional information regarding copyright
  14  *   ownership. The ASF licenses this file to you under the Apache
  15  *   License, Version 2.0 (the "License"); you may not use this file
  16  *   except in compliance with the License. You may obtain a copy of
  17  *   the License at http://www.apache.org/licenses/LICENSE-2.0 .
  18  */
  19
  20 #include <swrect.hxx>
  21 #include <swregion.hxx>
  22 #include <swtypes.hxx>
  23
  24 SwRegionRects::SwRegionRects( const SwRect &rStartRect, sal_uInt16 nInit ) :
  25     m_aOrigin( rStartRect )
  26 {
  27     reserve(nInit);
  28     push_back( m_aOrigin );
  29 }
  30
  31 SwRegionRects::SwRegionRects( sal_uInt16 nInit ) :
  32     m_aOrigin()
  33 {
  34     reserve(nInit);
  35 }
  36
  37 // If <rDel> is true then this Rect will be overwritten by <rRect> at
  38 // position <nPos>. Otherwise <rRect> is attached at the end.
  39 inline void SwRegionRects::InsertRect( const SwRect &rRect,
  40                                        const sal_uInt16 nPos, bool &rDel )
  41 {
  42     if( rDel )
  43     {
  44         (*this)[nPos] = rRect;
  45         rDel = false;
  46     }
  47     else
  48     {
  49         push_back( rRect );
  50     }
  51 }
  52
  53 void SwRegionRects::operator+=( const SwRect &rRect )
  54 {
  55     push_back( rRect );
  56 }
  57
  58 /** Delete all overlaps of the Rects in array with the given <rRect>
  59
  60     To do so, all existing rectangles have to be either split or deleted.
  61
  62     @param rRect rectangle with the area that should be deleted
  63 */
  64 void SwRegionRects::operator-=( const SwRect &rRect )
  65 {
  66     sal_uInt16 nMax = size();
  67     for ( sal_uInt16 i = 0; i < nMax; ++i )
  68     {
  69         if ( rRect.Overlaps( (*this)[i] ) )
  70         {
  71             SwRect aTmp( (*this)[i] );
  72             SwRect aInter( aTmp );
  73             aInter.Intersection_( rRect );
  74
  75             // The first Rect that should be inserted takes position of i.
  76             // This avoids one Delete() call.
  77             bool bDel = true;
  78
  79             // now split; only those rectangles should be left over that are in
  80             // the "old" but not in the "new" area; hence, not in intersection.
  81             tools::Long nTmp = aInter.Top() - aTmp.Top();
  82             if ( 0 < nTmp )
  83             {
  84                 const tools::Long nOldVal = aTmp.Height();
  85                 aTmp.Height(nTmp);
  86                 InsertRect( aTmp, i, bDel );
  87                 aTmp.Height( nOldVal );
  88             }
  89
  90             aTmp.Top( aInter.Top() + aInter.Height() );
  91             if ( aTmp.Height() > 0 )
  92                 InsertRect( aTmp, i, bDel );
  93
  94             aTmp.Top( aInter.Top() );
  95             aTmp.Bottom( aInter.Bottom() );
  96             nTmp = aInter.Left() - aTmp.Left();
  97             if ( 0 < nTmp )
  98             {
  99                 const tools::Long nOldVal = aTmp.Width();
 100                 aTmp.Width( nTmp );
 101                 InsertRect( aTmp, i, bDel );
 102                 aTmp.Width( nOldVal );
 103             }
 104
 105             aTmp.Left( aInter.Left() + aInter.Width() ); //+1?
 106             if ( aTmp.Width() > 0 )
 107                 InsertRect( aTmp, i, bDel );
 108
 109             if( bDel )
 110             {
 111                 erase( begin() + i );
 112                 --i;     // so that we don't forget any
 113                 --nMax;  // so that we don't check too much
 114             }
 115         }
 116     }
 117 }
 118
 119 /** invert current rectangle
 120
 121     Change the shape, such that holes with be areas and areas are holes now.
 122
 123     Note: If no rects were removed, then the shape is identical to the original
 124           shape. As a result, it will be a NULL-SRectangle after inverting.
 125 */
 126 void SwRegionRects::Invert()
 127 {
 128     // not very elegant and fast, but efficient:
 129     // Create a new region and remove all areas that are left over. Afterwards
 130     // copy all values.
 131
 132     // To avoid unnecessary memory requirements, create a "useful" initial size:
 133     // Number of rectangles in this area * 2 + 2 for the special case of a
 134     // single hole (so four Rects in the inverse case).
 135     SwRegionRects aInvRegion( m_aOrigin, size()*2+2 );
 136     for( const_iterator it = begin(); it != end(); ++it )
 137         aInvRegion -= *it;
 138
 139     // overwrite all existing
 140     swap( aInvRegion );
 141 }
 142
 143 static inline SwTwips CalcArea( const SwRect &rRect )
 144 {
 145     return rRect.Width() * rRect.Height();
 146 }
 147
 148 void SwRegionRects::LimitToOrigin()
 149 {
 150     for (size_type i = 0; i < size(); ++i )
 151         (*this)[ i ].Intersection( m_aOrigin );
 152 }
 153
 154 // combine all adjacent rectangles
 155 void SwRegionRects::Compress( CompressType type )
 156 {
 157     bool bAgain;
 158     do
 159     {
 160         sort( begin(), end(), []( const SwRect& l, const SwRect& r ) { return l.Top() < r.Top(); } );
 161         bAgain = false;
 162         bool bRemoved = false;
 163         for (size_type i = 0; i < size(); ++i )
 164         {
 165             if( (*this)[i].IsEmpty())
 166                 continue;
 167             // Rectangles are sorted by Y axis, so check only pairs of rectangles
 168             // that are possibly overlapping or adjacent or close enough to be grouped by the fuzzy
 169             // code below.
 170             const tools::Long nFuzzy = type == CompressFuzzy ? 1361513 : 0;
 171             const tools::Long yMax = (*this)[i].Top() + (*this)[i].Height() + nFuzzy
 172                 / std::max<tools::Long>( 1, (*this)[i].Width());
 173             for(size_type j = i+1; j < size(); ++j)
 174             {
 175                 if( (*this)[j].IsEmpty())
 176                     continue;
 177                 if( (*this)[j].Top() > yMax )
 178                     break;
 179                 // If one rectangle contains a second completely than the latter
 180                 // does not need to be stored and can be deleted
 181                 else if ( (*this)[i].Contains( (*this)[j] ) )
 182                 {
 183                     (*this)[j].Width(0); // = erase(), see below
 184                     bRemoved = true;
 185                 }
 186                 else if ( (*this)[j].Contains( (*this)[i] ) )
 187                 {
 188                     (*this)[i] = (*this)[j];
 189                     (*this)[j].Width(0);
 190                     bRemoved = true;
 191                     bAgain = true;
 192                 }
 193                 else
 194                 {
 195                     // Merge adjacent rectangles (possibly overlapping), such rectangles can be
 196                     // detected by their merged areas being equal to the area of the union
 197                     // (which is obviously the case if they share one side, and using
 198                     // the nFuzzy extra allows merging also rectangles that do not quite cover
 199                     // the entire union but it's close enough).
 200
 201                     // For combining as much as possible (and for having less single
 202                     // paints), the area of the union can be a little bit larger:
 203                     // ( 9622 * 141.5 = 1361513 ~= a quarter (1/4) centimeter wider
 204                     // than the width of an A4 page
 205                     SwRect aUnion = (*this)[i].GetUnion( (*this)[j] );
 206                     SwRect aInter = (*this)[i].GetIntersection( (*this)[j] );
 207                     if ( CalcArea( (*this)[i] ) + CalcArea( (*this)[j] ) - CalcArea( aInter )
 208                             + nFuzzy >= CalcArea( aUnion ) )
 209                     {
 210                         (*this)[i] = aUnion;
 211                         (*this)[j].Width(0);
 212                         bRemoved = true;
 213                         bAgain = true;
 214                     }
 215                 }
 216             }
 217         }
 218         // Instead of repeated erase() we Width(0) the elements, and now erase
 219         // all empty elements just once.
 220         if( bRemoved )
 221             resize( std::remove_if(begin(), end(), [](const SwRect& rect) { return rect.IsEmpty(); }) - begin());
 222         // Code paths setting bAgain alter elements of the vector, possibly breaking
 223         // the Y-axis optimization, so run another pass just to make sure. The adjacent-rects
 224         // merging code may possibly benefit from a repeated pass also if two pairs of merged
 225         // rects might get merged again and this pass skipped that.
 226     } while(bAgain);
 227 }
 228
 229 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */