do not try to merge polygons if they do not share a point (tdf#136222)

If two polygons do not share a point, then they do not share an edge,
so they cannot be adjacent polygons. As a side-effect this avoids
the problem with tdf#136222, as it turns out
basegfx::utils::mergeToSinglePolyPolygon() is broken with polygons
that are almost but not quite adjacent.

Change-Id: Ibf290cc886d7c337fd04c925b551b2e7773a6b70
Reviewed-on: https://gerrit.libreoffice.org/c/core/+/102985
Reviewed-by: Noel Grandin <noel.grandin@collabora.co.uk>
Reviewed-by: Luboš Luňák <l.lunak@collabora.com>
Tested-by: Jenkins
(cherry picked from commit 859596233146590f7ebac1f05bbb83ce5ea8aac4)
Reviewed-on: https://gerrit.libreoffice.org/c/core/+/103052
Reviewed-by: Caolán McNamara <caolanm@redhat.com>

1 files changed, 41 insertions, 0 deletions

diff --git a/vcl/skia/gdiimpl.cxx b/vcl/skia/gdiimpl.cxx
index 9fa79f498801..0555cb9549f6 100644
--- a/vcl/skia/gdiimpl.cxx
+++ b/vcl/skia/gdiimpl.cxx
@@ -40,6 +40,7 @@
 #include <basegfx/polygon/b2dpolygontools.hxx>
 #include <basegfx/polygon/b2dpolypolygontools.hxx>
 #include <basegfx/polygon/b2dpolypolygoncutter.hxx>
+#include <o3tl/sorted_vector.hxx>
 
 namespace
 {
@@ -830,6 +831,19 @@ void SkiaSalGraphicsImpl::performDrawPolyPolygon(const basegfx::B2DPolyPolygon&
 #endif
 }
 
+namespace
+{
+struct LessThan
+{
+    bool operator()(const basegfx::B2DPoint& point1, const basegfx::B2DPoint& point2) const
+    {
+        if (basegfx::fTools::equal(point1.getX(), point2.getX()))
+            return basegfx::fTools::less(point1.getY(), point2.getY());
+        return basegfx::fTools::less(point1.getX(), point2.getX());
+    }
+};
+} // namespace
+
 bool SkiaSalGraphicsImpl::delayDrawPolyPolygon(const basegfx::B2DPolyPolygon& aPolyPolygon,
                                                double fTransparency)
 {
@@ -858,6 +872,9 @@ bool SkiaSalGraphicsImpl::delayDrawPolyPolygon(const basegfx::B2DPolyPolygon& aP
     // so they do not need joining.
     if (aPolyPolygon.count() != 1)
         return false;
+    // If the polygon is not closed, it doesn't mark an area to be filled.
+    if (!aPolyPolygon.isClosed())
+        return false;
     // If a polygon does not contain a straight line, i.e. it's all curves, then do not merge.
     // First of all that's even more expensive, and second it's very unlikely that it's a polygon
     // split into more polygons.
@@ -870,6 +887,28 @@ bool SkiaSalGraphicsImpl::delayDrawPolyPolygon(const basegfx::B2DPolyPolygon& aP
     {
         checkPendingDrawing(); // Cannot be parts of the same larger polygon, draw the last and reset.
     }
+    if (!mLastPolyPolygonInfo.polygons.empty())
+    {
+        assert(aPolyPolygon.count() == 1);
+        assert(mLastPolyPolygonInfo.polygons.back().count() == 1);
+        // Check if the new and the previous polygon share at least one point. If not, then they
+        // cannot be adjacent polygons, so there's no point in trying to merge them.
+        bool sharePoint = false;
+        const basegfx::B2DPolygon& poly1 = aPolyPolygon.getB2DPolygon(0);
+        const basegfx::B2DPolygon& poly2 = mLastPolyPolygonInfo.polygons.back().getB2DPolygon(0);
+        o3tl::sorted_vector<basegfx::B2DPoint, LessThan> poly1Points; // for O(n log n)
+        poly1Points.reserve(poly1.count());
+        for (sal_uInt32 i = 0; i < poly1.count(); ++i)
+            poly1Points.insert(poly1.getB2DPoint(i));
+        for (sal_uInt32 i = 0; i < poly2.count(); ++i)
+            if (poly1Points.find(poly2.getB2DPoint(i)) != poly1Points.end())
+            {
+                sharePoint = true;
+                break;
+            }
+        if (!sharePoint)
+            checkPendingDrawing(); // Draw the previous one and reset.
+    }
     // Collect the polygons that can be possibly merged. Do the merging only once at the end,
     // because it's not a cheap operation.
     mLastPolyPolygonInfo.polygons.push_back(aPolyPolygon);
@@ -889,6 +928,8 @@ void SkiaSalGraphicsImpl::checkPendingDrawing()
         if (polygons.size() == 1)
             performDrawPolyPolygon(polygons.front(), transparency, true);
         else
+            // TODO: tdf#136222 shows that basegfx::utils::mergeToSinglePolyPolygon() is unreliable
+            // in corner cases, possibly either a bug or rounding errors somewhere.
             performDrawPolyPolygon(basegfx::utils::mergeToSinglePolyPolygon(polygons), transparency,
                                    true);
     }