svx/source/sdr/overlay/overlayselection.cxx | 141 +++++++++++++++++++++++++---
1 file changed, 128 insertions(+), 13 deletions(-)
New commits:
commit e5bc241d197ed946fc4a2ba4901e25c7f82cab85
Author: Noel Grandin <noel.gran...@collabora.co.uk>
AuthorDate: Wed Apr 3 16:12:12 2024 +0200
Commit: Noel Grandin <noel.gran...@collabora.co.uk>
CommitDate: Sat Apr 20 14:55:40 2024 +0200
cool#8571 use better algorithm for generating selection overlay
when we know that the selection overlay consists purely of rectanges, we
can use a faster algorithm to generate the combined polygon
Change-Id: I15129facc6e682261fb59e79cf93b0e9d9e114b5
Reviewed-on: https://gerrit.libreoffice.org/c/core/+/165752
Tested-by: Jenkins
Reviewed-by: Noel Grandin <noel.gran...@collabora.co.uk>
diff --git a/svx/source/sdr/overlay/overlayselection.cxx
b/svx/source/sdr/overlay/overlayselection.cxx
index 9644650263c9..8dafb00778a5 100644
--- a/svx/source/sdr/overlay/overlayselection.cxx
+++ b/svx/source/sdr/overlay/overlayselection.cxx
@@ -31,33 +31,149 @@
#include <basegfx/polygon/b2dpolypolygoncutter.hxx>
#include <svx/sdr/overlay/overlaymanager.hxx>
#include <officecfg/Office/Common.hxx>
+#include <o3tl/sorted_vector.hxx>
+#include <map>
+namespace
+{
+struct B2DPointCompare
+{
+ bool operator()(const basegfx::B2DPoint& lhs, const basegfx::B2DPoint&
rhs) const
+ {
+ if (lhs.getX() < rhs.getX())
+ return true;
+ if (lhs.getX() > rhs.getX())
+ return false;
+ return lhs.getY() < rhs.getY();
+ }
+};
+
+struct B2DPointCompareYThenX
+{
+ bool operator()(const basegfx::B2DPoint& lhs, const basegfx::B2DPoint&
rhs) const
+ {
+ if (lhs.getY() < rhs.getY())
+ return true;
+ if (lhs.getY() > rhs.getY())
+ return false;
+ return lhs.getX() < rhs.getX();
+ }
+};
+
+}
namespace sdr::overlay
{
- // combine rages geometrically to a single, ORed polygon
- static basegfx::B2DPolyPolygon impCombineRangesToPolyPolygon(const
std::vector< basegfx::B2DRange >& rRanges)
+
+ // Combine rectangles geometrically to a single OR'ed polygon.
+ // Algorithm is from
+ // "Uniqueness of orthogonal connect-the-dots" Joseph O'Rourke 1988
+ // The basic algorithm is:
+ // Sort points by lowest x, lowest y
+ // Go through each column and create edges between the vertices 2i and
2i + 1 in that column
+ // Sort points by lowest y, lowest x
+ // Go through each row and create edges between the vertices 2i and 2i +
1 in that row.
+ //
+ static basegfx::B2DPolyPolygon impCombineRectanglesToPolyPolygon(const
std::vector< basegfx::B2DRange >& rRectangles)
+ {
+ o3tl::sorted_vector<basegfx::B2DPoint, B2DPointCompare> sort_x;
+ for (auto const & rRect : rRectangles)
{
- const sal_uInt32 nCount(rRanges.size());
- basegfx::B2DPolyPolygon aRetval;
+ auto checkPoint = [&sort_x](double x, double y)
+ {
+ basegfx::B2DPoint pt(x, y);
+ auto it = sort_x.find(pt);
+ if (it != sort_x.end()) // Shared vertice, remove it.
+ sort_x.erase(it);
+ else
+ sort_x.insert(pt);
+ };
+ checkPoint(rRect.getMinX(), rRect.getMinY());
+ checkPoint(rRect.getMinX(), rRect.getMaxY());
+ checkPoint(rRect.getMaxX(), rRect.getMinY());
+ checkPoint(rRect.getMaxX(), rRect.getMaxY());
+ }
+
+
+ o3tl::sorted_vector<basegfx::B2DPoint, B2DPointCompareYThenX> sort_y;
+ for (auto const & i : sort_x)
+ sort_y.insert(i);
- for(sal_uInt32 a(0); a < nCount; a++)
+ std::map<basegfx::B2DPoint, basegfx::B2DPoint, B2DPointCompare>
edges_h;
+ std::map<basegfx::B2DPoint, basegfx::B2DPoint, B2DPointCompare>
edges_v;
+
+ size_t i = 0;
+ while (i < sort_x.size())
+ {
+ auto curr_y = sort_y[i].getY();
+ while (i < sort_x.size() && sort_y[i].getY() == curr_y)
+ {
+ edges_h[sort_y[i]] = sort_y[i + 1];
+ edges_h[sort_y[i + 1]] = sort_y[i];
+ i += 2;
+ }
+ }
+ i = 0;
+ while (i < sort_x.size())
+ {
+ auto curr_x = sort_x[i].getX();
+ while (i < sort_x.size() && sort_x[i].getX() == curr_x)
{
- const basegfx::B2DPolygon
aDiscretePolygon(basegfx::utils::createPolygonFromRect(rRanges[a]));
+ edges_v[sort_x[i]] = sort_x[i + 1];
+ edges_v[sort_x[i + 1]] = sort_x[i];
+ i += 2;
+ }
+ }
- if(0 == a)
+ // Get all the polygons.
+ basegfx::B2DPolyPolygon aPolyPolygon;
+ std::vector<std::tuple<basegfx::B2DPoint, bool>> tmpPolygon;
+ while (!edges_h.empty())
+ {
+ tmpPolygon.clear();
+ // We can start with any point.
+ basegfx::B2DPoint pt = edges_h.begin()->first;
+ edges_h.erase(edges_h.begin());
+ tmpPolygon.push_back({pt, false});
+ for (;;)
+ {
+ auto [curr, e] = tmpPolygon.back();
+ if (!e)
{
- aRetval.append(aDiscretePolygon);
+ auto it = edges_v.find(curr);
+ auto next_vertex = it->second;
+ edges_v.erase(it);
+ tmpPolygon.push_back({next_vertex, true});
}
else
{
- aRetval = basegfx::utils::solvePolygonOperationOr(aRetval,
basegfx::B2DPolyPolygon(aDiscretePolygon));
+ auto it = edges_h.find(curr);
+ auto next_vertex = it->second;
+ edges_h.erase(it);
+ tmpPolygon.push_back({next_vertex, false});
+ }
+ if (tmpPolygon.back() == tmpPolygon.front())
+ {
+ // Closed polygon
+ break;
}
}
-
- return aRetval;
+ for (auto const & pair : tmpPolygon)
+ {
+ auto const & vertex = std::get<0>(pair);
+ edges_h.erase(vertex);
+ edges_v.erase(vertex);
+ }
+ basegfx::B2DPolygon aPoly;
+ aPoly.reserve(tmpPolygon.size());
+ for (auto const & pair : tmpPolygon)
+ aPoly.append(std::get<0>(pair));
+ aPolyPolygon.append(std::move(aPoly));
}
+ return aPolyPolygon;
+ }
+
// check if wanted type OverlayType::Transparent or OverlayType::Solid
// is possible. If not, fallback to invert mode (classic mode)
static OverlayType impCheckPossibleOverlayType(OverlayType
aOverlayType)
@@ -134,10 +250,9 @@ namespace sdr::overlay
if(mbBorder)
{
- basegfx::B2DPolyPolygon
aBorderPolyPolygon(impCombineRangesToPolyPolygon(maRanges));
drawinglayer::primitive2d::Primitive2DReference
aSelectionOutline(
new
drawinglayer::primitive2d::PolyPolygonHairlinePrimitive2D(
- std::move(aBorderPolyPolygon),
+ impCombineRectanglesToPolyPolygon(maRanges),
aRGBColor));
// add both to result
