LibreOffice Module sw (master) 1
swregion.cxx
Go to the documentation of this file.
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
24SwRegionRects::SwRegionRects( const SwRect &rStartRect, sal_uInt16 nInit ) :
25 m_aOrigin( rStartRect )
26{
27 reserve(nInit);
28 push_back( m_aOrigin );
29}
30
31SwRegionRects::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.
39inline 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
54{
55 push_back( rRect );
56}
57
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
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
143static inline SwTwips CalcArea( const SwRect &rRect )
144{
145 return rRect.Width() * rRect.Height();
146}
147
149{
150 for (size_type i = 0; i < size(); ++i )
151 (*this)[ i ].Intersection( m_aOrigin );
152}
153
154// combine all adjacent rectangles
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: */
Of course Writer needs its own rectangles.
Definition: swrect.hxx:35
void Height(tools::Long nNew)
Definition: swrect.hxx:193
bool IsEmpty() const
Definition: swrect.hxx:304
void Top(const tools::Long nTop)
Definition: swrect.hxx:206
void Bottom(const tools::Long nBottom)
Definition: swrect.hxx:211
SwRect GetUnion(const SwRect &rRect) const
Definition: swrect.hxx:382
SwRect & Intersection_(const SwRect &rRect)
Definition: swrect.cxx:81
SwRect GetIntersection(const SwRect &rRect) const
Definition: swrect.hxx:391
bool Overlaps(const SwRect &rRect) const
Definition: swrect.hxx:374
void Left(const tools::Long nLeft)
Definition: swrect.hxx:197
void Width(tools::Long nNew)
Definition: swrect.hxx:189
void operator-=(const SwRect &rRect)
Delete all overlaps of the Rects in array with the given <rRect>
Definition: swregion.cxx:64
void InsertRect(const SwRect &rRect, const sal_uInt16 nPos, bool &rDel)
Definition: swregion.cxx:39
void operator+=(const SwRect &rRect)
Definition: swregion.cxx:53
void LimitToOrigin()
Definition: swregion.cxx:148
SwRegionRects(const SwRect &rStartRect, sal_uInt16 nInit=20)
Definition: swregion.cxx:24
void Compress(CompressType type)
Definition: swregion.cxx:155
void Invert()
invert current rectangle
Definition: swregion.cxx:126
SwRect m_aOrigin
Definition: swregion.hxx:37
sal_uInt16 nPos
size
int i
void swap(cow_wrapper< T, P > &a, cow_wrapper< T, P > &b)
enumrange< T >::Iterator begin(enumrange< T >)
end
long Long
static SwTwips CalcArea(const SwRect &rRect)
Definition: swregion.cxx:143
tools::Long SwTwips
Definition: swtypes.hxx:51
ResultType type