tdf#112687 Simplify polylines from slideshow annotations

Drawing with 'mouse as pen' in a slideshow creates hundreds of points.
By commit 631964a2ce1da3fbbeb53a5550c0e6728ba644aa they are at least
already combines to a polyline. The patch here now reduces the amount
of points in such polyline to a reasonable number. If at some point the
drawings in the slideshow are improved, this can be removed.

The reduction is performed using the Douglas-Peucker algorithm. I have
added the method to b2dpolygontools because I think it could be useful in
other contexts.

Change-Id: I9224ec3546d4442da8bc348aea8ce7b88fcc46dc
Reviewed-on: https://gerrit.libreoffice.org/c/core/+/155811
Tested-by: Jenkins
Reviewed-by: Regina Henschel <rb.henschel@t-online.de>

1 files changed, 100 insertions, 0 deletions

diff --git a/basegfx/source/polygon/b2dpolygontools.cxx b/basegfx/source/polygon/b2dpolygontools.cxx
index 900ab735a1e0..04a22df578a6 100644
--- a/basegfx/source/polygon/b2dpolygontools.cxx
+++ b/basegfx/source/polygon/b2dpolygontools.cxx
@@ -18,6 +18,7 @@
  */
 #include <numeric>
 #include <algorithm>
+#include <stack>
 
 #include <basegfx/numeric/ftools.hxx>
 #include <basegfx/polygon/b2dpolygontools.hxx>
@@ -3574,6 +3575,105 @@ namespace basegfx::utils
             }
         }
 
+B2DPolygon createSimplifiedPolygon(const B2DPolygon& rCandidate, const double fTolerance)
+{
+    const sal_uInt32 nPointCount(rCandidate.count());
+    if (nPointCount < 3 || rCandidate.areControlPointsUsed())
+        return rCandidate;
+
+    // The solution does not use recursion directly, since this could lead to a stack overflow if
+    // nPointCount is very large. Instead, an own stack is used. This does not contain points, but
+    // pairs of low and high index of a range in rCandidate. A parallel boolean vector is used to note
+    // whether a point of rCandidate belongs to the output polygon or not.
+    std::vector<bool> bIsKeptVec(nPointCount, false);
+    bIsKeptVec[0] = true;
+    bIsKeptVec[nPointCount - 1] = true;
+    sal_uInt32 nKept = 2;
+    std::stack<std::pair<sal_uInt32, sal_uInt32>> aUnfinishedRangesStack;
+
+    // The RDP algorithm draws a straight line from the first point to the last point of a range.
+    // Then, from the inner points of the range, the point that has the largest distance to the line
+    // is determined. If the distance is greater than the tolerance, this point is kept and the lower
+    // and upper sub-segments of the range are treated in the same way. If the distance is smaller
+    // than the tolerance, none of the inner points will be kept.
+    sal_uInt32 nLowIndex = 0;
+    sal_uInt32 nHighIndex = nPointCount - 1;
+    bool bContinue = true;
+    do
+    {
+        bContinue = false;
+        if (nHighIndex - nLowIndex < 2) // maximal two points, range is finished.
+        {
+            // continue with sibling upper range if any
+            if (!aUnfinishedRangesStack.empty())
+            {
+                std::pair<sal_uInt32, sal_uInt32> aIndexPair = aUnfinishedRangesStack.top();
+                aUnfinishedRangesStack.pop();
+                nLowIndex = aIndexPair.first;
+                nHighIndex = aIndexPair.second;
+                bContinue = true;
+            }
+        }
+        else // the range needs examine the max distance
+        {
+            // Get maximal distance of inner points of the range to the straight line from start to
+            // end point of the range.
+            // For calculation of the distance we use the Hesse normal form of the straight line.
+            B2DPoint aLowPoint = rCandidate.getB2DPoint(nLowIndex);
+            B2DPoint aHighPoint = rCandidate.getB2DPoint(nHighIndex);
+            B2DVector aNormalVec
+                = basegfx::getNormalizedPerpendicular(B2DVector(aHighPoint) - B2DVector(aLowPoint));
+            double fLineOriginDistance = aNormalVec.scalar(B2DVector(aLowPoint));
+            double fMaxDist = 0;
+            sal_uInt32 nMaxPointIndex = nLowIndex;
+            for (sal_uInt32 i = nLowIndex + 1; i < nHighIndex; i++)
+            {
+                double fDistance
+                    = aNormalVec.scalar(B2DVector(rCandidate.getB2DPoint(i))) - fLineOriginDistance;
+                if (std::fabs(fDistance) > fMaxDist)
+                {
+                    fMaxDist = std::fabs(fDistance);
+                    nMaxPointIndex = i;
+                }
+            }
+
+            if (fMaxDist >= fTolerance)
+            {
+                // We need to divide the current range into two sub ranges.
+                bIsKeptVec[nMaxPointIndex] = true;
+                nKept++;
+                // continue with lower sub range and push upper sub range to stack
+                aUnfinishedRangesStack.push(std::make_pair(nMaxPointIndex, nHighIndex));
+                nHighIndex = nMaxPointIndex;
+                bContinue = true;
+            }
+            else
+            {
+                // We do not keep any of the inner points of the current range.
+                // continue with sibling upper range if any
+                if (!aUnfinishedRangesStack.empty())
+                {
+                    std::pair<sal_uInt32, sal_uInt32> aIndexPair = aUnfinishedRangesStack.top();
+                    aUnfinishedRangesStack.pop();
+                    nLowIndex = aIndexPair.first;
+                    nHighIndex = aIndexPair.second;
+                    bContinue = true;
+                }
+            }
+        }
+    } while (bContinue);
+
+    // Put all points which are marked as "keep" into the result polygon
+    B2DPolygon aResultPolygon;
+    aResultPolygon.reserve(nKept);
+    for (sal_uInt32 i = 0; i < nPointCount; i++)
+    {
+        if (bIsKeptVec[i])
+            aResultPolygon.append(rCandidate.getB2DPoint(i));
+    }
+    return aResultPolygon;
+}
+
 } // end of namespace
 
 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */