diff options
author | Luboš Luňák <l.lunak@collabora.com> | 2021-09-17 00:14:08 +0200 |
---|---|---|
committer | Luboš Luňák <l.lunak@collabora.com> | 2021-09-19 09:33:23 +0200 |
commit | cc832cbbe2e6d9af16919f7d3801ec52b94a792a (patch) | |
tree | 6c0f5a361ac2dcf701feef5b154131982a064413 /sw/source | |
parent | f90fac8e0c7cf4b4ffcca8ad9cdc076460360cdb (diff) |
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/+/122216
Tested-by: Jenkins CollaboraOffice <jenkinscollaboraoffice@gmail.com>
Reviewed-by: Luboš Luňák <l.lunak@collabora.com>
Diffstat (limited to 'sw/source')
-rw-r--r-- | sw/source/core/bastyp/swregion.cxx | 21 |
1 files changed, 16 insertions, 5 deletions
diff --git a/sw/source/core/bastyp/swregion.cxx b/sw/source/core/bastyp/swregion.cxx index defc4c07e95c..55b857ffdefa 100644 --- a/sw/source/core/bastyp/swregion.cxx +++ b/sw/source/core/bastyp/swregion.cxx @@ -147,23 +147,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 @@ -187,7 +196,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] ); @@ -198,12 +206,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); } |