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>
diff --git a/basegfx/source/polygon/b2dpolygontools.cxx b/basegfx/source/polygon/b2dpolygontools.cxx
index 900ab73..04a22df 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 d5aa092e..2f73b76 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 81661fa..34cb4418 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
