basegfx/source/polygon/b2dpolygontools.cxx | 100 ++++++++++++++++++++++++++++
include/basegfx/polygon/b2dpolygontools.hxx | 19 +++++
slideshow/source/engine/slideshowimpl.cxx | 38 +++++++---
3 files changed, 144 insertions(+), 13 deletions(-)
New commits:
commit 44c0f2da567b49ef8a539958a834f1bc841c2003
Author: Regina Henschel <rb.hensc...@t-online.de>
AuthorDate: Thu Aug 17 19:30:56 2023 +0200
Commit: Regina Henschel <rb.hensc...@t-online.de>
CommitDate: Thu Aug 24 17:54:46 2023 +0200
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.hensc...@t-online.de>
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: */
diff --git a/include/basegfx/polygon/b2dpolygontools.hxx
b/include/basegfx/polygon/b2dpolygontools.hxx
index d5aa092ed9cb..2f73b76d33c6 100644
--- a/include/basegfx/polygon/b2dpolygontools.hxx
+++ b/include/basegfx/polygon/b2dpolygontools.hxx
@@ -524,6 +524,25 @@ namespace basegfx::utils
*/
BASEGFX_DLLPUBLIC OUString exportToSvgPoints( const B2DPolygon& rPoly
);
+ /** Reduces the number of points using the Ramer-Douglas-Peucker (RDP)
algorithm. If the input
+ polygon has control points or less than three points, the input
polygon is returned
+ unchanged. Otherwise, a simplified polygon is returned. If the
input polygon is closed,
+ the caller is expected to ensure that the first and last points of
the polygon are
+ identical. The polygon is treated as open in this case. Closing
the result polygon is not
+ performed here, but left to the caller.
+
+ @param rCandidate
+ The source polygon from which the reduced polygon is generated
+
+ @param fTolerance
+ The tolerance for the RDP algorithm.
+
+ @return
+ A newly created polygon with reduced point count.
+ */
+ BASEGFX_DLLPUBLIC B2DPolygon createSimplifiedPolygon(const B2DPolygon&
rCandidate,
+ const double
fTolerance);
+
} // end of namespace basegfx::utils
/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/slideshow/source/engine/slideshowimpl.cxx
b/slideshow/source/engine/slideshowimpl.cxx
index 81661fab215a..34cb4418db9d 100644
--- a/slideshow/source/engine/slideshowimpl.cxx
+++ b/slideshow/source/engine/slideshowimpl.cxx
@@ -36,6 +36,7 @@
#include <basegfx/point/b2dpoint.hxx>
#include <basegfx/polygon/b2dpolygon.hxx>
+#include <basegfx/polygon/b2dpolygontools.hxx>
#include <basegfx/utils/canvastools.hxx>
#include <sal/log.hxx>
@@ -1499,11 +1500,17 @@ void SlideShowImpl::registerUserPaintPolygons( const
uno::Reference< lang::XMult
xDrawnInSlideshow->setPropertyValue("IsLocked", aPropLayer);
//Register polygons for each slide
- for( const auto& rPoly : maPolygons )
+ // The polygons are simplified using the Ramer-Douglas-Peucker algorithm.
+ // This is the therefore needed tolerance. Ideally the value should be
user defined.
+ // For now a suitable value is found experimental.
+ constexpr double fTolerance(12);
+ for (const auto& rPoly : maPolygons)
{
PolyPolygonVector aPolygons = rPoly.second;
+ if (aPolygons.empty())
+ continue;
//Get shapes for the slide
- css::uno::Reference< css::drawing::XShapes > Shapes = rPoly.first;
+ css::uno::Reference<css::drawing::XShapes> Shapes = rPoly.first;
//Retrieve polygons for one slide
// #tdf112687 A pen drawing in slideshow is actually a chain of
individual line shapes, where
@@ -1512,15 +1519,17 @@ void SlideShowImpl::registerUserPaintPolygons( const
uno::Reference< lang::XMult
// slide.
::basegfx::B2DPolygon aDrawingPoints;
cppcanvas::PolyPolygonSharedPtr pFirstPolyPoly = aPolygons.front(); //
for style properties
- for( const auto& pPolyPoly : aPolygons )
+ for (const auto& pPolyPoly : aPolygons)
{
// Actually, each item in aPolygons has two points, but wrapped in
a cppcanvas::PopyPolygon.
- ::basegfx::B2DPolyPolygon b2DPolyPoly =
::basegfx::unotools::b2DPolyPolygonFromXPolyPolygon2D(pPolyPoly->getUNOPolyPolygon());
+ ::basegfx::B2DPolyPolygon b2DPolyPoly
+ = ::basegfx::unotools::b2DPolyPolygonFromXPolyPolygon2D(
+ pPolyPoly->getUNOPolyPolygon());
//Normally there is only one polygon
- for(sal_uInt32 i=0; i< b2DPolyPoly.count();i++)
+ for (sal_uInt32 i = 0; i < b2DPolyPoly.count(); i++)
{
- const ::basegfx::B2DPolygon& aPoly =
b2DPolyPoly.getB2DPolygon(i);
+ const ::basegfx::B2DPolygon& aPoly =
b2DPolyPoly.getB2DPolygon(i);
if (aPoly.count() > 1) // otherwise skip it, count should be 2
{
@@ -1530,8 +1539,8 @@ void SlideShowImpl::registerUserPaintPolygons( const
uno::Reference< lang::XMult
pFirstPolyPoly = pPolyPoly;
continue;
}
-
- basegfx::B2DPoint aLast =
aDrawingPoints.getB2DPoint(aDrawingPoints.count() - 1);
+ basegfx::B2DPoint aLast
+ = aDrawingPoints.getB2DPoint(aDrawingPoints.count() -
1);
if (aPoly.getB2DPoint(0).equal(aLast))
{
aDrawingPoints.append(aPoly, 1);
@@ -1540,12 +1549,14 @@ void SlideShowImpl::registerUserPaintPolygons( const
uno::Reference< lang::XMult
// Put what we have collected to the slide and then start
a new pen drawing object
//create the PolyLineShape. The points will be in its
PolyPolygon property.
- uno::Reference< uno::XInterface >
polyshape(xDocFactory->createInstance(
-
"com.sun.star.drawing.PolyLineShape" ) );
- uno::Reference< drawing::XShape > rPolyShape(polyshape,
uno::UNO_QUERY);
+ uno::Reference<uno::XInterface> polyshape(
+
xDocFactory->createInstance("com.sun.star.drawing.PolyLineShape"));
+ uno::Reference<drawing::XShape> rPolyShape(polyshape,
uno::UNO_QUERY);
//Add the shape to the slide
Shapes->add(rPolyShape);
//Construct a sequence of points sequence
+ aDrawingPoints
+ =
basegfx::utils::createSimplifiedPolygon(aDrawingPoints, fTolerance);
const drawing::PointSequenceSequence aRetval
=
lcl_createPointSequenceSequenceFromB2DPolygon(aDrawingPoints);
//Fill the properties
@@ -1563,12 +1574,13 @@ void SlideShowImpl::registerUserPaintPolygons( const
uno::Reference< lang::XMult
if (aDrawingPoints.count() > 1)
{
//create the PolyLineShape. The points will be in its PolyPolygon
property.
- uno::Reference< uno::XInterface > polyshape(
+ uno::Reference<uno::XInterface> polyshape(
xDocFactory->createInstance("com.sun.star.drawing.PolyLineShape"));
- uno::Reference< drawing::XShape > rPolyShape(polyshape,
uno::UNO_QUERY);
+ uno::Reference<drawing::XShape> rPolyShape(polyshape,
uno::UNO_QUERY);
//Add the shape to the slide
Shapes->add(rPolyShape);
//Construct a sequence of points sequence
+ aDrawingPoints =
basegfx::utils::createSimplifiedPolygon(aDrawingPoints, fTolerance);
drawing::PointSequenceSequence aRetval
=
lcl_createPointSequenceSequenceFromB2DPolygon(aDrawingPoints);
//Fill the properties
