sw/source/core/bastyp/swregion.cxx | 21 ++++++++++++++++-----
1 file changed, 16 insertions(+), 5 deletions(-)
New commits:
commit bc09e2c08f9db85c8f1cbd9c0e71e3e60d6d6ed3
Author: Luboš Luňák <l.lu...@collabora.com>
AuthorDate: Fri Sep 17 00:14:08 2021 +0200
Commit: Luboš Luňák <l.lu...@collabora.com>
CommitDate: Sun Sep 19 09:32:15 2021 +0200
optimize SwRegionRects::Compress() more
Implement Noel's idea of sorting the rectangles by Y axis and then
considering only pairs of rectangles that are close enough to
possibly get merged.
Change-Id: Iac4a94fc411237f8c0fb5812906dc832be398cfa
Reviewed-on: https://gerrit.libreoffice.org/c/core/+/122214
Tested-by: Jenkins
Reviewed-by: Luboš Luňák <l.lu...@collabora.com>
diff --git a/sw/source/core/bastyp/swregion.cxx
b/sw/source/core/bastyp/swregion.cxx
index 54b237c3756d..19ab3c3c988d 100644
--- a/sw/source/core/bastyp/swregion.cxx
+++ b/sw/source/core/bastyp/swregion.cxx
@@ -146,23 +146,32 @@ void SwRegionRects::Compress()
bool bAgain;
do
{
+ sort( begin(), end(), []( const SwRect& l, const SwRect& r ) { return
l.Top() < r.Top(); } );
bAgain = false;
for (size_type i = 0; i < size(); ++i )
{
- for ( size_type j = i+1; j < size(); ++j )
+ // Rectangles are sorted by Y axis, so check only pairs of
rectangles
+ // that are possibly overlapping or adjacent or close enough to be
grouped by the fuzzy
+ // code below.
+ const tools::Long nFuzzy = 1361513;
+ const tools::Long yMax = (*this)[i].Bottom() + nFuzzy /
(*this)[i].Width();
+ size_type j = i+1;
+ while( j < size() && (*this)[j].Top() <= yMax )
+ ++j;
+ --j;
+ // Walk backwards for simpler and faster erase().
+ for ( ; j >= i+1; --j )
{
// If one rectangle contains a second completely than the
latter
// does not need to be stored and can be deleted
if ( (*this)[i].IsInside( (*this)[j] ) )
{
erase( begin() + j );
- --j;
}
else if ( (*this)[j].IsInside( (*this)[i] ) )
{
(*this)[i] = (*this)[j];
erase( begin() + j );
- --j;
bAgain = true;
}
else
@@ -186,7 +195,6 @@ void SwRegionRects::Compress()
// paints), the area of the union can be a little bit
larger:
// ( 9622 * 141.5 = 1361513 ~= a quarter (1/4) centimeter
wider
// than the width of an A4 page
- const tools::Long nFuzzy = 1361513;
SwRect aUnion( (*this)[i] );
aUnion.Union( (*this)[j] );
SwRect aInter( (*this)[i] );
@@ -197,12 +205,15 @@ void SwRegionRects::Compress()
{
(*this)[i] = aUnion;
erase( begin() + j );
- --j;
bAgain = true;
}
}
}
}
+ // Code paths setting bAgain alter elements of the vector, possibly
breaking
+ // the Y-axis optimization, so run another pass just to make sure. The
adjacent-rects
+ // merging code may possibly benefit from a repeated pass also if two
pairs of merged
+ // rects might get merged again and this pass skipped that.
} while(bAgain);
}
