/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
/*
* This file is part of the LibreOffice project.
*
* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/.
*
* This file incorporates work covered by the following license notice:
*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed
* with this work for additional information regarding copyright
* ownership. The ASF licenses this file to you under the Apache
* License, Version 2.0 (the "License"); you may not use this file
* except in compliance with the License. You may obtain a copy of
* the License at http://www.apache.org/licenses/LICENSE-2.0 .
*/
#include <osl/endian.h>
#include <osl/diagnose.h>
#include <sal/log.hxx>
#include <tools/bigint.hxx>
#include <tools/debug.hxx>
#include <tools/helpers.hxx>
#include <tools/stream.hxx>
#include <tools/vcompat.hxx>
#include <tools/gen.hxx>
#include <poly.h>
#include <o3tl/safeint.hxx>
#include <tools/line.hxx>
#include <tools/poly.hxx>
#include <basegfx/polygon/b2dpolygon.hxx>
#include <basegfx/point/b2dpoint.hxx>
#include <basegfx/vector/b2dvector.hxx>
#include <basegfx/polygon/b2dpolygontools.hxx>
#include <basegfx/curve/b2dcubicbezier.hxx>
#include <memory>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
#include <limits.h>
#include <cmath>
constexpr int EDGE_LEFT = 1;
constexpr int EDGE_TOP = 2;
constexpr int EDGE_RIGHT = 4;
constexpr int EDGE_BOTTOM = 8;
constexpr int EDGE_HORZ = EDGE_RIGHT | EDGE_LEFT;
constexpr int EDGE_VERT = EDGE_TOP | EDGE_BOTTOM;
constexpr double SMALL_DVALUE = 0.0000001;
#define FSQRT2 1.4142135623730950488016887242097
static double ImplGetParameter( const Point& rCenter, const Point& rPt, double fWR, double fHR )
{
const double nDX = static_cast<double>(rPt.X()) - rCenter.X();
const double nDY = static_cast<double>(rCenter.Y()) - rPt.Y();
double fAngle = atan2(nDY, nDX);
return atan2(fWR*sin(fAngle), fHR*cos(fAngle));
}
ImplPolygon::ImplPolygon( sal_uInt16 nInitSize )
{
ImplInitSize(nInitSize, false);
}
ImplPolygon::ImplPolygon( const ImplPolygon& rImpPoly )
{
if ( rImpPoly.mnPoints )
{
mxPointAry.reset(new Point[rImpPoly.mnPoints]);
memcpy(mxPointAry.get(), rImpPoly.mxPointAry.get(), rImpPoly.mnPoints * sizeof(Point));
if( rImpPoly.mxFlagAry )
{
mxFlagAry.reset(new PolyFlags[rImpPoly.mnPoints]);
memcpy(mxFlagAry.get(), rImpPoly.mxFlagAry.get(), rImpPoly.mnPoints);
}
}
mnPoints = rImpPoly.mnPoints;
}
ImplPolygon::ImplPolygon(ImplPolygon&& rImpPoly) noexcept
{
mxPointAry = std::move(rImpPoly.mxPointAry);
mxFlagAry = std::move(rImpPoly.mxFlagAry);
mnPoints = rImpPoly.mnPoints;
}
ImplPolygon::ImplPolygon( sal_uInt16 nInitSize, const Point* pInitAry, const PolyFlags* pInitFlags )
{
if ( nInitSize )
{
mxPointAry.reset(new Point[nInitSize]);
memcpy(mxPointAry.get(), pInitAry, nInitSize * sizeof(Point));
if( pInitFlags )
{
mxFlagAry.reset(new PolyFlags[nInitSize]);
memcpy(mxFlagAry.get(), pInitFlags, nInitSize);
}
}
mnPoints = nInitSize;
}
ImplPolygon::ImplPolygon( const tools::Rectangle& rRect )
{
if ( !rRect.IsEmpty() )
{
ImplInitSize(5);
mxPointAry[0] = rRect.TopLeft();
mxPointAry[1] = rRect.TopRight();
mxPointAry[2] = rRect.BottomRight();
mxPointAry[3] = rRect.BottomLeft();
mxPointAry[4] = rRect.TopLeft();
}
else
mnPoints = 0;
}
ImplPolygon::ImplPolygon( const tools::Rectangle& rRect, sal_uInt32 nHorzRound, sal_uInt32 nVertRound )
{
if ( !rRect.IsEmpty() )
{
tools::Rectangle aRect( rRect );
aRect.Normalize(); // SJ: i9140
nHorzRound = std::min( nHorzRound, static_cast<sal_uInt32>(std::abs( aRect.GetWidth() >> 1 )) );
nVertRound = std::min( nVertRound, static_cast<sal_uInt32>(std::abs( aRect.GetHeight() >> 1 )) );
if( !nHorzRound && !nVertRound )
{
ImplInitSize(5);
mxPointAry[0] = aRect.TopLeft();
mxPointAry[1] = aRect.TopRight();
mxPointAry[2] = aRect.BottomRight();
mxPointAry[3] = aRect.BottomLeft();
mxPointAry[4] = aRect.TopLeft();
}
else
{
const Point aTL( aRect.Left() + nHorzRound, aRect.Top() + nVertRound );
const Point aTR( aRect.Right() - nHorzRound, aRect.Top() + nVertRound );
const Point aBR( aRect.Right() - nHorzRound, aRect.Bottom() - nVertRound );
const Point aBL( aRect.Left() + nHorzRound, aRect.Bottom() - nVertRound );
tools::Polygon aEllipsePoly( Point(), nHorzRound, nVertRound );
sal_uInt16 i, nEnd, nSize4 = aEllipsePoly.GetSize() >> 2;
ImplInitSize(aEllipsePoly.GetSize() + 1);
const Point* pSrcAry = aEllipsePoly.GetConstPointAry();
Point* pDstAry = mxPointAry.get();
for( i = 0, nEnd = nSize4; i < nEnd; i++ )
pDstAry[ i ] = pSrcAry[ i ] + aTR;
for( nEnd = nEnd + nSize4; i < nEnd; i++ )
pDstAry[ i ] = pSrcAry[ i ] + aTL;
for( nEnd = nEnd + nSize4; i < nEnd; i++ )
pDstAry[ i ] = pSrcAry[ i ] + aBL;
for( nEnd = nEnd + nSize4; i < nEnd; i++ )
pDstAry[ i ] = pSrcAry[ i ] + aBR;
pDstAry[ nEnd ] = pDstAry[ 0 ];
}
}
else
mnPoints = 0;
}
ImplPolygon::ImplPolygon( const Point& rCenter, tools::Long nRadX, tools::Long nRadY )
{
if( nRadX && nRadY )
{
// Compute default (depends on size)
sal_uInt16 nPoints = std::clamp(
( M_PI * ( 1.5 * ( nRadX + nRadY ) - sqrt( std::fabs(double(nRadX) * nRadY) ) ) ),
32.0, 256.0 );
if( ( nRadX > 32 ) && ( nRadY > 32 ) && ( nRadX + nRadY ) < 8192 )
nPoints >>= 1;
// Ceil number of points until divisible by four
nPoints = (nPoints + 3) & ~3;
ImplInitSize(nPoints);
sal_uInt16 i;
sal_uInt16 nPoints2 = nPoints >> 1;
sal_uInt16 nPoints4 = nPoints >> 2;
double nAngle;
double nAngleStep = M_PI_2 / ( nPoints4 - 1 );
for( i=0, nAngle = 0.0; i < nPoints4; i++, nAngle += nAngleStep )
{
tools::Long nX = basegfx::fround<tools::Long>(nRadX * cos(nAngle));
tools::Long nY = basegfx::fround<tools::Long>(nRadY * -sin(nAngle));
Point* pPt = &(mxPointAry[i]);
pPt->setX( nX + rCenter.X() );
pPt->setY( nY + rCenter.Y() );
pPt = &(mxPointAry[nPoints2-i-1]);
pPt->setX( -nX + rCenter.X() );
pPt->setY( nY + rCenter.Y() );
pPt = &(mxPointAry[i+nPoints2]);
pPt->setX( -nX + rCenter.X() );
pPt->setY( -nY + rCenter.Y() );
pPt = &(mxPointAry[nPoints-i-1]);
pPt->setX( nX + rCenter.X() );
pPt->setY( -nY + rCenter.Y() );
}
}
else
mnPoints = 0;
}
ImplPolygon::ImplPolygon(const tools::Rectangle& rBound, const Point& rStart, const Point& rEnd,
PolyStyle eStyle, const bool bClockWiseArcDirection)
{
const auto nWidth = rBound.GetWidth();
const auto nHeight = rBound.GetHeight();
if ((nWidth != 0) && (nHeight != 0))
{
const Point aCenter(rBound.Center());
// tdf#142268 Get Top Left corner of rectangle (the rectangle is not always correctly created)
const auto aBoundLeft = rBound.Left() < aCenter.X() ? rBound.Left() : rBound.Right();
const auto aBoundTop = rBound.Top() < aCenter.Y() ? rBound.Top() : rBound.Bottom();
const auto nRadX = o3tl::saturating_sub(aCenter.X(), aBoundLeft);
const auto nRadY = o3tl::saturating_sub(aCenter.Y(), aBoundTop);
sal_uInt16 nPoints = std::clamp(
( M_PI * ( 1.5 * ( nRadX + nRadY ) - sqrt( std::fabs(double(nRadX) * nRadY) ) ) ),
32.0, 256.0 );
if (nRadX > 32 && nRadY > 32 && o3tl::saturating_add(nRadX, nRadY) < 8192)
nPoints >>= 1;
// compute threshold
const double fRadX = nRadX;
const double fRadY = nRadY;
const double fCenterX = aCenter.X();
const double fCenterY = aCenter.Y();
double fStart = ImplGetParameter( aCenter, rStart, fRadX, fRadY );
double fEnd = ImplGetParameter( aCenter, rEnd, fRadX, fRadY );
double fDiff = fEnd - fStart;
double fStep;
sal_uInt16 nStart;
sal_uInt16 nEnd;
if (bClockWiseArcDirection == false)
{
// #i73608# If startPoint is equal to endPoint, then draw full circle instead of nothing (as Metafiles spec)
if (fDiff <= 0.)
fDiff += 2. * M_PI;
}
else
{
fDiff = (2. * M_PI) - fDiff;
if (fDiff > 2. * M_PI)
fDiff -= 2. * M_PI;
}
// Proportionally shrink number of points( fDiff / (2PI) );
nPoints = std::max(static_cast<sal_uInt16>((fDiff / (2. * M_PI)) * nPoints), sal_uInt16(16));
fStep = fDiff / (nPoints - 1);
if (bClockWiseArcDirection == true)
fStep = -fStep;
if (PolyStyle::Pie == eStyle)
{
const Point aCenter2(basegfx::fround<tools::Long>(fCenterX),
basegfx::fround<tools::Long>(fCenterY));
nStart = 1;
nEnd = nPoints + 1;
ImplInitSize(nPoints + 2);
mxPointAry[0] = aCenter2;
mxPointAry[nEnd] = aCenter2;
}
else
{
ImplInitSize( ( PolyStyle::Chord == eStyle ) ? ( nPoints + 1 ) : nPoints );
nStart = 0;
nEnd = nPoints;
}
for(; nStart < nEnd; nStart++, fStart += fStep )
{
Point& rPt = mxPointAry[nStart];
rPt.setX(basegfx::fround<tools::Long>(fCenterX + fRadX * cos(fStart)));
rPt.setY(basegfx::fround<tools::Long>(fCenterY - fRadY * sin(fStart)));
}
if( PolyStyle::Chord == eStyle )
mxPointAry[nPoints] = mxPointAry[0];
}
else
mnPoints = 0;
}
ImplPolygon::ImplPolygon( const Point& rBezPt1, const Point& rCtrlPt1,
const Point& rBezPt2, const Point& rCtrlPt2, sal_uInt16 nPoints )
{
nPoints = ( 0 == nPoints ) ? 25 : ( ( nPoints < 2 ) ? 2 : nPoints );
const double fInc = 1.0 / ( nPoints - 1 );
double fK_1 = 0.0, fK1_1 = 1.0;
double fK_2, fK_3, fK1_2, fK1_3;
const double fX0 = rBezPt1.X();
const double fY0 = rBezPt1.Y();
const double fX1 = 3.0 * rCtrlPt1.X();
const double fY1 = 3.0 * rCtrlPt1.Y();
const double fX2 = 3.0 * rCtrlPt2.X();
const double fY2 = 3.0 * rCtrlPt2.Y();
const double fX3 = rBezPt2.X();
const double fY3 = rBezPt2.Y();
ImplInitSize(nPoints);
for( sal_uInt16 i = 0; i < nPoints; i++, fK_1 += fInc, fK1_1 -= fInc )
{
Point& rPt = mxPointAry[i];
fK_2 = fK_1;
fK_2 *= fK_1;
fK_3 = fK_2;
fK_3 *= fK_1;
fK1_2 = fK1_1;
fK1_2 *= fK1_1;
fK1_3 = fK1_2;
fK1_3 *= fK1_1;
double fK12 = fK_1 * fK1_2;
double fK21 = fK_2 * fK1_1;
rPt.setX(basegfx::fround<tools::Long>(fK1_3 * fX0 + fK12 * fX1 + fK21 * fX2 + fK_3 * fX3));
rPt.setY(basegfx::fround<tools::Long>(fK1_3 * fY0 + fK12 * fY1 + fK21 * fY2 + fK_3 * fY3));
}
}
// constructor to convert from basegfx::B2DPolygon
// #i76891# Needed to change from adding all control points (even for unused
// edges) and creating a fixed-size Polygon in the first run to creating the
// minimal Polygon. This requires a temporary Point- and Flag-Array for curves
// and a memcopy at ImplPolygon creation, but contains no zero-controlpoints
// for straight edges.
ImplPolygon::ImplPolygon(const basegfx::B2DPolygon& rPolygon)
: mnPoints(0)
{
const bool bCurve(rPolygon.areControlPointsUsed());
const bool bClosed(rPolygon.isClosed());
sal_uInt32 nB2DLocalCount(rPolygon.count());
if(bCurve)
{
// #127979# Reduce source point count hard to the limit of the tools Polygon
if(nB2DLocalCount > ((0x0000ffff / 3) - 1))
{
OSL_FAIL("Polygon::Polygon: Too many points in given B2DPolygon, need to reduce hard to maximum of tools Polygon (!)");
nB2DLocalCount = ((0x0000ffff / 3) - 1);
}
// calculate target point count
const sal_uInt32 nLoopCount(bClosed ? nB2DLocalCount : (nB2DLocalCount ? nB2DLocalCount - 1 : 0 ));
if(nLoopCount)
{
// calculate maximum array size and allocate; prepare insert index
const sal_uInt32 nMaxTargetCount((nLoopCount * 3) + 1);
ImplInitSize(static_cast< sal_uInt16 >(nMaxTargetCount), true);
// prepare insert index and current point
sal_uInt32 nArrayInsert(0);
basegfx::B2DCubicBezier aBezier;
aBezier.setStartPoint(rPolygon.getB2DPoint(0));
for(sal_uInt32 a(0); a < nLoopCount; a++)
{
// add current point (always) and remember StartPointIndex for evtl. later corrections
const Point aStartPoint(
basegfx::fround<tools::Long>(aBezier.getStartPoint().getX()),
basegfx::fround<tools::Long>(aBezier.getStartPoint().getY()));
const sal_uInt32 nStartPointIndex(nArrayInsert);
mxPointAry[nStartPointIndex] = aStartPoint;
mxFlagAry[nStartPointIndex] = PolyFlags::Normal;
nArrayInsert++;
// prepare next segment
const sal_uInt32 nNextIndex((a + 1) % nB2DLocalCount);
aBezier.setEndPoint(rPolygon.getB2DPoint(nNextIndex));
aBezier.setControlPointA(rPolygon.getNextControlPoint(a));
aBezier.setControlPointB(rPolygon.getPrevControlPoint(nNextIndex));
if(aBezier.isBezier())
{
// if one is used, add always two control points due to the old schema
mxPointAry[nArrayInsert] = Point(basegfx::fround<tools::Long>(aBezier.getControlPointA().getX()),
basegfx::fround<tools::Long>(aBezier.getControlPointA().getY()));
mxFlagAry[nArrayInsert] = PolyFlags::Control;
nArrayInsert++;
mxPointAry[nArrayInsert] = Point(basegfx::fround<tools::Long>(aBezier.getControlPointB().getX()),
basegfx::fround<tools::Long>(aBezier.getControlPointB().getY()));
mxFlagAry[nArrayInsert] = PolyFlags::Control;
nArrayInsert++;
}
// test continuity with previous control point to set flag value
if(aBezier.getControlPointA() != aBezier.getStartPoint() && (bClosed || a))
{
const basegfx::B2VectorContinuity eCont(rPolygon.getContinuityInPoint(a));
if(basegfx::B2VectorContinuity::C1 == eCont)
{
mxFlagAry[nStartPointIndex] = PolyFlags::Smooth;
}
else if(basegfx::B2VectorContinuity::C2 == eCont)
{
mxFlagAry[nStartPointIndex] = PolyFlags::Symmetric;
}
}
// prepare next polygon step
aBezier.setStartPoint(aBezier.getEndPoint());
}
if(bClosed)
{
// add first point again as closing point due to old definition
mxPointAry[nArrayInsert] = mxPointAry[0];
mxFlagAry[nArrayInsert] = PolyFlags::Normal;
nArrayInsert++;
}
else
{
// add last point as closing point
const basegfx::B2DPoint aClosingPoint(rPolygon.getB2DPoint(nB2DLocalCount - 1));
const Point aEnd(basegfx::fround<tools::Long>(aClosingPoint.getX()),
basegfx::fround<tools::Long>(aClosingPoint.getY()));
mxPointAry[nArrayInsert] = aEnd;
mxFlagAry[nArrayInsert] = PolyFlags::Normal;
nArrayInsert++;
}
DBG_ASSERT(nArrayInsert <= nMaxTargetCount, "Polygon::Polygon from basegfx::B2DPolygon: wrong max point count estimation (!)");
if(nArrayInsert != nMaxTargetCount)
{
ImplSetSize(static_cast< sal_uInt16 >(nArrayInsert));
}
}
}
else
{
// #127979# Reduce source point count hard to the limit of the tools Polygon
if(nB2DLocalCount > (0x0000ffff - 1))
{
OSL_FAIL("Polygon::Polygon: Too many points in given B2DPolygon, need to reduce hard to maximum of tools Polygon (!)");
nB2DLocalCount = (0x0000ffff - 1);
}
if(nB2DLocalCount)
{
// point list creation
const sal_uInt32 nTargetCount(nB2DLocalCount + (bClosed ? 1 : 0));
ImplInitSize(static_cast< sal_uInt16 >(nTargetCount));
sal_uInt16 nIndex(0);
for(sal_uInt32 a(0); a < nB2DLocalCount; a++)
{
basegfx::B2DPoint aB2DPoint(rPolygon.getB2DPoint(a));
Point aPoint(basegfx::fround<tools::Long>(aB2DPoint.getX()),
basegfx::fround<tools::Long>(aB2DPoint.getY()));
mxPointAry[nIndex++] = aPoint;
}
if(bClosed)
{
// add first point as closing point
mxPointAry[nIndex] = mxPointAry[0];
}
}
}
}
bool ImplPolygon::operator==( const ImplPolygon& rCandidate) const
{
return mnPoints == rCandidate.mnPoints &&
mxFlagAry.get() == rCandidate.mxFlagAry.get() &&
mxPointAry.get() == rCandidate.mxPointAry.get();
}
void ImplPolygon::ImplInitSize(sal_uInt16 nInitSize, bool bFlags)
{
if (nInitSize)
{
mxPointAry.reset(new Point[nInitSize]);
}
if (bFlags)
{
mxFlagAry.reset(new PolyFlags[nInitSize]);
memset(mxFlagAry.get(), 0, nInitSize);
}
mnPoints = nInitSize;
}
void ImplPolygon::ImplSetSize( sal_uInt16 nNewSize, bool bResize )
{
if( mnPoints == nNewSize )
return;
std::unique_ptr<Point[]> xNewAry;
if (nNewSize)
{
const std::size_t nNewSz(static_cast<std::size_t>(nNewSize)*sizeof(Point));
xNewAry.reset(new Point[nNewSize]);
if ( bResize )
{
// Copy the old points
if ( mnPoints < nNewSize )
{
// New points are already implicitly initialized to zero
const std::size_t nOldSz(mnPoints * sizeof(Point));
if (mxPointAry)
memcpy(xNewAry.get(), mxPointAry.get(), nOldSz);
}
else
{
if (mxPointAry)
memcpy(xNewAry.get(), mxPointAry.get(), nNewSz);
}
}
}
mxPointAry = std::move(xNewAry);
// take FlagArray into account, if applicable
if( mxFlagAry )
{
std::unique_ptr<PolyFlags[]> xNewFlagAry;
if( nNewSize )
{
xNewFlagAry.reset(new PolyFlags[nNewSize]);
if( bResize )
{
// copy the old flags
if ( mnPoints < nNewSize )
{
// initialize new flags to zero
memset(xNewFlagAry.get() + mnPoints, 0, nNewSize-mnPoints);
memcpy(xNewFlagAry.get(), mxFlagAry.get(), mnPoints);
}
else
memcpy(xNewFlagAry.get(), mxFlagAry.get(), nNewSize);
}
}
mxFlagAry = std::move(xNewFlagAry);
}
mnPoints = nNewSize;
}
bool ImplPolygon::ImplSplit( sal_uInt16 nPos, sal_uInt16 nSpace, ImplPolygon const * pInitPoly )
{
//Can't fit this in :-(, throw ?
if (mnPoints + nSpace > USHRT_MAX)
{
SAL_WARN("tools", "Polygon needs " << mnPoints + nSpace << " points, but only " << USHRT_MAX << " possible");
return false;
}
const sal_uInt16 nNewSize = mnPoints + nSpace;
const std::size_t nSpaceSize = static_cast<std::size_t>(nSpace) * sizeof(Point);
if( nPos >= mnPoints )
{
// Append at the back
nPos = mnPoints;
ImplSetSize( nNewSize );
if( pInitPoly )
{
memcpy(mxPointAry.get() + nPos, pInitPoly->mxPointAry.get(), nSpaceSize);
if (pInitPoly->mxFlagAry)
memcpy(mxFlagAry.get() + nPos, pInitPoly->mxFlagAry.get(), nSpace);
}
}
else
{
const sal_uInt16 nSecPos = nPos + nSpace;
const sal_uInt16 nRest = mnPoints - nPos;
std::unique_ptr<Point[]> xNewAry(new Point[nNewSize]);
memcpy(xNewAry.get(), mxPointAry.get(), nPos * sizeof(Point));
if( pInitPoly )
memcpy(xNewAry.get() + nPos, pInitPoly->mxPointAry.get(), nSpaceSize);
memcpy(xNewAry.get() + nSecPos, mxPointAry.get() + nPos, nRest * sizeof(Point));
mxPointAry = std::move(xNewAry);
// consider FlagArray
if (mxFlagAry)
{
std::unique_ptr<PolyFlags[]> xNewFlagAry(new PolyFlags[nNewSize]);
memcpy(xNewFlagAry.get(), mxFlagAry.get(), nPos);
if (pInitPoly && pInitPoly->mxFlagAry)
memcpy(xNewFlagAry.get() + nPos, pInitPoly->mxFlagAry.get(), nSpace);
else
memset(xNewFlagAry.get() + nPos, 0, nSpace);
memcpy(xNewFlagAry.get() + nSecPos, mxFlagAry.get() + nPos, nRest);
mxFlagAry = std::move(xNewFlagAry);
}
mnPoints = nNewSize;
}
return true;
}
void ImplPolygon::ImplCreateFlagArray()
{
if (!mxFlagAry)
{
mxFlagAry.reset(new PolyFlags[mnPoints]);
memset(mxFlagAry.get(), 0, mnPoints);
}
}
namespace {
class ImplPointFilter
{
public:
virtual void LastPoint() = 0;
virtual void Input( const Point& rPoint ) = 0;
protected:
~ImplPointFilter() {}
};
class ImplPolygonPointFilter : public ImplPointFilter
{
ImplPolygon maPoly;
sal_uInt16 mnSize;
public:
explicit ImplPolygonPointFilter(sal_uInt16 nDestSize)
: maPoly(nDestSize)
, mnSize(0)
{
}
virtual ~ImplPolygonPointFilter()
{
}
virtual void LastPoint() override;
virtual void Input( const Point& rPoint ) override;
ImplPolygon& get() { return maPoly; }
};
}
void ImplPolygonPointFilter::Input( const Point& rPoint )
{
if ( !mnSize || (rPoint != maPoly.mxPointAry[mnSize-1]) )
{
mnSize++;
if ( mnSize > maPoly.mnPoints )
maPoly.ImplSetSize( mnSize );
maPoly.mxPointAry[mnSize-1] = rPoint;
}
}
void ImplPolygonPointFilter::LastPoint()
{
if ( mnSize < maPoly.mnPoints )
maPoly.ImplSetSize( mnSize );
};
namespace {
class ImplEdgePointFilter : public ImplPointFilter
{
Point maFirstPoint;
Point maLastPoint;
ImplPointFilter& mrNextFilter;
const tools::Long mnLow;
const tools::Long mnHigh;
const int mnEdge;
int mnLastOutside;
bool mbFirst;
public:
ImplEdgePointFilter( int nEdge, tools::Long nLow, tools::Long nHigh,
ImplPointFilter& rNextFilter ) :
mrNextFilter( rNextFilter ),
mnLow( nLow ),
mnHigh( nHigh ),
mnEdge( nEdge ),
mnLastOutside( 0 ),
mbFirst( true )
{
}
virtual ~ImplEdgePointFilter() {}
Point EdgeSection( const Point& rPoint, int nEdge ) const;
int VisibleSide( const Point& rPoint ) const;
bool IsPolygon() const
{ return maFirstPoint == maLastPoint; }
virtual void Input( const Point& rPoint ) override;
virtual void LastPoint() override;
};
}
inline int ImplEdgePointFilter::VisibleSide( const Point& rPoint ) const
{
if ( mnEdge & EDGE_HORZ )
{
return rPoint.X() < mnLow ? EDGE_LEFT :
rPoint.X() > mnHigh ? EDGE_RIGHT : 0;
}
else
{
return rPoint.Y() < mnLow ? EDGE_TOP :
rPoint.Y() > mnHigh ? EDGE_BOTTOM : 0;
}
}
Point ImplEdgePointFilter::EdgeSection( const Point& rPoint, int nEdge ) const
{
tools::Long lx = maLastPoint.X();
tools::Long ly = maLastPoint.Y();
tools::Long md = rPoint.X() - lx;
tools::Long mn = rPoint.Y() - ly;
tools::Long nNewX;
tools::Long nNewY;
if ( nEdge & EDGE_VERT )
{
nNewY = (nEdge == EDGE_TOP) ? mnLow : mnHigh;
tools::Long dy = nNewY - ly;
if ( !md )
nNewX = lx;
else if ( (LONG_MAX / std::abs(md)) >= std::abs(dy) )
nNewX = (dy * md) / mn + lx;
else
{
BigInt ady = dy;
ady *= md;
if( ady.IsNeg() )
if( mn < 0 )
ady += mn/2;
else
ady -= (mn-1)/2;
else
if( mn < 0 )
ady -= (mn+1)/2;
else
ady += mn/2;
ady /= mn;
nNewX = static_cast<tools::Long>(ady) + lx;
}
}
else
{
nNewX = (nEdge == EDGE_LEFT) ? mnLow : mnHigh;
tools::Long dx = nNewX - lx;
if ( !mn )
nNewY = ly;
else if ( (LONG_MAX / std::abs(mn)) >= std::abs(dx) )
nNewY = (dx * mn) / md + ly;
else
{
BigInt adx = dx;
adx *= mn;
if( adx.IsNeg() )
if( md < 0 )
adx += md/2;
else
adx -= (md-1)/2;
else
if( md < 0 )
adx -= (md+1)/2;
else
adx += md/2;
adx /= md;
nNewY = static_cast<tools::Long>(adx) + ly;
}
}
return Point( nNewX, nNewY );
}
void ImplEdgePointFilter::Input( const Point& rPoint )
{
int nOutside = VisibleSide( rPoint );
if ( mbFirst )
{
maFirstPoint = rPoint;
mbFirst = false;
if ( !nOutside )
mrNextFilter.Input( rPoint );
}
else if ( rPoint == maLastPoint )
return;
else if ( !nOutside )
{
if ( mnLastOutside )
mrNextFilter.Input( EdgeSection( rPoint, mnLastOutside ) );
mrNextFilter.Input( rPoint );
}
else if ( !mnLastOutside )
mrNextFilter.Input( EdgeSection( rPoint, nOutside ) );
else if ( nOutside != mnLastOutside )
{
mrNextFilter.Input( EdgeSection( rPoint, mnLastOutside ) );
mrNextFilter.Input( EdgeSection( rPoint, nOutside ) );
}
maLastPoint = rPoint;
mnLastOutside = nOutside;
}
void ImplEdgePointFilter::LastPoint()
{
if ( !mbFirst )
{
int nOutside = VisibleSide( maFirstPoint );
if ( nOutside != mnLastOutside )
Input( maFirstPoint );
mrNextFilter.LastPoint();
}
}
namespace tools
{
tools::Polygon Polygon::SubdivideBezier( const tools::Polygon& rPoly )
{
tools::Polygon aPoly;
// #100127# Use adaptive subdivide instead of fixed 25 segments
rPoly.AdaptiveSubdivide( aPoly );
return aPoly;
}
Polygon::Polygon() : mpImplPolygon(ImplPolygon())
{
}
Polygon::Polygon( sal_uInt16 nSize ) : mpImplPolygon(ImplPolygon(nSize))
{
}
Polygon::Polygon( sal_uInt16 nPoints, const Point* pPtAry, const PolyFlags* pFlagAry ) : mpImplPolygon(ImplPolygon(nPoints, pPtAry, pFlagAry))
{
}
Polygon::Polygon( const tools::Polygon& rPoly ) : mpImplPolygon(rPoly.mpImplPolygon)
{
}
Polygon::Polygon( tools::Polygon&& rPoly) noexcept
: mpImplPolygon(std::move(rPoly.mpImplPolygon))
{
}
Polygon::Polygon( const tools::Rectangle& rRect ) : mpImplPolygon(ImplPolygon(rRect))
{
}
Polygon::Polygon( const tools::Rectangle& rRect, sal_uInt32 nHorzRound, sal_uInt32 nVertRound )
: mpImplPolygon(ImplPolygon(rRect, nHorzRound, nVertRound))
{
}
Polygon::Polygon( const Point& rCenter, tools::Long nRadX, tools::Long nRadY )
: mpImplPolygon(ImplPolygon(rCenter, nRadX, nRadY))
{
}
Polygon::Polygon(const tools::Rectangle& rBound, const Point& rStart, const Point& rEnd,
PolyStyle eStyle, const bool bClockWiseArcDirection)
: mpImplPolygon(ImplPolygon(rBound, rStart, rEnd, eStyle, bClockWiseArcDirection))
{
}
Polygon::Polygon( const Point& rBezPt1, const Point& rCtrlPt1,
const Point& rBezPt2, const Point& rCtrlPt2,
sal_uInt16 nPoints ) : mpImplPolygon(ImplPolygon(rBezPt1, rCtrlPt1, rBezPt2, rCtrlPt2, nPoints))
{
}
Polygon::~Polygon()
{
}
Point * Polygon::GetPointAry()
{
return mpImplPolygon->mxPointAry.get();
}
const Point* Polygon::GetConstPointAry() const
{
return mpImplPolygon->mxPointAry.get();
}
const PolyFlags* Polygon::GetConstFlagAry() const
{
return mpImplPolygon->mxFlagAry.get();
}
void Polygon::SetPoint( const Point& rPt, sal_uInt16 nPos )
{
DBG_ASSERT( nPos < mpImplPolygon->mnPoints,
"Polygon::SetPoint(): nPos >= nPoints" );
mpImplPolygon->mxPointAry[nPos] = rPt;
}
void Polygon::SetFlags( sal_uInt16 nPos, PolyFlags eFlags )
{
DBG_ASSERT( nPos < mpImplPolygon->mnPoints,
"Polygon::SetFlags(): nPos >= nPoints" );
// we do only want to create the flag array if there
// is at least one flag different to PolyFlags::Normal
if ( eFlags != PolyFlags::Normal )
{
mpImplPolygon->ImplCreateFlagArray();
mpImplPolygon->mxFlagAry[ nPos ] = eFlags;
}
}
const Point& Polygon::GetPoint( sal_uInt16 nPos ) const
{
DBG_ASSERT( nPos < mpImplPolygon->mnPoints,
"Polygon::GetPoint(): nPos >= nPoints" );
return mpImplPolygon->mxPointAry[nPos];
}
PolyFlags Polygon::GetFlags( sal_uInt16 nPos ) const
{
DBG_ASSERT( nPos < mpImplPolygon->mnPoints,
"Polygon::GetFlags(): nPos >= nPoints" );
return mpImplPolygon->mxFlagAry
? mpImplPolygon->mxFlagAry[ nPos ]
: PolyFlags::Normal;
}
bool Polygon::HasFlags() const
{
return bool(mpImplPolygon->mxFlagAry);
}
bool Polygon::IsRect() const
{
bool bIsRect = false;
if (!mpImplPolygon->mxFlagAry)
{
if ( ( ( mpImplPolygon->mnPoints == 5 ) && ( mpImplPolygon->mxPointAry[ 0 ] == mpImplPolygon->mxPointAry[ 4 ] ) ) ||
( mpImplPolygon->mnPoints == 4 ) )
{
if ( ( mpImplPolygon->mxPointAry[ 0 ].X() == mpImplPolygon->mxPointAry[ 3 ].X() ) &&
( mpImplPolygon->mxPointAry[ 0 ].Y() == mpImplPolygon->mxPointAry[ 1 ].Y() ) &&
( mpImplPolygon->mxPointAry[ 1 ].X() == mpImplPolygon->mxPointAry[ 2 ].X() ) &&
( mpImplPolygon->mxPointAry[ 2 ].Y() == mpImplPolygon->mxPointAry[ 3 ].Y() ) )
bIsRect = true;
}
}
return bIsRect;
}
void Polygon::SetSize( sal_uInt16 nNewSize )
{
if( nNewSize != mpImplPolygon->mnPoints )
{
mpImplPolygon->ImplSetSize( nNewSize );
}
}
sal_uInt16 Polygon::GetSize() const
{
return mpImplPolygon->mnPoints;
}
void Polygon::Clear()
{
mpImplPolygon = ImplType(ImplPolygon());
}
double Polygon::CalcDistance( sal_uInt16 nP1, sal_uInt16 nP2 ) const
{
DBG_ASSERT( nP1 < mpImplPolygon->mnPoints,
"Polygon::CalcDistance(): nPos1 >= nPoints" );
DBG_ASSERT( nP2 < mpImplPolygon->mnPoints,
"Polygon::CalcDistance(): nPos2 >= nPoints" );
const Point& rP1 = mpImplPolygon->mxPointAry[ nP1 ];
const Point& rP2 = mpImplPolygon->mxPointAry[ nP2 ];
const double fDx = rP2.X() - rP1.X();
const double fDy = rP2.Y() - rP1.Y();
return std::hypot( fDx, fDy );
}
void Polygon::Optimize( PolyOptimizeFlags nOptimizeFlags )
{
sal_uInt16 nSize = mpImplPolygon->mnPoints;
if( !(bool(nOptimizeFlags) && nSize) )
return;
if( nOptimizeFlags & PolyOptimizeFlags::EDGES )
{
const tools::Rectangle aBound( GetBoundRect() );
const double fArea = ( aBound.GetWidth() + aBound.GetHeight() ) * 0.5;
const sal_uInt16 nPercent = 50;
Optimize( PolyOptimizeFlags::NO_SAME );
ImplReduceEdges( *this, fArea, nPercent );
}
else if( nOptimizeFlags & PolyOptimizeFlags::NO_SAME )
{
tools::Polygon aNewPoly;
const Point& rFirst = mpImplPolygon->mxPointAry[ 0 ];
while( nSize && ( mpImplPolygon->mxPointAry[ nSize - 1 ] == rFirst ) )
nSize--;
if( nSize > 1 )
{
sal_uInt16 nLast = 0, nNewCount = 1;
aNewPoly.SetSize( nSize );
aNewPoly[ 0 ] = rFirst;
for( sal_uInt16 i = 1; i < nSize; i++ )
{
if( mpImplPolygon->mxPointAry[ i ] != mpImplPolygon->mxPointAry[ nLast ])
{
nLast = i;
aNewPoly[ nNewCount++ ] = mpImplPolygon->mxPointAry[ i ];
}
}
if( nNewCount == 1 )
aNewPoly.Clear();
else
aNewPoly.SetSize( nNewCount );
}
*this = std::move(aNewPoly);
}
nSize = mpImplPolygon->mnPoints;
if( nSize > 1 )
{
if( ( nOptimizeFlags & PolyOptimizeFlags::CLOSE ) &&
( mpImplPolygon->mxPointAry[ 0 ] != mpImplPolygon->mxPointAry[ nSize - 1 ] ) )
{
SetSize( mpImplPolygon->mnPoints + 1 );
mpImplPolygon->mxPointAry[ mpImplPolygon->mnPoints - 1 ] = mpImplPolygon->mxPointAry[ 0 ];
}
}
}
/** Recursively subdivide cubic bezier curve via deCasteljau.
@param rPoints
Output vector, where the subdivided polylines are written to.
@param d
Squared difference of curve to a straight line
@param P*
Exactly four points, interpreted as support and control points of
a cubic bezier curve. Must be in device coordinates, since stop
criterion is based on the following assumption: the device has a
finite resolution, it is thus sufficient to stop subdivision if the
curve does not deviate more than one pixel from a straight line.
*/
static void ImplAdaptiveSubdivide( std::vector<Point>& rPoints,
const double old_d2,
int recursionDepth,
const double d2,
const double P1x, const double P1y,
const double P2x, const double P2y,
const double P3x, const double P3y,
const double P4x, const double P4y )
{
// Hard limit on recursion depth, empiric number.
enum {maxRecursionDepth=128};
// Perform bezier flatness test (lecture notes from R. Schaback,
// Mathematics of Computer-Aided Design, Uni Goettingen, 2000)
// ||P(t) - L(t)|| <= max ||b_j - b_0 - j/n(b_n - b_0)||
// 0<=j<=n
// What is calculated here is an upper bound to the distance from
// a line through b_0 and b_3 (P1 and P4 in our notation) and the
// curve. We can drop 0 and n from the running indices, since the
// argument of max becomes zero for those cases.
const double fJ1x( P2x - P1x - 1.0/3.0*(P4x - P1x) );
const double fJ1y( P2y - P1y - 1.0/3.0*(P4y - P1y) );
const double fJ2x( P3x - P1x - 2.0/3.0*(P4x - P1x) );
const double fJ2y( P3y - P1y - 2.0/3.0*(P4y - P1y) );
const double distance2( ::std::max( fJ1x*fJ1x + fJ1y*fJ1y,
fJ2x*fJ2x + fJ2y*fJ2y) );
// stop if error measure does not improve anymore. This is a
// safety guard against floating point inaccuracies.
// stop at recursion level 128. This is a safety guard against
// floating point inaccuracies.
// stop if distance from line is guaranteed to be bounded by d
if( old_d2 > d2 &&
recursionDepth < maxRecursionDepth &&
distance2 >= d2 &&
rPoints.size() < SAL_MAX_UINT16 )
{
// deCasteljau bezier arc, split at t=0.5
// Foley/vanDam, p. 508
const double L1x( P1x ), L1y( P1y );
const double L2x( (P1x + P2x)*0.5 ), L2y( (P1y + P2y)*0.5 );
const double Hx ( (P2x + P3x)*0.5 ), Hy ( (P2y + P3y)*0.5 );
const double L3x( (L2x + Hx)*0.5 ), L3y( (L2y + Hy)*0.5 );
const double R4x( P4x ), R4y( P4y );
const double R3x( (P3x + P4x)*0.5 ), R3y( (P3y + P4y)*0.5 );
const double R2x( (Hx + R3x)*0.5 ), R2y( (Hy + R3y)*0.5 );
const double R1x( (L3x + R2x)*0.5 ), R1y( (L3y + R2y)*0.5 );
const double L4x( R1x ), L4y( R1y );
// subdivide further
++recursionDepth;
ImplAdaptiveSubdivide(rPoints, distance2, recursionDepth, d2, L1x, L1y, L2x, L2y, L3x, L3y, L4x, L4y);
ImplAdaptiveSubdivide(rPoints, distance2, recursionDepth, d2, R1x, R1y, R2x, R2y, R3x, R3y, R4x, R4y);
}
else
{
// requested resolution reached.
// Add end points to output iterator.
// order is preserved, since this is so to say depth first traversal.
rPoints.push_back(Point(basegfx::fround<tools::Long>(P1x), basegfx::fround<tools::Long>(P1y)));
}
}
void Polygon::AdaptiveSubdivide( Polygon& rResult, const double d ) const
{
if (!mpImplPolygon->mxFlagAry)
{
rResult = *this;
}
else
{
sal_uInt16 i;
sal_uInt16 nPts( GetSize() );
::std::vector< Point > aPoints;
aPoints.reserve( nPts );
for(i=0; i<nPts;)
{
if( ( i + 3 ) < nPts )
{
PolyFlags P1( mpImplPolygon->mxFlagAry[ i ] );
PolyFlags P4( mpImplPolygon->mxFlagAry[ i + 3 ] );
if( ( PolyFlags::Normal == P1 || PolyFlags::Smooth == P1 || PolyFlags::Symmetric == P1 ) &&
( PolyFlags::Control == mpImplPolygon->mxFlagAry[ i + 1 ] ) &&
( PolyFlags::Control == mpImplPolygon->mxFlagAry[ i + 2 ] ) &&
( PolyFlags::Normal == P4 || PolyFlags::Smooth == P4 || PolyFlags::Symmetric == P4 ) )
{
ImplAdaptiveSubdivide( aPoints, d*d+1.0, 0, d*d,
mpImplPolygon->mxPointAry[ i ].X(), mpImplPolygon->mxPointAry[ i ].Y(),
mpImplPolygon->mxPointAry[ i+1 ].X(), mpImplPolygon->mxPointAry[ i+1 ].Y(),
mpImplPolygon->mxPointAry[ i+2 ].X(), mpImplPolygon->mxPointAry[ i+2 ].Y(),
mpImplPolygon->mxPointAry[ i+3 ].X(), mpImplPolygon->mxPointAry[ i+3 ].Y() );
i += 3;
continue;
}
}
aPoints.push_back(mpImplPolygon->mxPointAry[i++]);
if (aPoints.size() >= SAL_MAX_UINT16)
{
OSL_ENSURE(aPoints.size() < SAL_MAX_UINT16,
"Polygon::AdaptiveSubdivision created polygon too many points;"
" using original polygon instead");
// The resulting polygon can not hold all the points
// that we have created so far. Stop the subdivision
// and return a copy of the unmodified polygon.
rResult = *this;
return;
}
}
// fill result polygon
rResult = tools::Polygon( static_cast<sal_uInt16>(aPoints.size()) ); // ensure sufficient size for copy
::std::copy(aPoints.begin(), aPoints.end(), rResult.mpImplPolygon->mxPointAry.get());
}
}
namespace {
class Vector2D
{
private:
double mfX;
double mfY;
public:
explicit Vector2D( const Point& rPoint ) : mfX( rPoint.X() ), mfY( rPoint.Y() ) {};
double GetLength() const { return hypot( mfX, mfY ); }
Vector2D& operator-=( const Vector2D& rVec ) { mfX -= rVec.mfX; mfY -= rVec.mfY; return *this; }
double Scalar( const Vector2D& rVec ) const { return mfX * rVec.mfX + mfY * rVec.mfY ; }
Vector2D& Normalize();
bool IsPositive( Vector2D const & rVec ) const { return ( mfX * rVec.mfY - mfY * rVec.mfX ) >= 0.0; }
bool IsNegative( Vector2D const & rVec ) const { return !IsPositive( rVec ); }
};
}
Vector2D& Vector2D::Normalize()
{
double fLen = Scalar( *this );
if( ( fLen != 0.0 ) && ( fLen != 1.0 ) )
{
fLen = sqrt( fLen );
if( fLen != 0.0 )
{
mfX /= fLen;
mfY /= fLen;
}
}
return *this;
}
void Polygon::ImplReduceEdges( tools::Polygon& rPoly, const double& rArea, sal_uInt16 nPercent )
{
const double fBound = 2000.0 * ( 100 - nPercent ) * 0.01;
sal_uInt16 nNumNoChange = 0,
nNumRuns = 0;
while( nNumNoChange < 2 )
{
sal_uInt16 nPntCnt = rPoly.GetSize(), nNewPos = 0;
tools::Polygon aNewPoly( nPntCnt );
bool bChangeInThisRun = false;
for( sal_uInt16 n = 0; n < nPntCnt; n++ )
{
bool bDeletePoint = false;
if( ( n + nNumRuns ) % 2 )
{
sal_uInt16 nIndPrev = !n ? nPntCnt - 1 : n - 1;
sal_uInt16 nIndPrevPrev = !nIndPrev ? nPntCnt - 1 : nIndPrev - 1;
sal_uInt16 nIndNext = ( n == nPntCnt-1 ) ? 0 : n + 1;
sal_uInt16 nIndNextNext = ( nIndNext == nPntCnt - 1 ) ? 0 : nIndNext + 1;
Vector2D aVec1( rPoly[ nIndPrev ] ); aVec1 -= Vector2D(rPoly[ nIndPrevPrev ]);
Vector2D aVec2( rPoly[ n ] ); aVec2 -= Vector2D(rPoly[ nIndPrev ]);
Vector2D aVec3( rPoly[ nIndNext ] ); aVec3 -= Vector2D(rPoly[ n ]);
Vector2D aVec4( rPoly[ nIndNextNext ] ); aVec4 -= Vector2D(rPoly[ nIndNext ]);
double fDist1 = aVec1.GetLength(), fDist2 = aVec2.GetLength();
double fDist3 = aVec3.GetLength(), fDist4 = aVec4.GetLength();
double fTurnB = aVec2.Normalize().Scalar( aVec3.Normalize() );
if( fabs( fTurnB ) < ( 1.0 + SMALL_DVALUE ) && fabs( fTurnB ) > ( 1.0 - SMALL_DVALUE ) )
bDeletePoint = true;
else
{
Vector2D aVecB( rPoly[ nIndNext ] );
aVecB -= Vector2D(rPoly[ nIndPrev ] );
double fDistB = aVecB.GetLength();
double fLenWithB = fDist2 + fDist3;
double fLenFact = ( fDistB != 0.0 ) ? fLenWithB / fDistB : 1.0;
double fTurnPrev = aVec1.Normalize().Scalar( aVec2 );
double fTurnNext = aVec3.Scalar( aVec4.Normalize() );
double fGradPrev, fGradB, fGradNext;
if( fabs( fTurnPrev ) < ( 1.0 + SMALL_DVALUE ) && fabs( fTurnPrev ) > ( 1.0 - SMALL_DVALUE ) )
fGradPrev = 0.0;
else
fGradPrev = basegfx::rad2deg(acos(fTurnPrev)) * (aVec1.IsNegative(aVec2) ? -1 : 1);
fGradB = basegfx::rad2deg(acos(fTurnB)) * (aVec2.IsNegative(aVec3) ? -1 : 1);
if( fabs( fTurnNext ) < ( 1.0 + SMALL_DVALUE ) && fabs( fTurnNext ) > ( 1.0 - SMALL_DVALUE ) )
fGradNext = 0.0;
else
fGradNext = basegfx::rad2deg(acos(fTurnNext)) * (aVec3.IsNegative(aVec4) ? -1 : 1);
if( ( fGradPrev > 0.0 && fGradB < 0.0 && fGradNext > 0.0 ) ||
( fGradPrev < 0.0 && fGradB > 0.0 && fGradNext < 0.0 ) )
{
if( ( fLenFact < ( FSQRT2 + SMALL_DVALUE ) ) &&
( ( ( fDist1 + fDist4 ) / ( fDist2 + fDist3 ) ) * 2000.0 ) > fBound )
{
bDeletePoint = true;
}
}
else
{
double fRelLen = 1.0 - sqrt( fDistB / rArea );
if( fRelLen < 0.0 )
fRelLen = 0.0;
else if( fRelLen > 1.0 )
fRelLen = 1.0;
if( ( std::round( ( fLenFact - 1.0 ) * 1000000.0 ) < fBound ) &&
( fabs( fGradB ) <= ( fRelLen * fBound * 0.01 ) ) )
{
bDeletePoint = true;
}
}
}
}
if( !bDeletePoint )
aNewPoly[ nNewPos++ ] = rPoly[ n ];
else
bChangeInThisRun = true;
}
if( bChangeInThisRun && nNewPos )
{
aNewPoly.SetSize( nNewPos );
rPoly = std::move(aNewPoly);
nNumNoChange = 0;
}
else
nNumNoChange++;
nNumRuns++;
}
}
void Polygon::Move( tools::Long nHorzMove, tools::Long nVertMove )
{
// This check is required for DrawEngine
if ( !nHorzMove && !nVertMove )
return;
// Move points
sal_uInt16 nCount = mpImplPolygon->mnPoints;
for ( sal_uInt16 i = 0; i < nCount; i++ )
{
Point& rPt = mpImplPolygon->mxPointAry[i];
rPt.AdjustX(nHorzMove );
rPt.AdjustY(nVertMove );
}
}
void Polygon::Translate(const Point& rTrans)
{
for ( sal_uInt16 i = 0, nCount = mpImplPolygon->mnPoints; i < nCount; i++ )
mpImplPolygon->mxPointAry[ i ] += rTrans;
}
void Polygon::Scale( double fScaleX, double fScaleY )
{
for ( sal_uInt16 i = 0, nCount = mpImplPolygon->mnPoints; i < nCount; i++ )
{
Point& rPnt = mpImplPolygon->mxPointAry[i];
rPnt.setX( static_cast<tools::Long>( fScaleX * rPnt.X() ) );
rPnt.setY( static_cast<tools::Long>( fScaleY * rPnt.Y() ) );
}
}
void Polygon::Rotate( const Point& rCenter, Degree10 nAngle10 )
{
nAngle10 %= 3600_deg10;
if( nAngle10 )
{
const double fAngle = toRadians(nAngle10);
Rotate( rCenter, sin( fAngle ), cos( fAngle ) );
}
}
void Polygon::Rotate( const Point& rCenter, double fSin, double fCos )
{
tools::Long nCenterX = rCenter.X();
tools::Long nCenterY = rCenter.Y();
for( sal_uInt16 i = 0, nCount = mpImplPolygon->mnPoints; i < nCount; i++ )
{
Point& rPt = mpImplPolygon->mxPointAry[ i ];
const tools::Long nX = rPt.X() - nCenterX;
const tools::Long nY = rPt.Y() - nCenterY;
rPt.setX(basegfx::fround<tools::Long>(fCos * nX + fSin * nY + nCenterX));
rPt.setY(basegfx::fround<tools::Long>(-(fSin * nX - fCos * nY - nCenterY)));
}
}
void Polygon::Clip( const tools::Rectangle& rRect )
{
// This algorithm is broken for bezier curves, they would get converted to lines.
// Use PolyPolygon::Clip().
assert( !HasFlags());
// #105251# Normalize rect before edge filtering
tools::Rectangle aJustifiedRect( rRect );
aJustifiedRect.Normalize();
sal_uInt16 nSourceSize = mpImplPolygon->mnPoints;
ImplPolygonPointFilter aPolygon( nSourceSize );
ImplEdgePointFilter aHorzFilter( EDGE_HORZ, aJustifiedRect.Left(), aJustifiedRect.Right(),
aPolygon );
ImplEdgePointFilter aVertFilter( EDGE_VERT, aJustifiedRect.Top(), aJustifiedRect.Bottom(),
aHorzFilter );
for ( sal_uInt16 i = 0; i < nSourceSize; i++ )
aVertFilter.Input( mpImplPolygon->mxPointAry[i] );
if ( aVertFilter.IsPolygon() )
aVertFilter.LastPoint();
else
aPolygon.LastPoint();
mpImplPolygon = ImplType(aPolygon.get());
}
tools::Rectangle Polygon::GetBoundRect() const
{
// Removing the assert. Bezier curves have the attribute that each single
// curve segment defined by four points can not exit the four-point polygon
// defined by that points. This allows to say that the curve segment can also
// never leave the Range of its defining points.
// The result is that Polygon::GetBoundRect() may not create the minimal
// BoundRect of the Polygon (to get that, use basegfx::B2DPolygon classes),
// but will always create a valid BoundRect, at least as long as this method
// 'blindly' travels over all points, including control points.
// DBG_ASSERT( !mpImplPolygon->mxFlagAry.get(), "GetBoundRect could fail with beziers!" );
sal_uInt16 nCount = mpImplPolygon->mnPoints;
if( ! nCount )
return tools::Rectangle();
tools::Long nXMin, nXMax, nYMin, nYMax;
const Point& pFirstPt = mpImplPolygon->mxPointAry[0];
nXMin = nXMax = pFirstPt.X();
nYMin = nYMax = pFirstPt.Y();
for ( sal_uInt16 i = 0; i < nCount; i++ )
{
const Point& rPt = mpImplPolygon->mxPointAry[i];
if (rPt.X() < nXMin)
nXMin = rPt.X();
if (rPt.X() > nXMax)
nXMax = rPt.X();
if (rPt.Y() < nYMin)
nYMin = rPt.Y();
if (rPt.Y() > nYMax)
nYMax = rPt.Y();
}
return tools::Rectangle( nXMin, nYMin, nXMax, nYMax );
}
bool Polygon::Contains( const Point& rPoint ) const
{
DBG_ASSERT( !mpImplPolygon->mxFlagAry, "IsInside could fail with beziers!" );
const tools::Rectangle aBound( GetBoundRect() );
const Line aLine( rPoint, Point( aBound.Right() + 100, rPoint.Y() ) );
sal_uInt16 nCount = mpImplPolygon->mnPoints;
sal_uInt16 nPCounter = 0;
if ( ( nCount > 2 ) && aBound.Contains( rPoint ) )
{
Point aPt1( mpImplPolygon->mxPointAry[ 0 ] );
Point aIntersection;
Point aLastIntersection;
while ( ( aPt1 == mpImplPolygon->mxPointAry[ nCount - 1 ] ) && ( nCount > 3 ) )
nCount--;
for ( sal_uInt16 i = 1; i <= nCount; i++ )
{
const Point& rPt2 = mpImplPolygon->mxPointAry[ ( i < nCount ) ? i : 0 ];
if ( aLine.Intersection( Line( aPt1, rPt2 ), aIntersection ) )
{
// This avoids insertion of double intersections
if ( nPCounter )
{
if ( aIntersection != aLastIntersection )
{
aLastIntersection = aIntersection;
nPCounter++;
}
}
else
{
aLastIntersection = aIntersection;
nPCounter++;
}
}
aPt1 = rPt2;
}
}
// is inside, if number of intersection points is odd
return ( ( nPCounter & 1 ) == 1 );
}
void Polygon::Insert( sal_uInt16 nPos, const Point& rPt )
{
if( nPos >= mpImplPolygon->mnPoints )
nPos = mpImplPolygon->mnPoints;
if (mpImplPolygon->ImplSplit(nPos, 1))
mpImplPolygon->mxPointAry[ nPos ] = rPt;
}
void Polygon::Insert( sal_uInt16 nPos, const tools::Polygon& rPoly )
{
const sal_uInt16 nInsertCount = rPoly.mpImplPolygon->mnPoints;
if( nInsertCount )
{
if( nPos >= mpImplPolygon->mnPoints )
nPos = mpImplPolygon->mnPoints;
if (rPoly.mpImplPolygon->mxFlagAry)
mpImplPolygon->ImplCreateFlagArray();
mpImplPolygon->ImplSplit( nPos, nInsertCount, rPoly.mpImplPolygon.get() );
}
}
Point& Polygon::operator[]( sal_uInt16 nPos )
{
assert( nPos < mpImplPolygon->mnPoints );
return mpImplPolygon->mxPointAry[nPos];
}
tools::Polygon& Polygon::operator=( const tools::Polygon& rPoly )
{
mpImplPolygon = rPoly.mpImplPolygon;
return *this;
}
tools::Polygon& Polygon::operator=( tools::Polygon&& rPoly ) noexcept
{
mpImplPolygon = std::move(rPoly.mpImplPolygon);
return *this;
}
bool Polygon::operator==( const tools::Polygon& rPoly ) const
{
return (mpImplPolygon == rPoly.mpImplPolygon);
}
bool Polygon::IsEqual( const tools::Polygon& rPoly ) const
{
bool bIsEqual = true;
sal_uInt16 i;
if ( GetSize() != rPoly.GetSize() )
bIsEqual = false;
else
{
for ( i = 0; i < GetSize(); i++ )
{
if ( ( GetPoint( i ) != rPoly.GetPoint( i ) ) ||
( GetFlags( i ) != rPoly.GetFlags( i ) ) )
{
bIsEqual = false;
break;
}
}
}
return bIsEqual;
}
SvStream& ReadPolygon( SvStream& rIStream, tools::Polygon& rPoly )
{
sal_uInt16 nPoints(0);
// read all points and create array
rIStream.ReadUInt16( nPoints );
const size_t nMaxRecordsPossible = rIStream.remainingSize() / (2 * sizeof(sal_Int32));
if (nPoints > nMaxRecordsPossible)
{
SAL_WARN("tools", "Polygon claims " << nPoints << " records, but only " << nMaxRecordsPossible << " possible");
nPoints = nMaxRecordsPossible;
}
rPoly.mpImplPolygon->ImplSetSize( nPoints, false );
for (sal_uInt16 i = 0; i < nPoints; i++)
{
sal_Int32 nTmpX(0), nTmpY(0);
rIStream.ReadInt32(nTmpX).ReadInt32(nTmpY);
rPoly.mpImplPolygon->mxPointAry[i].setX(nTmpX);
rPoly.mpImplPolygon->mxPointAry[i].setY(nTmpY);
}
return rIStream;
}
SvStream& WritePolygon( SvStream& rOStream, const tools::Polygon& rPoly )
{
sal_uInt16 nPoints = rPoly.GetSize();
// Write number of points
rOStream.WriteUInt16( nPoints );
for (sal_uInt16 i = 0; i < nPoints; i++)
{
rOStream.WriteInt32(rPoly.mpImplPolygon->mxPointAry[i].X())
.WriteInt32(rPoly.mpImplPolygon->mxPointAry[i].Y());
}
return rOStream;
}
void Polygon::ImplRead( SvStream& rIStream )
{
sal_uInt8 bHasPolyFlags(0);
ReadPolygon( rIStream, *this );
rIStream.ReadUChar( bHasPolyFlags );
if ( bHasPolyFlags )
{
mpImplPolygon->mxFlagAry.reset(new PolyFlags[mpImplPolygon->mnPoints]);
auto nRead = rIStream.ReadBytes(mpImplPolygon->mxFlagAry.get(), mpImplPolygon->mnPoints);
if (nRead != mpImplPolygon->mnPoints)
{
SAL_WARN("tools", "Short read");
memset(mpImplPolygon->mxFlagAry.get() + nRead, 0, mpImplPolygon->mnPoints - nRead);
}
}
}
void Polygon::Read( SvStream& rIStream )
{
VersionCompatRead aCompat(rIStream);
ImplRead( rIStream );
}
void Polygon::ImplWrite( SvStream& rOStream ) const
{
bool bHasPolyFlags(mpImplPolygon->mxFlagAry);
WritePolygon( rOStream, *this );
rOStream.WriteBool(bHasPolyFlags);
if ( bHasPolyFlags )
rOStream.WriteBytes(mpImplPolygon->mxFlagAry.get(), mpImplPolygon->mnPoints);
}
void Polygon::Write( SvStream& rOStream ) const
{
VersionCompatWrite aCompat(rOStream, 1);
ImplWrite( rOStream );
}
// #i74631#/#i115917# numerical correction method for B2DPolygon
static void impCorrectContinuity(basegfx::B2DPolygon& roPolygon, sal_uInt32 nIndex, PolyFlags nCFlag)
{
const sal_uInt32 nPointCount(roPolygon.count());
OSL_ENSURE(nIndex < nPointCount, "impCorrectContinuity: index access out of range (!)");
if(nIndex >= nPointCount || (PolyFlags::Smooth != nCFlag && PolyFlags::Symmetric != nCFlag))
return;
if(!roPolygon.isPrevControlPointUsed(nIndex) || !roPolygon.isNextControlPointUsed(nIndex))
return;
// #i115917# Patch from osnola (modified, thanks for showing the problem)
// The correction is needed because an integer polygon with control points
// is converted to double precision. When C1 or C2 is used the involved vectors
// may not have the same directions/lengths since these come from integer coordinates
// and may have been snapped to different nearest integer coordinates. The snap error
// is in the range of +-1 in y and y, thus 0.0 <= error <= sqrt(2.0). Nonetheless,
// it needs to be corrected to be able to detect the continuity in this points
// correctly.
// We only have the integer data here (already in double precision form, but no mantissa
// used), so the best correction is to use:
// for C1: The longest vector since it potentially has best preserved the original vector.
// Even better the sum of the vectors, weighted by their length. This gives the
// normal vector addition to get the vector itself, lengths need to be preserved.
// for C2: The mediated vector(s) since both should be the same, but mirrored
// extract the point and vectors
const basegfx::B2DPoint aPoint(roPolygon.getB2DPoint(nIndex));
const basegfx::B2DVector aNext(roPolygon.getNextControlPoint(nIndex) - aPoint);
const basegfx::B2DVector aPrev(aPoint - roPolygon.getPrevControlPoint(nIndex));
// calculate common direction vector, normalize
const basegfx::B2DVector aDirection(aNext + aPrev);
const double fDirectionLen = aDirection.getLength();
if (fDirectionLen == 0.0)
return;
if (PolyFlags::Smooth == nCFlag)
{
// C1: apply common direction vector, preserve individual lengths
const double fInvDirectionLen(1.0 / fDirectionLen);
roPolygon.setNextControlPoint(nIndex, basegfx::B2DPoint(aPoint + (aDirection * (aNext.getLength() * fInvDirectionLen))));
roPolygon.setPrevControlPoint(nIndex, basegfx::B2DPoint(aPoint - (aDirection * (aPrev.getLength() * fInvDirectionLen))));
}
else // PolyFlags::Symmetric
{
// C2: get mediated length. Taking half of the unnormalized direction would be
// an approximation, but not correct.
const double fMedLength((aNext.getLength() + aPrev.getLength()) * (0.5 / fDirectionLen));
const basegfx::B2DVector aScaledDirection(aDirection * fMedLength);
// Bring Direction to correct length and apply
roPolygon.setNextControlPoint(nIndex, basegfx::B2DPoint(aPoint + aScaledDirection));
roPolygon.setPrevControlPoint(nIndex, basegfx::B2DPoint(aPoint - aScaledDirection));
}
}
// convert to basegfx::B2DPolygon and return
basegfx::B2DPolygon Polygon::getB2DPolygon() const
{
basegfx::B2DPolygon aRetval;
const sal_uInt16 nCount(mpImplPolygon->mnPoints);
if (nCount)
{
if (mpImplPolygon->mxFlagAry)
{
// handling for curves. Add start point
const Point aStartPoint(mpImplPolygon->mxPointAry[0]);
PolyFlags nPointFlag(mpImplPolygon->mxFlagAry[0]);
aRetval.append(basegfx::B2DPoint(aStartPoint.X(), aStartPoint.Y()));
Point aControlA, aControlB;
for(sal_uInt16 a(1); a < nCount;)
{
bool bControlA(false);
bool bControlB(false);
if(PolyFlags::Control == mpImplPolygon->mxFlagAry[a])
{
aControlA = mpImplPolygon->mxPointAry[a++];
bControlA = true;
}
if(a < nCount && PolyFlags::Control == mpImplPolygon->mxFlagAry[a])
{
aControlB = mpImplPolygon->mxPointAry[a++];
bControlB = true;
}
// assert invalid polygons
OSL_ENSURE(bControlA == bControlB, "Polygon::getB2DPolygon: Invalid source polygon (!)");
if(a < nCount)
{
const Point aEndPoint(mpImplPolygon->mxPointAry[a]);
if(bControlA)
{
// bezier edge, add
aRetval.appendBezierSegment(
basegfx::B2DPoint(aControlA.X(), aControlA.Y()),
basegfx::B2DPoint(aControlB.X(), aControlB.Y()),
basegfx::B2DPoint(aEndPoint.X(), aEndPoint.Y()));
impCorrectContinuity(aRetval, aRetval.count() - 2, nPointFlag);
}
else
{
// no bezier edge, add end point
aRetval.append(basegfx::B2DPoint(aEndPoint.X(), aEndPoint.Y()));
}
nPointFlag = mpImplPolygon->mxFlagAry[a++];
}
}
// if exist, remove double first/last points, set closed and correct control points
basegfx::utils::checkClosed(aRetval);
if(aRetval.isClosed())
{
// closeWithGeometryChange did really close, so last point(s) were removed.
// Correct the continuity in the changed point
impCorrectContinuity(aRetval, 0, mpImplPolygon->mxFlagAry[0]);
}
}
else
{
// extra handling for non-curves (most-used case) for speedup
for(sal_uInt16 a(0); a < nCount; a++)
{
// get point and add
const Point aPoint(mpImplPolygon->mxPointAry[a]);
aRetval.append(basegfx::B2DPoint(aPoint.X(), aPoint.Y()));
}
// set closed flag
basegfx::utils::checkClosed(aRetval);
}
}
return aRetval;
}
Polygon::Polygon(const basegfx::B2DPolygon& rPolygon) : mpImplPolygon(ImplPolygon(rPolygon))
{
}
} // namespace tools
/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
↑ V547 Expression 'aPoints.size() < ((sal_uInt16) 0xFFFF)' is always false.
↑ V1077 The 'ImplPolygon' constructor contains potentially uninitialized members. Inspect the following: mnPoints.
↑ V1077 The 'ImplPolygon' constructor contains potentially uninitialized members. Inspect the following: mnPoints.