1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 /*
3 * This file is part of the LibreOffice project.
4 *
5 * This Source Code Form is subject to the terms of the Mozilla Public
6 * License, v. 2.0. If a copy of the MPL was not distributed with this
7 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
8 *
9 * This file incorporates work covered by the following license notice:
10 *
11 * Licensed to the Apache Software Foundation (ASF) under one or more
12 * contributor license agreements. See the NOTICE file distributed
13 * with this work for additional information regarding copyright
14 * ownership. The ASF licenses this file to you under the Apache
15 * License, Version 2.0 (the "License"); you may not use this file
16 * except in compliance with the License. You may obtain a copy of
17 * the License at http://www.apache.org/licenses/LICENSE-2.0 .
18 */
19
20 #include <osl/endian.h>
21 #include <osl/diagnose.h>
22 #include <sal/log.hxx>
23 #include <tools/bigint.hxx>
24 #include <tools/debug.hxx>
25 #include <tools/helpers.hxx>
26 #include <tools/stream.hxx>
27 #include <tools/vcompat.hxx>
28 #include <tools/gen.hxx>
29 #include <poly.h>
30 #include <o3tl/safeint.hxx>
31 #include <tools/line.hxx>
32 #include <tools/poly.hxx>
33 #include <basegfx/polygon/b2dpolygon.hxx>
34 #include <basegfx/point/b2dpoint.hxx>
35 #include <basegfx/vector/b2dvector.hxx>
36 #include <basegfx/polygon/b2dpolygontools.hxx>
37 #include <basegfx/curve/b2dcubicbezier.hxx>
38
39 #include <memory>
40 #include <vector>
41 #include <iterator>
42 #include <algorithm>
43 #include <cstdlib>
44 #include <cstring>
45 #include <limits.h>
46 #include <cmath>
47
48 #define EDGE_LEFT 1
49 #define EDGE_TOP 2
50 #define EDGE_RIGHT 4
51 #define EDGE_BOTTOM 8
52 #define EDGE_HORZ (EDGE_RIGHT | EDGE_LEFT)
53 #define EDGE_VERT (EDGE_TOP | EDGE_BOTTOM)
54 #define SMALL_DVALUE 0.0000001
55 #define FSQRT2 1.4142135623730950488016887242097
56
ImplGetParameter(const Point & rCenter,const Point & rPt,double fWR,double fHR)57 static double ImplGetParameter( const Point& rCenter, const Point& rPt, double fWR, double fHR )
58 {
59 const tools::Long nDX = rPt.X() - rCenter.X();
60 double fAngle = atan2( o3tl::saturating_toggle_sign(rPt.Y()) + rCenter.Y(), ( ( nDX == 0 ) ? 0.000000001 : nDX ) );
61
62 return atan2(fWR*sin(fAngle), fHR*cos(fAngle));
63 }
64
ImplPolygon(sal_uInt16 nInitSize)65 ImplPolygon::ImplPolygon( sal_uInt16 nInitSize )
66 {
67 ImplInitSize(nInitSize, false);
68 }
69
ImplPolygon(const ImplPolygon & rImpPoly)70 ImplPolygon::ImplPolygon( const ImplPolygon& rImpPoly )
71 {
72 if ( rImpPoly.mnPoints )
73 {
74 mxPointAry.reset(new Point[rImpPoly.mnPoints]);
75 memcpy(mxPointAry.get(), rImpPoly.mxPointAry.get(), rImpPoly.mnPoints * sizeof(Point));
76
77 if( rImpPoly.mxFlagAry )
78 {
79 mxFlagAry.reset(new PolyFlags[rImpPoly.mnPoints]);
80 memcpy(mxFlagAry.get(), rImpPoly.mxFlagAry.get(), rImpPoly.mnPoints);
81 }
82 }
83
84 mnPoints = rImpPoly.mnPoints;
85 }
86
ImplPolygon(sal_uInt16 nInitSize,const Point * pInitAry,const PolyFlags * pInitFlags)87 ImplPolygon::ImplPolygon( sal_uInt16 nInitSize, const Point* pInitAry, const PolyFlags* pInitFlags )
88 {
89 if ( nInitSize )
90 {
91 mxPointAry.reset(new Point[nInitSize]);
92 memcpy(mxPointAry.get(), pInitAry, nInitSize * sizeof(Point));
93
94 if( pInitFlags )
95 {
96 mxFlagAry.reset(new PolyFlags[nInitSize]);
97 memcpy(mxFlagAry.get(), pInitFlags, nInitSize);
98 }
99 }
100
101 mnPoints = nInitSize;
102 }
103
ImplPolygon(const tools::Rectangle & rRect)104 ImplPolygon::ImplPolygon( const tools::Rectangle& rRect )
105 {
106 if ( !rRect.IsEmpty() )
107 {
108 ImplInitSize(5);
109 mxPointAry[0] = rRect.TopLeft();
110 mxPointAry[1] = rRect.TopRight();
111 mxPointAry[2] = rRect.BottomRight();
112 mxPointAry[3] = rRect.BottomLeft();
113 mxPointAry[4] = rRect.TopLeft();
114 }
115 else
116 mnPoints = 0;
117 }
118
ImplPolygon(const tools::Rectangle & rRect,sal_uInt32 nHorzRound,sal_uInt32 nVertRound)119 ImplPolygon::ImplPolygon( const tools::Rectangle& rRect, sal_uInt32 nHorzRound, sal_uInt32 nVertRound )
120 {
121 if ( !rRect.IsEmpty() )
122 {
123 tools::Rectangle aRect( rRect );
124 aRect.Justify(); // SJ: i9140
125
126 nHorzRound = std::min( nHorzRound, static_cast<sal_uInt32>(std::abs( aRect.GetWidth() >> 1 )) );
127 nVertRound = std::min( nVertRound, static_cast<sal_uInt32>(std::abs( aRect.GetHeight() >> 1 )) );
128
129 if( !nHorzRound && !nVertRound )
130 {
131 ImplInitSize(5);
132 mxPointAry[0] = aRect.TopLeft();
133 mxPointAry[1] = aRect.TopRight();
134 mxPointAry[2] = aRect.BottomRight();
135 mxPointAry[3] = aRect.BottomLeft();
136 mxPointAry[4] = aRect.TopLeft();
137 }
138 else
139 {
140 const Point aTL( aRect.Left() + nHorzRound, aRect.Top() + nVertRound );
141 const Point aTR( aRect.Right() - nHorzRound, aRect.Top() + nVertRound );
142 const Point aBR( aRect.Right() - nHorzRound, aRect.Bottom() - nVertRound );
143 const Point aBL( aRect.Left() + nHorzRound, aRect.Bottom() - nVertRound );
144 tools::Polygon aEllipsePoly( Point(), nHorzRound, nVertRound );
145 sal_uInt16 i, nEnd, nSize4 = aEllipsePoly.GetSize() >> 2;
146
147 ImplInitSize(aEllipsePoly.GetSize() + 1);
148
149 const Point* pSrcAry = aEllipsePoly.GetConstPointAry();
150 Point* pDstAry = mxPointAry.get();
151
152 for( i = 0, nEnd = nSize4; i < nEnd; i++ )
153 pDstAry[ i ] = pSrcAry[ i ] + aTR;
154
155 for( nEnd = nEnd + nSize4; i < nEnd; i++ )
156 pDstAry[ i ] = pSrcAry[ i ] + aTL;
157
158 for( nEnd = nEnd + nSize4; i < nEnd; i++ )
159 pDstAry[ i ] = pSrcAry[ i ] + aBL;
160
161 for( nEnd = nEnd + nSize4; i < nEnd; i++ )
162 pDstAry[ i ] = pSrcAry[ i ] + aBR;
163
164 pDstAry[ nEnd ] = pDstAry[ 0 ];
165 }
166 }
167 else
168 mnPoints = 0;
169 }
170
ImplPolygon(const Point & rCenter,tools::Long nRadX,tools::Long nRadY)171 ImplPolygon::ImplPolygon( const Point& rCenter, tools::Long nRadX, tools::Long nRadY )
172 {
173 if( nRadX && nRadY )
174 {
175 sal_uInt16 nPoints;
176 // Compute default (depends on size)
177 tools::Long nRadXY;
178 const bool bOverflow = o3tl::checked_multiply(nRadX, nRadY, nRadXY);
179 if (!bOverflow)
180 {
181 nPoints = static_cast<sal_uInt16>(MinMax(
182 ( F_PI * ( 1.5 * ( nRadX + nRadY ) -
183 sqrt( static_cast<double>(std::abs(nRadXY)) ) ) ),
184 32, 256 ));
185 }
186 else
187 {
188 nPoints = 256;
189 }
190
191 if( ( nRadX > 32 ) && ( nRadY > 32 ) && ( nRadX + nRadY ) < 8192 )
192 nPoints >>= 1;
193
194 // Ceil number of points until divisible by four
195 nPoints = (nPoints + 3) & ~3;
196 ImplInitSize(nPoints);
197
198 sal_uInt16 i;
199 sal_uInt16 nPoints2 = nPoints >> 1;
200 sal_uInt16 nPoints4 = nPoints >> 2;
201 double nAngle;
202 double nAngleStep = F_PI2 / ( nPoints4 - 1 );
203
204 for( i=0, nAngle = 0.0; i < nPoints4; i++, nAngle += nAngleStep )
205 {
206 tools::Long nX = FRound( nRadX * cos( nAngle ) );
207 tools::Long nY = FRound( -nRadY * sin( nAngle ) );
208
209 Point* pPt = &(mxPointAry[i]);
210 pPt->setX( nX + rCenter.X() );
211 pPt->setY( nY + rCenter.Y() );
212 pPt = &(mxPointAry[nPoints2-i-1]);
213 pPt->setX( -nX + rCenter.X() );
214 pPt->setY( nY + rCenter.Y() );
215 pPt = &(mxPointAry[i+nPoints2]);
216 pPt->setX( -nX + rCenter.X() );
217 pPt->setY( -nY + rCenter.Y() );
218 pPt = &(mxPointAry[nPoints-i-1]);
219 pPt->setX( nX + rCenter.X() );
220 pPt->setY( -nY + rCenter.Y() );
221 }
222 }
223 else
224 mnPoints = 0;
225 }
226
ImplPolygon(const tools::Rectangle & rBound,const Point & rStart,const Point & rEnd,PolyStyle eStyle)227 ImplPolygon::ImplPolygon( const tools::Rectangle& rBound, const Point& rStart, const Point& rEnd,
228 PolyStyle eStyle )
229 {
230 const auto nWidth = rBound.GetWidth();
231 const auto nHeight = rBound.GetHeight();
232
233 if( ( nWidth != 0 ) && ( nHeight != 0 ) )
234 {
235 const Point aCenter( rBound.Center() );
236 // tdf#142268 Get Top Left corner of rectangle (the rectangle is not always correctly created)
237 const auto aBoundLeft = rBound.Left() < aCenter.X() ? rBound.Left() : rBound.Right();
238 const auto aBoundTop = rBound.Top() < aCenter.Y() ? rBound.Top() : rBound.Bottom();
239 const auto nRadX = o3tl::saturating_sub(aCenter.X(), aBoundLeft);
240 const auto nRadY = o3tl::saturating_sub(aCenter.Y(), aBoundTop);
241 sal_uInt16 nPoints;
242
243 tools::Long nRadXY;
244 const bool bOverflow = o3tl::checked_multiply(nRadX, nRadY, nRadXY);
245 if (!bOverflow)
246 {
247 nPoints = static_cast<sal_uInt16>(MinMax(
248 ( F_PI * ( 1.5 * ( nRadX + nRadY ) -
249 sqrt( static_cast<double>(std::abs(nRadXY)) ) ) ),
250 32, 256 ));
251 }
252 else
253 {
254 nPoints = 256;
255 }
256
257
258 if (nRadX > 32 && nRadY > 32 && o3tl::saturating_add(nRadX, nRadY) < 8192)
259 nPoints >>= 1;
260
261 // compute threshold
262 const double fRadX = nRadX;
263 const double fRadY = nRadY;
264 const double fCenterX = aCenter.X();
265 const double fCenterY = aCenter.Y();
266 double fStart = ImplGetParameter( aCenter, rStart, fRadX, fRadY );
267 double fEnd = ImplGetParameter( aCenter, rEnd, fRadX, fRadY );
268 double fDiff = fEnd - fStart;
269 double fStep;
270 sal_uInt16 nStart;
271 sal_uInt16 nEnd;
272 // #i73608# If startPoint is equal to endPoint, then draw full circle instead of nothing (as Metafiles spec)
273 if( fDiff <= 0. )
274 fDiff += F_2PI;
275
276 // Proportionally shrink number of points( fDiff / (2PI) );
277 nPoints = std::max( static_cast<sal_uInt16>( ( fDiff / F_2PI ) * nPoints ), sal_uInt16(16) );
278 fStep = fDiff / ( nPoints - 1 );
279
280 if( PolyStyle::Pie == eStyle )
281 {
282 const Point aCenter2( FRound( fCenterX ), FRound( fCenterY ) );
283
284 nStart = 1;
285 nEnd = nPoints + 1;
286 ImplInitSize(nPoints + 2);
287 mxPointAry[0] = aCenter2;
288 mxPointAry[nEnd] = aCenter2;
289 }
290 else
291 {
292 ImplInitSize( ( PolyStyle::Chord == eStyle ) ? ( nPoints + 1 ) : nPoints );
293 nStart = 0;
294 nEnd = nPoints;
295 }
296
297 for(; nStart < nEnd; nStart++, fStart += fStep )
298 {
299 Point& rPt = mxPointAry[nStart];
300
301 rPt.setX( FRound( fCenterX + fRadX * cos( fStart ) ) );
302 rPt.setY( FRound( fCenterY - fRadY * sin( fStart ) ) );
303 }
304
305 if( PolyStyle::Chord == eStyle )
306 mxPointAry[nPoints] = mxPointAry[0];
307 }
308 else
309 mnPoints = 0;
310 }
311
ImplPolygon(const Point & rBezPt1,const Point & rCtrlPt1,const Point & rBezPt2,const Point & rCtrlPt2,sal_uInt16 nPoints)312 ImplPolygon::ImplPolygon( const Point& rBezPt1, const Point& rCtrlPt1,
313 const Point& rBezPt2, const Point& rCtrlPt2, sal_uInt16 nPoints )
314 {
315 nPoints = ( 0 == nPoints ) ? 25 : ( ( nPoints < 2 ) ? 2 : nPoints );
316
317 const double fInc = 1.0 / ( nPoints - 1 );
318 double fK_1 = 0.0, fK1_1 = 1.0;
319 double fK_2, fK_3, fK1_2, fK1_3;
320 const double fX0 = rBezPt1.X();
321 const double fY0 = rBezPt1.Y();
322 const double fX1 = 3.0 * rCtrlPt1.X();
323 const double fY1 = 3.0 * rCtrlPt1.Y();
324 const double fX2 = 3.0 * rCtrlPt2.X();
325 const double fY2 = 3.0 * rCtrlPt2.Y();
326 const double fX3 = rBezPt2.X();
327 const double fY3 = rBezPt2.Y();
328
329 ImplInitSize(nPoints);
330
331 for( sal_uInt16 i = 0; i < nPoints; i++, fK_1 += fInc, fK1_1 -= fInc )
332 {
333 Point& rPt = mxPointAry[i];
334
335 fK_2 = fK_1;
336 fK_2 *= fK_1;
337 fK_3 = fK_2;
338 fK_3 *= fK_1;
339 fK1_2 = fK1_1;
340 fK1_2 *= fK1_1;
341 fK1_3 = fK1_2;
342 fK1_3 *= fK1_1;
343 double fK12 = fK_1 * fK1_2;
344 double fK21 = fK_2 * fK1_1;
345
346 rPt.setX( FRound( fK1_3 * fX0 + fK12 * fX1 + fK21 * fX2 + fK_3 * fX3 ) );
347 rPt.setY( FRound( fK1_3 * fY0 + fK12 * fY1 + fK21 * fY2 + fK_3 * fY3 ) );
348 }
349 }
350
351 // constructor to convert from basegfx::B2DPolygon
352 // #i76891# Needed to change from adding all control points (even for unused
353 // edges) and creating a fixed-size Polygon in the first run to creating the
354 // minimal Polygon. This requires a temporary Point- and Flag-Array for curves
355 // and a memcopy at ImplPolygon creation, but contains no zero-controlpoints
356 // for straight edges.
ImplPolygon(const basegfx::B2DPolygon & rPolygon)357 ImplPolygon::ImplPolygon(const basegfx::B2DPolygon& rPolygon)
358 : mnPoints(0)
359 {
360 const bool bCurve(rPolygon.areControlPointsUsed());
361 const bool bClosed(rPolygon.isClosed());
362 sal_uInt32 nB2DLocalCount(rPolygon.count());
363
364 if(bCurve)
365 {
366 // #127979# Reduce source point count hard to the limit of the tools Polygon
367 if(nB2DLocalCount > ((0x0000ffff / 3) - 1))
368 {
369 OSL_FAIL("Polygon::Polygon: Too many points in given B2DPolygon, need to reduce hard to maximum of tools Polygon (!)");
370 nB2DLocalCount = ((0x0000ffff / 3) - 1);
371 }
372
373 // calculate target point count
374 const sal_uInt32 nLoopCount(bClosed ? nB2DLocalCount : (nB2DLocalCount ? nB2DLocalCount - 1 : 0 ));
375
376 if(nLoopCount)
377 {
378 // calculate maximum array size and allocate; prepare insert index
379 const sal_uInt32 nMaxTargetCount((nLoopCount * 3) + 1);
380 ImplInitSize(static_cast< sal_uInt16 >(nMaxTargetCount), true);
381
382 // prepare insert index and current point
383 sal_uInt32 nArrayInsert(0);
384 basegfx::B2DCubicBezier aBezier;
385 aBezier.setStartPoint(rPolygon.getB2DPoint(0));
386
387 for(sal_uInt32 a(0); a < nLoopCount; a++)
388 {
389 // add current point (always) and remember StartPointIndex for evtl. later corrections
390 const Point aStartPoint(FRound(aBezier.getStartPoint().getX()), FRound(aBezier.getStartPoint().getY()));
391 const sal_uInt32 nStartPointIndex(nArrayInsert);
392 mxPointAry[nStartPointIndex] = aStartPoint;
393 mxFlagAry[nStartPointIndex] = PolyFlags::Normal;
394 nArrayInsert++;
395
396 // prepare next segment
397 const sal_uInt32 nNextIndex((a + 1) % nB2DLocalCount);
398 aBezier.setEndPoint(rPolygon.getB2DPoint(nNextIndex));
399 aBezier.setControlPointA(rPolygon.getNextControlPoint(a));
400 aBezier.setControlPointB(rPolygon.getPrevControlPoint(nNextIndex));
401
402 if(aBezier.isBezier())
403 {
404 // if one is used, add always two control points due to the old schema
405 mxPointAry[nArrayInsert] = Point(FRound(aBezier.getControlPointA().getX()), FRound(aBezier.getControlPointA().getY()));
406 mxFlagAry[nArrayInsert] = PolyFlags::Control;
407 nArrayInsert++;
408
409 mxPointAry[nArrayInsert] = Point(FRound(aBezier.getControlPointB().getX()), FRound(aBezier.getControlPointB().getY()));
410 mxFlagAry[nArrayInsert] = PolyFlags::Control;
411 nArrayInsert++;
412 }
413
414 // test continuity with previous control point to set flag value
415 if(aBezier.getControlPointA() != aBezier.getStartPoint() && (bClosed || a))
416 {
417 const basegfx::B2VectorContinuity eCont(rPolygon.getContinuityInPoint(a));
418
419 if(basegfx::B2VectorContinuity::C1 == eCont)
420 {
421 mxFlagAry[nStartPointIndex] = PolyFlags::Smooth;
422 }
423 else if(basegfx::B2VectorContinuity::C2 == eCont)
424 {
425 mxFlagAry[nStartPointIndex] = PolyFlags::Symmetric;
426 }
427 }
428
429 // prepare next polygon step
430 aBezier.setStartPoint(aBezier.getEndPoint());
431 }
432
433 if(bClosed)
434 {
435 // add first point again as closing point due to old definition
436 mxPointAry[nArrayInsert] = mxPointAry[0];
437 mxFlagAry[nArrayInsert] = PolyFlags::Normal;
438 nArrayInsert++;
439 }
440 else
441 {
442 // add last point as closing point
443 const basegfx::B2DPoint aClosingPoint(rPolygon.getB2DPoint(nB2DLocalCount - 1));
444 const Point aEnd(FRound(aClosingPoint.getX()), FRound(aClosingPoint.getY()));
445 mxPointAry[nArrayInsert] = aEnd;
446 mxFlagAry[nArrayInsert] = PolyFlags::Normal;
447 nArrayInsert++;
448 }
449
450 DBG_ASSERT(nArrayInsert <= nMaxTargetCount, "Polygon::Polygon from basegfx::B2DPolygon: wrong max point count estimation (!)");
451
452 if(nArrayInsert != nMaxTargetCount)
453 {
454 ImplSetSize(static_cast< sal_uInt16 >(nArrayInsert));
455 }
456 }
457 }
458 else
459 {
460 // #127979# Reduce source point count hard to the limit of the tools Polygon
461 if(nB2DLocalCount > (0x0000ffff - 1))
462 {
463 OSL_FAIL("Polygon::Polygon: Too many points in given B2DPolygon, need to reduce hard to maximum of tools Polygon (!)");
464 nB2DLocalCount = (0x0000ffff - 1);
465 }
466
467 if(nB2DLocalCount)
468 {
469 // point list creation
470 const sal_uInt32 nTargetCount(nB2DLocalCount + (bClosed ? 1 : 0));
471 ImplInitSize(static_cast< sal_uInt16 >(nTargetCount));
472 sal_uInt16 nIndex(0);
473
474 for(sal_uInt32 a(0); a < nB2DLocalCount; a++)
475 {
476 basegfx::B2DPoint aB2DPoint(rPolygon.getB2DPoint(a));
477 Point aPoint(FRound(aB2DPoint.getX()), FRound(aB2DPoint.getY()));
478 mxPointAry[nIndex++] = aPoint;
479 }
480
481 if(bClosed)
482 {
483 // add first point as closing point
484 mxPointAry[nIndex] = mxPointAry[0];
485 }
486 }
487 }
488 }
489
operator ==(const ImplPolygon & rCandidate) const490 bool ImplPolygon::operator==( const ImplPolygon& rCandidate) const
491 {
492 return mnPoints == rCandidate.mnPoints &&
493 mxFlagAry.get() == rCandidate.mxFlagAry.get() &&
494 mxPointAry.get() == rCandidate.mxPointAry.get();
495 }
496
ImplInitSize(sal_uInt16 nInitSize,bool bFlags)497 void ImplPolygon::ImplInitSize(sal_uInt16 nInitSize, bool bFlags)
498 {
499 if (nInitSize)
500 {
501 mxPointAry.reset(new Point[nInitSize]);
502 }
503
504 if (bFlags)
505 {
506 mxFlagAry.reset(new PolyFlags[nInitSize]);
507 memset(mxFlagAry.get(), 0, nInitSize);
508 }
509
510 mnPoints = nInitSize;
511 }
512
ImplSetSize(sal_uInt16 nNewSize,bool bResize)513 void ImplPolygon::ImplSetSize( sal_uInt16 nNewSize, bool bResize )
514 {
515 if( mnPoints == nNewSize )
516 return;
517
518 std::unique_ptr<Point[]> xNewAry;
519
520 if (nNewSize)
521 {
522 const std::size_t nNewSz(static_cast<std::size_t>(nNewSize)*sizeof(Point));
523 xNewAry.reset(new Point[nNewSize]);
524
525 if ( bResize )
526 {
527 // Copy the old points
528 if ( mnPoints < nNewSize )
529 {
530 // New points are already implicitly initialized to zero
531 const std::size_t nOldSz(mnPoints * sizeof(Point));
532 if (mxPointAry)
533 memcpy(xNewAry.get(), mxPointAry.get(), nOldSz);
534 }
535 else
536 {
537 if (mxPointAry)
538 memcpy(xNewAry.get(), mxPointAry.get(), nNewSz);
539 }
540 }
541 }
542
543 mxPointAry = std::move(xNewAry);
544
545 // take FlagArray into account, if applicable
546 if( mxFlagAry )
547 {
548 std::unique_ptr<PolyFlags[]> xNewFlagAry;
549
550 if( nNewSize )
551 {
552 xNewFlagAry.reset(new PolyFlags[nNewSize]);
553
554 if( bResize )
555 {
556 // copy the old flags
557 if ( mnPoints < nNewSize )
558 {
559 // initialize new flags to zero
560 memset(xNewFlagAry.get() + mnPoints, 0, nNewSize-mnPoints);
561 memcpy(xNewFlagAry.get(), mxFlagAry.get(), mnPoints);
562 }
563 else
564 memcpy(xNewFlagAry.get(), mxFlagAry.get(), nNewSize);
565 }
566 }
567
568 mxFlagAry = std::move(xNewFlagAry);
569 }
570
571 mnPoints = nNewSize;
572 }
573
ImplSplit(sal_uInt16 nPos,sal_uInt16 nSpace,ImplPolygon const * pInitPoly)574 bool ImplPolygon::ImplSplit( sal_uInt16 nPos, sal_uInt16 nSpace, ImplPolygon const * pInitPoly )
575 {
576 //Can't fit this in :-(, throw ?
577 if (mnPoints + nSpace > USHRT_MAX)
578 {
579 SAL_WARN("tools", "Polygon needs " << mnPoints + nSpace << " points, but only " << USHRT_MAX << " possible");
580 return false;
581 }
582
583 const sal_uInt16 nNewSize = mnPoints + nSpace;
584 const std::size_t nSpaceSize = static_cast<std::size_t>(nSpace) * sizeof(Point);
585
586 if( nPos >= mnPoints )
587 {
588 // Append at the back
589 nPos = mnPoints;
590 ImplSetSize( nNewSize );
591
592 if( pInitPoly )
593 {
594 memcpy(mxPointAry.get() + nPos, pInitPoly->mxPointAry.get(), nSpaceSize);
595
596 if (pInitPoly->mxFlagAry)
597 memcpy(mxFlagAry.get() + nPos, pInitPoly->mxFlagAry.get(), nSpace);
598 }
599 }
600 else
601 {
602 const sal_uInt16 nSecPos = nPos + nSpace;
603 const sal_uInt16 nRest = mnPoints - nPos;
604
605 std::unique_ptr<Point[]> xNewAry(new Point[nNewSize]);
606 memcpy(xNewAry.get(), mxPointAry.get(), nPos * sizeof(Point));
607
608 if( pInitPoly )
609 memcpy(xNewAry.get() + nPos, pInitPoly->mxPointAry.get(), nSpaceSize);
610
611 memcpy(xNewAry.get() + nSecPos, mxPointAry.get() + nPos, nRest * sizeof(Point));
612 mxPointAry = std::move(xNewAry);
613
614 // consider FlagArray
615 if (mxFlagAry)
616 {
617 std::unique_ptr<PolyFlags[]> xNewFlagAry(new PolyFlags[nNewSize]);
618
619 memcpy(xNewFlagAry.get(), mxFlagAry.get(), nPos);
620
621 if (pInitPoly && pInitPoly->mxFlagAry)
622 memcpy(xNewFlagAry.get() + nPos, pInitPoly->mxFlagAry.get(), nSpace);
623 else
624 memset(xNewFlagAry.get() + nPos, 0, nSpace);
625
626 memcpy(xNewFlagAry.get() + nSecPos, mxFlagAry.get() + nPos, nRest);
627 mxFlagAry = std::move(xNewFlagAry);
628 }
629
630 mnPoints = nNewSize;
631 }
632
633 return true;
634 }
635
ImplCreateFlagArray()636 void ImplPolygon::ImplCreateFlagArray()
637 {
638 if (!mxFlagAry)
639 {
640 mxFlagAry.reset(new PolyFlags[mnPoints]);
641 memset(mxFlagAry.get(), 0, mnPoints);
642 }
643 }
644
645 namespace {
646
647 class ImplPointFilter
648 {
649 public:
650 virtual void LastPoint() = 0;
651 virtual void Input( const Point& rPoint ) = 0;
652
653 protected:
~ImplPointFilter()654 ~ImplPointFilter() {}
655 };
656
657 class ImplPolygonPointFilter : public ImplPointFilter
658 {
659 ImplPolygon maPoly;
660 sal_uInt16 mnSize;
661 public:
ImplPolygonPointFilter(sal_uInt16 nDestSize)662 explicit ImplPolygonPointFilter(sal_uInt16 nDestSize)
663 : maPoly(nDestSize)
664 , mnSize(0)
665 {
666 }
667
~ImplPolygonPointFilter()668 virtual ~ImplPolygonPointFilter()
669 {
670 }
671
672 virtual void LastPoint() override;
673 virtual void Input( const Point& rPoint ) override;
674
get()675 ImplPolygon& get() { return maPoly; }
676 };
677
678 }
679
Input(const Point & rPoint)680 void ImplPolygonPointFilter::Input( const Point& rPoint )
681 {
682 if ( !mnSize || (rPoint != maPoly.mxPointAry[mnSize-1]) )
683 {
684 mnSize++;
685 if ( mnSize > maPoly.mnPoints )
686 maPoly.ImplSetSize( mnSize );
687 maPoly.mxPointAry[mnSize-1] = rPoint;
688 }
689 }
690
LastPoint()691 void ImplPolygonPointFilter::LastPoint()
692 {
693 if ( mnSize < maPoly.mnPoints )
694 maPoly.ImplSetSize( mnSize );
695 };
696
697 namespace {
698
699 class ImplEdgePointFilter : public ImplPointFilter
700 {
701 Point maFirstPoint;
702 Point maLastPoint;
703 ImplPointFilter& mrNextFilter;
704 const tools::Long mnLow;
705 const tools::Long mnHigh;
706 const int mnEdge;
707 int mnLastOutside;
708 bool mbFirst;
709
710 public:
ImplEdgePointFilter(int nEdge,tools::Long nLow,tools::Long nHigh,ImplPointFilter & rNextFilter)711 ImplEdgePointFilter( int nEdge, tools::Long nLow, tools::Long nHigh,
712 ImplPointFilter& rNextFilter ) :
713 mrNextFilter( rNextFilter ),
714 mnLow( nLow ),
715 mnHigh( nHigh ),
716 mnEdge( nEdge ),
717 mnLastOutside( 0 ),
718 mbFirst( true )
719 {
720 }
721
~ImplEdgePointFilter()722 virtual ~ImplEdgePointFilter() {}
723
724 Point EdgeSection( const Point& rPoint, int nEdge ) const;
725 int VisibleSide( const Point& rPoint ) const;
IsPolygon() const726 bool IsPolygon() const
727 { return maFirstPoint == maLastPoint; }
728
729 virtual void Input( const Point& rPoint ) override;
730 virtual void LastPoint() override;
731 };
732
733 }
734
VisibleSide(const Point & rPoint) const735 inline int ImplEdgePointFilter::VisibleSide( const Point& rPoint ) const
736 {
737 if ( mnEdge & EDGE_HORZ )
738 {
739 return rPoint.X() < mnLow ? EDGE_LEFT :
740 rPoint.X() > mnHigh ? EDGE_RIGHT : 0;
741 }
742 else
743 {
744 return rPoint.Y() < mnLow ? EDGE_TOP :
745 rPoint.Y() > mnHigh ? EDGE_BOTTOM : 0;
746 }
747 }
748
EdgeSection(const Point & rPoint,int nEdge) const749 Point ImplEdgePointFilter::EdgeSection( const Point& rPoint, int nEdge ) const
750 {
751 tools::Long lx = maLastPoint.X();
752 tools::Long ly = maLastPoint.Y();
753 tools::Long md = rPoint.X() - lx;
754 tools::Long mn = rPoint.Y() - ly;
755 tools::Long nNewX;
756 tools::Long nNewY;
757
758 if ( nEdge & EDGE_VERT )
759 {
760 nNewY = (nEdge == EDGE_TOP) ? mnLow : mnHigh;
761 tools::Long dy = nNewY - ly;
762 if ( !md )
763 nNewX = lx;
764 else if ( (LONG_MAX / std::abs(md)) >= std::abs(dy) )
765 nNewX = (dy * md) / mn + lx;
766 else
767 {
768 BigInt ady = dy;
769 ady *= md;
770 if( ady.IsNeg() )
771 if( mn < 0 )
772 ady += mn/2;
773 else
774 ady -= (mn-1)/2;
775 else
776 if( mn < 0 )
777 ady -= (mn+1)/2;
778 else
779 ady += mn/2;
780 ady /= mn;
781 nNewX = static_cast<tools::Long>(ady) + lx;
782 }
783 }
784 else
785 {
786 nNewX = (nEdge == EDGE_LEFT) ? mnLow : mnHigh;
787 tools::Long dx = nNewX - lx;
788 if ( !mn )
789 nNewY = ly;
790 else if ( (LONG_MAX / std::abs(mn)) >= std::abs(dx) )
791 nNewY = (dx * mn) / md + ly;
792 else
793 {
794 BigInt adx = dx;
795 adx *= mn;
796 if( adx.IsNeg() )
797 if( md < 0 )
798 adx += md/2;
799 else
800 adx -= (md-1)/2;
801 else
802 if( md < 0 )
803 adx -= (md+1)/2;
804 else
805 adx += md/2;
806 adx /= md;
807 nNewY = static_cast<tools::Long>(adx) + ly;
808 }
809 }
810
811 return Point( nNewX, nNewY );
812 }
813
Input(const Point & rPoint)814 void ImplEdgePointFilter::Input( const Point& rPoint )
815 {
816 int nOutside = VisibleSide( rPoint );
817
818 if ( mbFirst )
819 {
820 maFirstPoint = rPoint;
821 mbFirst = false;
822 if ( !nOutside )
823 mrNextFilter.Input( rPoint );
824 }
825 else if ( rPoint == maLastPoint )
826 return;
827 else if ( !nOutside )
828 {
829 if ( mnLastOutside )
830 mrNextFilter.Input( EdgeSection( rPoint, mnLastOutside ) );
831 mrNextFilter.Input( rPoint );
832 }
833 else if ( !mnLastOutside )
834 mrNextFilter.Input( EdgeSection( rPoint, nOutside ) );
835 else if ( nOutside != mnLastOutside )
836 {
837 mrNextFilter.Input( EdgeSection( rPoint, mnLastOutside ) );
838 mrNextFilter.Input( EdgeSection( rPoint, nOutside ) );
839 }
840
841 maLastPoint = rPoint;
842 mnLastOutside = nOutside;
843 }
844
LastPoint()845 void ImplEdgePointFilter::LastPoint()
846 {
847 if ( !mbFirst )
848 {
849 int nOutside = VisibleSide( maFirstPoint );
850
851 if ( nOutside != mnLastOutside )
852 Input( maFirstPoint );
853 mrNextFilter.LastPoint();
854 }
855 }
856
857 namespace tools
858 {
859
SubdivideBezier(const tools::Polygon & rPoly)860 tools::Polygon Polygon::SubdivideBezier( const tools::Polygon& rPoly )
861 {
862 tools::Polygon aPoly;
863
864 // #100127# Use adaptive subdivide instead of fixed 25 segments
865 rPoly.AdaptiveSubdivide( aPoly );
866
867 return aPoly;
868 }
869
Polygon()870 Polygon::Polygon() : mpImplPolygon(ImplPolygon())
871 {
872 }
873
Polygon(sal_uInt16 nSize)874 Polygon::Polygon( sal_uInt16 nSize ) : mpImplPolygon(ImplPolygon(nSize))
875 {
876 }
877
Polygon(sal_uInt16 nPoints,const Point * pPtAry,const PolyFlags * pFlagAry)878 Polygon::Polygon( sal_uInt16 nPoints, const Point* pPtAry, const PolyFlags* pFlagAry ) : mpImplPolygon(ImplPolygon(nPoints, pPtAry, pFlagAry))
879 {
880 }
881
Polygon(const tools::Polygon & rPoly)882 Polygon::Polygon( const tools::Polygon& rPoly ) : mpImplPolygon(rPoly.mpImplPolygon)
883 {
884 }
885
Polygon(tools::Polygon && rPoly)886 Polygon::Polygon( tools::Polygon&& rPoly) noexcept
887 : mpImplPolygon(std::move(rPoly.mpImplPolygon))
888 {
889 }
890
Polygon(const tools::Rectangle & rRect)891 Polygon::Polygon( const tools::Rectangle& rRect ) : mpImplPolygon(ImplPolygon(rRect))
892 {
893 }
894
Polygon(const tools::Rectangle & rRect,sal_uInt32 nHorzRound,sal_uInt32 nVertRound)895 Polygon::Polygon( const tools::Rectangle& rRect, sal_uInt32 nHorzRound, sal_uInt32 nVertRound )
896 : mpImplPolygon(ImplPolygon(rRect, nHorzRound, nVertRound))
897 {
898 }
899
Polygon(const Point & rCenter,tools::Long nRadX,tools::Long nRadY)900 Polygon::Polygon( const Point& rCenter, tools::Long nRadX, tools::Long nRadY )
901 : mpImplPolygon(ImplPolygon(rCenter, nRadX, nRadY))
902 {
903 }
904
Polygon(const tools::Rectangle & rBound,const Point & rStart,const Point & rEnd,PolyStyle eStyle)905 Polygon::Polygon( const tools::Rectangle& rBound, const Point& rStart, const Point& rEnd,
906 PolyStyle eStyle ) : mpImplPolygon(ImplPolygon(rBound, rStart, rEnd, eStyle))
907 {
908 }
909
Polygon(const Point & rBezPt1,const Point & rCtrlPt1,const Point & rBezPt2,const Point & rCtrlPt2,sal_uInt16 nPoints)910 Polygon::Polygon( const Point& rBezPt1, const Point& rCtrlPt1,
911 const Point& rBezPt2, const Point& rCtrlPt2,
912 sal_uInt16 nPoints ) : mpImplPolygon(ImplPolygon(rBezPt1, rCtrlPt1, rBezPt2, rCtrlPt2, nPoints))
913 {
914 }
915
~Polygon()916 Polygon::~Polygon()
917 {
918 }
919
GetPointAry()920 Point * Polygon::GetPointAry()
921 {
922 return mpImplPolygon->mxPointAry.get();
923 }
924
GetConstPointAry() const925 const Point* Polygon::GetConstPointAry() const
926 {
927 return mpImplPolygon->mxPointAry.get();
928 }
929
GetConstFlagAry() const930 const PolyFlags* Polygon::GetConstFlagAry() const
931 {
932 return mpImplPolygon->mxFlagAry.get();
933 }
934
SetPoint(const Point & rPt,sal_uInt16 nPos)935 void Polygon::SetPoint( const Point& rPt, sal_uInt16 nPos )
936 {
937 DBG_ASSERT( nPos < mpImplPolygon->mnPoints,
938 "Polygon::SetPoint(): nPos >= nPoints" );
939
940 mpImplPolygon->mxPointAry[nPos] = rPt;
941 }
942
SetFlags(sal_uInt16 nPos,PolyFlags eFlags)943 void Polygon::SetFlags( sal_uInt16 nPos, PolyFlags eFlags )
944 {
945 DBG_ASSERT( nPos < mpImplPolygon->mnPoints,
946 "Polygon::SetFlags(): nPos >= nPoints" );
947
948 // we do only want to create the flag array if there
949 // is at least one flag different to PolyFlags::Normal
950 if ( eFlags != PolyFlags::Normal )
951 {
952 mpImplPolygon->ImplCreateFlagArray();
953 mpImplPolygon->mxFlagAry[ nPos ] = eFlags;
954 }
955 }
956
GetPoint(sal_uInt16 nPos) const957 const Point& Polygon::GetPoint( sal_uInt16 nPos ) const
958 {
959 DBG_ASSERT( nPos < mpImplPolygon->mnPoints,
960 "Polygon::GetPoint(): nPos >= nPoints" );
961
962 return mpImplPolygon->mxPointAry[nPos];
963 }
964
GetFlags(sal_uInt16 nPos) const965 PolyFlags Polygon::GetFlags( sal_uInt16 nPos ) const
966 {
967 DBG_ASSERT( nPos < mpImplPolygon->mnPoints,
968 "Polygon::GetFlags(): nPos >= nPoints" );
969 return mpImplPolygon->mxFlagAry
970 ? mpImplPolygon->mxFlagAry[ nPos ]
971 : PolyFlags::Normal;
972 }
973
HasFlags() const974 bool Polygon::HasFlags() const
975 {
976 return bool(mpImplPolygon->mxFlagAry);
977 }
978
IsRect() const979 bool Polygon::IsRect() const
980 {
981 bool bIsRect = false;
982 if (!mpImplPolygon->mxFlagAry)
983 {
984 if ( ( ( mpImplPolygon->mnPoints == 5 ) && ( mpImplPolygon->mxPointAry[ 0 ] == mpImplPolygon->mxPointAry[ 4 ] ) ) ||
985 ( mpImplPolygon->mnPoints == 4 ) )
986 {
987 if ( ( mpImplPolygon->mxPointAry[ 0 ].X() == mpImplPolygon->mxPointAry[ 3 ].X() ) &&
988 ( mpImplPolygon->mxPointAry[ 0 ].Y() == mpImplPolygon->mxPointAry[ 1 ].Y() ) &&
989 ( mpImplPolygon->mxPointAry[ 1 ].X() == mpImplPolygon->mxPointAry[ 2 ].X() ) &&
990 ( mpImplPolygon->mxPointAry[ 2 ].Y() == mpImplPolygon->mxPointAry[ 3 ].Y() ) )
991 bIsRect = true;
992 }
993 }
994 return bIsRect;
995 }
996
SetSize(sal_uInt16 nNewSize)997 void Polygon::SetSize( sal_uInt16 nNewSize )
998 {
999 if( nNewSize != mpImplPolygon->mnPoints )
1000 {
1001 mpImplPolygon->ImplSetSize( nNewSize );
1002 }
1003 }
1004
GetSize() const1005 sal_uInt16 Polygon::GetSize() const
1006 {
1007 return mpImplPolygon->mnPoints;
1008 }
1009
Clear()1010 void Polygon::Clear()
1011 {
1012 mpImplPolygon = ImplType(ImplPolygon());
1013 }
1014
CalcDistance(sal_uInt16 nP1,sal_uInt16 nP2) const1015 double Polygon::CalcDistance( sal_uInt16 nP1, sal_uInt16 nP2 ) const
1016 {
1017 DBG_ASSERT( nP1 < mpImplPolygon->mnPoints,
1018 "Polygon::CalcDistance(): nPos1 >= nPoints" );
1019 DBG_ASSERT( nP2 < mpImplPolygon->mnPoints,
1020 "Polygon::CalcDistance(): nPos2 >= nPoints" );
1021
1022 const Point& rP1 = mpImplPolygon->mxPointAry[ nP1 ];
1023 const Point& rP2 = mpImplPolygon->mxPointAry[ nP2 ];
1024 const double fDx = rP2.X() - rP1.X();
1025 const double fDy = rP2.Y() - rP1.Y();
1026
1027 return sqrt( fDx * fDx + fDy * fDy );
1028 }
1029
Optimize(PolyOptimizeFlags nOptimizeFlags)1030 void Polygon::Optimize( PolyOptimizeFlags nOptimizeFlags )
1031 {
1032 DBG_ASSERT( !mpImplPolygon->mxFlagAry, "Optimizing could fail with beziers!" );
1033
1034 sal_uInt16 nSize = mpImplPolygon->mnPoints;
1035
1036 if( !(bool(nOptimizeFlags) && nSize) )
1037 return;
1038
1039 if( nOptimizeFlags & PolyOptimizeFlags::EDGES )
1040 {
1041 const tools::Rectangle aBound( GetBoundRect() );
1042 const double fArea = ( aBound.GetWidth() + aBound.GetHeight() ) * 0.5;
1043 const sal_uInt16 nPercent = 50;
1044
1045 Optimize( PolyOptimizeFlags::NO_SAME );
1046 ImplReduceEdges( *this, fArea, nPercent );
1047 }
1048 else if( nOptimizeFlags & PolyOptimizeFlags::NO_SAME )
1049 {
1050 tools::Polygon aNewPoly;
1051 const Point& rFirst = mpImplPolygon->mxPointAry[ 0 ];
1052
1053 while( nSize && ( mpImplPolygon->mxPointAry[ nSize - 1 ] == rFirst ) )
1054 nSize--;
1055
1056 if( nSize > 1 )
1057 {
1058 sal_uInt16 nLast = 0, nNewCount = 1;
1059
1060 aNewPoly.SetSize( nSize );
1061 aNewPoly[ 0 ] = rFirst;
1062
1063 for( sal_uInt16 i = 1; i < nSize; i++ )
1064 {
1065 if( mpImplPolygon->mxPointAry[ i ] != mpImplPolygon->mxPointAry[ nLast ])
1066 {
1067 nLast = i;
1068 aNewPoly[ nNewCount++ ] = mpImplPolygon->mxPointAry[ i ];
1069 }
1070 }
1071
1072 if( nNewCount == 1 )
1073 aNewPoly.Clear();
1074 else
1075 aNewPoly.SetSize( nNewCount );
1076 }
1077
1078 *this = aNewPoly;
1079 }
1080
1081 nSize = mpImplPolygon->mnPoints;
1082
1083 if( nSize > 1 )
1084 {
1085 if( ( nOptimizeFlags & PolyOptimizeFlags::CLOSE ) &&
1086 ( mpImplPolygon->mxPointAry[ 0 ] != mpImplPolygon->mxPointAry[ nSize - 1 ] ) )
1087 {
1088 SetSize( mpImplPolygon->mnPoints + 1 );
1089 mpImplPolygon->mxPointAry[ mpImplPolygon->mnPoints - 1 ] = mpImplPolygon->mxPointAry[ 0 ];
1090 }
1091 }
1092 }
1093
1094
1095 /** Recursively subdivide cubic bezier curve via deCasteljau.
1096
1097 @param rPointIter
1098 Output iterator, where the subdivided polylines are written to.
1099
1100 @param d
1101 Squared difference of curve to a straight line
1102
1103 @param P*
1104 Exactly four points, interpreted as support and control points of
1105 a cubic bezier curve. Must be in device coordinates, since stop
1106 criterion is based on the following assumption: the device has a
1107 finite resolution, it is thus sufficient to stop subdivision if the
1108 curve does not deviate more than one pixel from a straight line.
1109
1110 */
ImplAdaptiveSubdivide(::std::back_insert_iterator<::std::vector<Point>> & rPointIter,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)1111 static void ImplAdaptiveSubdivide( ::std::back_insert_iterator< ::std::vector< Point > >& rPointIter,
1112 const double old_d2,
1113 int recursionDepth,
1114 const double d2,
1115 const double P1x, const double P1y,
1116 const double P2x, const double P2y,
1117 const double P3x, const double P3y,
1118 const double P4x, const double P4y )
1119 {
1120 // Hard limit on recursion depth, empiric number.
1121 enum {maxRecursionDepth=128};
1122
1123 // Perform bezier flatness test (lecture notes from R. Schaback,
1124 // Mathematics of Computer-Aided Design, Uni Goettingen, 2000)
1125
1126 // ||P(t) - L(t)|| <= max ||b_j - b_0 - j/n(b_n - b_0)||
1127 // 0<=j<=n
1128
1129 // What is calculated here is an upper bound to the distance from
1130 // a line through b_0 and b_3 (P1 and P4 in our notation) and the
1131 // curve. We can drop 0 and n from the running indices, since the
1132 // argument of max becomes zero for those cases.
1133 const double fJ1x( P2x - P1x - 1.0/3.0*(P4x - P1x) );
1134 const double fJ1y( P2y - P1y - 1.0/3.0*(P4y - P1y) );
1135 const double fJ2x( P3x - P1x - 2.0/3.0*(P4x - P1x) );
1136 const double fJ2y( P3y - P1y - 2.0/3.0*(P4y - P1y) );
1137 const double distance2( ::std::max( fJ1x*fJ1x + fJ1y*fJ1y,
1138 fJ2x*fJ2x + fJ2y*fJ2y) );
1139
1140 // stop if error measure does not improve anymore. This is a
1141 // safety guard against floating point inaccuracies.
1142 // stop at recursion level 128. This is a safety guard against
1143 // floating point inaccuracies.
1144 // stop if distance from line is guaranteed to be bounded by d
1145 if( old_d2 > d2 &&
1146 recursionDepth < maxRecursionDepth &&
1147 distance2 >= d2 )
1148 {
1149 // deCasteljau bezier arc, split at t=0.5
1150 // Foley/vanDam, p. 508
1151 const double L1x( P1x ), L1y( P1y );
1152 const double L2x( (P1x + P2x)*0.5 ), L2y( (P1y + P2y)*0.5 );
1153 const double Hx ( (P2x + P3x)*0.5 ), Hy ( (P2y + P3y)*0.5 );
1154 const double L3x( (L2x + Hx)*0.5 ), L3y( (L2y + Hy)*0.5 );
1155 const double R4x( P4x ), R4y( P4y );
1156 const double R3x( (P3x + P4x)*0.5 ), R3y( (P3y + P4y)*0.5 );
1157 const double R2x( (Hx + R3x)*0.5 ), R2y( (Hy + R3y)*0.5 );
1158 const double R1x( (L3x + R2x)*0.5 ), R1y( (L3y + R2y)*0.5 );
1159 const double L4x( R1x ), L4y( R1y );
1160
1161 // subdivide further
1162 ++recursionDepth;
1163 ImplAdaptiveSubdivide(rPointIter, distance2, recursionDepth, d2, L1x, L1y, L2x, L2y, L3x, L3y, L4x, L4y);
1164 ImplAdaptiveSubdivide(rPointIter, distance2, recursionDepth, d2, R1x, R1y, R2x, R2y, R3x, R3y, R4x, R4y);
1165 }
1166 else
1167 {
1168 // requested resolution reached.
1169 // Add end points to output iterator.
1170 // order is preserved, since this is so to say depth first traversal.
1171 *rPointIter++ = Point( FRound(P1x), FRound(P1y) );
1172 }
1173 }
1174
AdaptiveSubdivide(Polygon & rResult,const double d) const1175 void Polygon::AdaptiveSubdivide( Polygon& rResult, const double d ) const
1176 {
1177 if (!mpImplPolygon->mxFlagAry)
1178 {
1179 rResult = *this;
1180 }
1181 else
1182 {
1183 sal_uInt16 i;
1184 sal_uInt16 nPts( GetSize() );
1185 ::std::vector< Point > aPoints;
1186 aPoints.reserve( nPts );
1187 ::std::back_insert_iterator< ::std::vector< Point > > aPointIter( aPoints );
1188
1189 for(i=0; i<nPts;)
1190 {
1191 if( ( i + 3 ) < nPts )
1192 {
1193 PolyFlags P1( mpImplPolygon->mxFlagAry[ i ] );
1194 PolyFlags P4( mpImplPolygon->mxFlagAry[ i + 3 ] );
1195
1196 if( ( PolyFlags::Normal == P1 || PolyFlags::Smooth == P1 || PolyFlags::Symmetric == P1 ) &&
1197 ( PolyFlags::Control == mpImplPolygon->mxFlagAry[ i + 1 ] ) &&
1198 ( PolyFlags::Control == mpImplPolygon->mxFlagAry[ i + 2 ] ) &&
1199 ( PolyFlags::Normal == P4 || PolyFlags::Smooth == P4 || PolyFlags::Symmetric == P4 ) )
1200 {
1201 ImplAdaptiveSubdivide( aPointIter, d*d+1.0, 0, d*d,
1202 mpImplPolygon->mxPointAry[ i ].X(), mpImplPolygon->mxPointAry[ i ].Y(),
1203 mpImplPolygon->mxPointAry[ i+1 ].X(), mpImplPolygon->mxPointAry[ i+1 ].Y(),
1204 mpImplPolygon->mxPointAry[ i+2 ].X(), mpImplPolygon->mxPointAry[ i+2 ].Y(),
1205 mpImplPolygon->mxPointAry[ i+3 ].X(), mpImplPolygon->mxPointAry[ i+3 ].Y() );
1206 i += 3;
1207 continue;
1208 }
1209 }
1210
1211 *aPointIter++ = mpImplPolygon->mxPointAry[ i++ ];
1212
1213 if (aPoints.size() >= SAL_MAX_UINT16)
1214 {
1215 OSL_ENSURE(aPoints.size() < SAL_MAX_UINT16,
1216 "Polygon::AdaptiveSubdivision created polygon too many points;"
1217 " using original polygon instead");
1218
1219 // The resulting polygon can not hold all the points
1220 // that we have created so far. Stop the subdivision
1221 // and return a copy of the unmodified polygon.
1222 rResult = *this;
1223 return;
1224 }
1225 }
1226
1227 // fill result polygon
1228 rResult = tools::Polygon( static_cast<sal_uInt16>(aPoints.size()) ); // ensure sufficient size for copy
1229 ::std::copy(aPoints.begin(), aPoints.end(), rResult.mpImplPolygon->mxPointAry.get());
1230 }
1231 }
1232
1233 namespace {
1234
1235 class Vector2D
1236 {
1237 private:
1238 double mfX;
1239 double mfY;
1240 public:
Vector2D(const Point & rPoint)1241 explicit Vector2D( const Point& rPoint ) : mfX( rPoint.X() ), mfY( rPoint.Y() ) {};
GetLength() const1242 double GetLength() const { return hypot( mfX, mfY ); }
operator -=(const Vector2D & rVec)1243 Vector2D& operator-=( const Vector2D& rVec ) { mfX -= rVec.mfX; mfY -= rVec.mfY; return *this; }
Scalar(const Vector2D & rVec) const1244 double Scalar( const Vector2D& rVec ) const { return mfX * rVec.mfX + mfY * rVec.mfY ; }
1245 Vector2D& Normalize();
IsPositive(Vector2D const & rVec) const1246 bool IsPositive( Vector2D const & rVec ) const { return ( mfX * rVec.mfY - mfY * rVec.mfX ) >= 0.0; }
IsNegative(Vector2D const & rVec) const1247 bool IsNegative( Vector2D const & rVec ) const { return !IsPositive( rVec ); }
1248 };
1249
1250 }
1251
Normalize()1252 Vector2D& Vector2D::Normalize()
1253 {
1254 double fLen = Scalar( *this );
1255
1256 if( ( fLen != 0.0 ) && ( fLen != 1.0 ) )
1257 {
1258 fLen = sqrt( fLen );
1259 if( fLen != 0.0 )
1260 {
1261 mfX /= fLen;
1262 mfY /= fLen;
1263 }
1264 }
1265
1266 return *this;
1267 }
1268
ImplReduceEdges(tools::Polygon & rPoly,const double & rArea,sal_uInt16 nPercent)1269 void Polygon::ImplReduceEdges( tools::Polygon& rPoly, const double& rArea, sal_uInt16 nPercent )
1270 {
1271 const double fBound = 2000.0 * ( 100 - nPercent ) * 0.01;
1272 sal_uInt16 nNumNoChange = 0,
1273 nNumRuns = 0;
1274
1275 while( nNumNoChange < 2 )
1276 {
1277 sal_uInt16 nPntCnt = rPoly.GetSize(), nNewPos = 0;
1278 tools::Polygon aNewPoly( nPntCnt );
1279 bool bChangeInThisRun = false;
1280
1281 for( sal_uInt16 n = 0; n < nPntCnt; n++ )
1282 {
1283 bool bDeletePoint = false;
1284
1285 if( ( n + nNumRuns ) % 2 )
1286 {
1287 sal_uInt16 nIndPrev = !n ? nPntCnt - 1 : n - 1;
1288 sal_uInt16 nIndPrevPrev = !nIndPrev ? nPntCnt - 1 : nIndPrev - 1;
1289 sal_uInt16 nIndNext = ( n == nPntCnt-1 ) ? 0 : n + 1;
1290 sal_uInt16 nIndNextNext = ( nIndNext == nPntCnt - 1 ) ? 0 : nIndNext + 1;
1291 Vector2D aVec1( rPoly[ nIndPrev ] ); aVec1 -= Vector2D(rPoly[ nIndPrevPrev ]);
1292 Vector2D aVec2( rPoly[ n ] ); aVec2 -= Vector2D(rPoly[ nIndPrev ]);
1293 Vector2D aVec3( rPoly[ nIndNext ] ); aVec3 -= Vector2D(rPoly[ n ]);
1294 Vector2D aVec4( rPoly[ nIndNextNext ] ); aVec4 -= Vector2D(rPoly[ nIndNext ]);
1295 double fDist1 = aVec1.GetLength(), fDist2 = aVec2.GetLength();
1296 double fDist3 = aVec3.GetLength(), fDist4 = aVec4.GetLength();
1297 double fTurnB = aVec2.Normalize().Scalar( aVec3.Normalize() );
1298
1299 if( fabs( fTurnB ) < ( 1.0 + SMALL_DVALUE ) && fabs( fTurnB ) > ( 1.0 - SMALL_DVALUE ) )
1300 bDeletePoint = true;
1301 else
1302 {
1303 Vector2D aVecB( rPoly[ nIndNext ] );
1304 aVecB -= Vector2D(rPoly[ nIndPrev ] );
1305 double fDistB = aVecB.GetLength();
1306 double fLenWithB = fDist2 + fDist3;
1307 double fLenFact = ( fDistB != 0.0 ) ? fLenWithB / fDistB : 1.0;
1308 double fTurnPrev = aVec1.Normalize().Scalar( aVec2 );
1309 double fTurnNext = aVec3.Scalar( aVec4.Normalize() );
1310 double fGradPrev, fGradB, fGradNext;
1311
1312 if( fabs( fTurnPrev ) < ( 1.0 + SMALL_DVALUE ) && fabs( fTurnPrev ) > ( 1.0 - SMALL_DVALUE ) )
1313 fGradPrev = 0.0;
1314 else
1315 fGradPrev = basegfx::rad2deg(acos(fTurnPrev)) * (aVec1.IsNegative(aVec2) ? -1 : 1);
1316
1317 fGradB = basegfx::rad2deg(acos(fTurnB)) * (aVec2.IsNegative(aVec3) ? -1 : 1);
1318
1319 if( fabs( fTurnNext ) < ( 1.0 + SMALL_DVALUE ) && fabs( fTurnNext ) > ( 1.0 - SMALL_DVALUE ) )
1320 fGradNext = 0.0;
1321 else
1322 fGradNext = basegfx::rad2deg(acos(fTurnNext)) * (aVec3.IsNegative(aVec4) ? -1 : 1);
1323
1324 if( ( fGradPrev > 0.0 && fGradB < 0.0 && fGradNext > 0.0 ) ||
1325 ( fGradPrev < 0.0 && fGradB > 0.0 && fGradNext < 0.0 ) )
1326 {
1327 if( ( fLenFact < ( FSQRT2 + SMALL_DVALUE ) ) &&
1328 ( ( ( fDist1 + fDist4 ) / ( fDist2 + fDist3 ) ) * 2000.0 ) > fBound )
1329 {
1330 bDeletePoint = true;
1331 }
1332 }
1333 else
1334 {
1335 double fRelLen = 1.0 - sqrt( fDistB / rArea );
1336
1337 if( fRelLen < 0.0 )
1338 fRelLen = 0.0;
1339 else if( fRelLen > 1.0 )
1340 fRelLen = 1.0;
1341
1342 if( ( std::round( ( fLenFact - 1.0 ) * 1000000.0 ) < fBound ) &&
1343 ( fabs( fGradB ) <= ( fRelLen * fBound * 0.01 ) ) )
1344 {
1345 bDeletePoint = true;
1346 }
1347 }
1348 }
1349 }
1350
1351 if( !bDeletePoint )
1352 aNewPoly[ nNewPos++ ] = rPoly[ n ];
1353 else
1354 bChangeInThisRun = true;
1355 }
1356
1357 if( bChangeInThisRun && nNewPos )
1358 {
1359 aNewPoly.SetSize( nNewPos );
1360 rPoly = aNewPoly;
1361 nNumNoChange = 0;
1362 }
1363 else
1364 nNumNoChange++;
1365
1366 nNumRuns++;
1367 }
1368 }
1369
Move(tools::Long nHorzMove,tools::Long nVertMove)1370 void Polygon::Move( tools::Long nHorzMove, tools::Long nVertMove )
1371 {
1372 // This check is required for DrawEngine
1373 if ( !nHorzMove && !nVertMove )
1374 return;
1375
1376 // Move points
1377 sal_uInt16 nCount = mpImplPolygon->mnPoints;
1378 for ( sal_uInt16 i = 0; i < nCount; i++ )
1379 {
1380 Point& rPt = mpImplPolygon->mxPointAry[i];
1381 rPt.AdjustX(nHorzMove );
1382 rPt.AdjustY(nVertMove );
1383 }
1384 }
1385
Translate(const Point & rTrans)1386 void Polygon::Translate(const Point& rTrans)
1387 {
1388 for ( sal_uInt16 i = 0, nCount = mpImplPolygon->mnPoints; i < nCount; i++ )
1389 mpImplPolygon->mxPointAry[ i ] += rTrans;
1390 }
1391
Scale(double fScaleX,double fScaleY)1392 void Polygon::Scale( double fScaleX, double fScaleY )
1393 {
1394 for ( sal_uInt16 i = 0, nCount = mpImplPolygon->mnPoints; i < nCount; i++ )
1395 {
1396 Point& rPnt = mpImplPolygon->mxPointAry[i];
1397 rPnt.setX( static_cast<tools::Long>( fScaleX * rPnt.X() ) );
1398 rPnt.setY( static_cast<tools::Long>( fScaleY * rPnt.Y() ) );
1399 }
1400 }
1401
Rotate(const Point & rCenter,Degree10 nAngle10)1402 void Polygon::Rotate( const Point& rCenter, Degree10 nAngle10 )
1403 {
1404 nAngle10 %= 3600_deg10;
1405
1406 if( nAngle10 )
1407 {
1408 const double fAngle = F_PI1800 * nAngle10.get();
1409 Rotate( rCenter, sin( fAngle ), cos( fAngle ) );
1410 }
1411 }
1412
Rotate(const Point & rCenter,double fSin,double fCos)1413 void Polygon::Rotate( const Point& rCenter, double fSin, double fCos )
1414 {
1415 tools::Long nCenterX = rCenter.X();
1416 tools::Long nCenterY = rCenter.Y();
1417
1418 for( sal_uInt16 i = 0, nCount = mpImplPolygon->mnPoints; i < nCount; i++ )
1419 {
1420 Point& rPt = mpImplPolygon->mxPointAry[ i ];
1421
1422 const tools::Long nX = rPt.X() - nCenterX;
1423 const tools::Long nY = rPt.Y() - nCenterY;
1424 rPt.setX( FRound( fCos * nX + fSin * nY ) + nCenterX );
1425 rPt.setY( - FRound( fSin * nX - fCos * nY ) + nCenterY );
1426 }
1427 }
1428
Clip(const tools::Rectangle & rRect)1429 void Polygon::Clip( const tools::Rectangle& rRect )
1430 {
1431 // This algorithm is broken for bezier curves, they would get converted to lines.
1432 // Use PolyPolygon::Clip().
1433 assert( !HasFlags());
1434
1435 // #105251# Justify rect before edge filtering
1436 tools::Rectangle aJustifiedRect( rRect );
1437 aJustifiedRect.Justify();
1438
1439 sal_uInt16 nSourceSize = mpImplPolygon->mnPoints;
1440 ImplPolygonPointFilter aPolygon( nSourceSize );
1441 ImplEdgePointFilter aHorzFilter( EDGE_HORZ, aJustifiedRect.Left(), aJustifiedRect.Right(),
1442 aPolygon );
1443 ImplEdgePointFilter aVertFilter( EDGE_VERT, aJustifiedRect.Top(), aJustifiedRect.Bottom(),
1444 aHorzFilter );
1445
1446 for ( sal_uInt16 i = 0; i < nSourceSize; i++ )
1447 aVertFilter.Input( mpImplPolygon->mxPointAry[i] );
1448 if ( aVertFilter.IsPolygon() )
1449 aVertFilter.LastPoint();
1450 else
1451 aPolygon.LastPoint();
1452
1453 mpImplPolygon = ImplType(aPolygon.get());
1454 }
1455
GetBoundRect() const1456 tools::Rectangle Polygon::GetBoundRect() const
1457 {
1458 // Removing the assert. Bezier curves have the attribute that each single
1459 // curve segment defined by four points can not exit the four-point polygon
1460 // defined by that points. This allows to say that the curve segment can also
1461 // never leave the Range of its defining points.
1462 // The result is that Polygon::GetBoundRect() may not create the minimal
1463 // BoundRect of the Polygon (to get that, use basegfx::B2DPolygon classes),
1464 // but will always create a valid BoundRect, at least as long as this method
1465 // 'blindly' travels over all points, including control points.
1466
1467 // DBG_ASSERT( !mpImplPolygon->mxFlagAry.get(), "GetBoundRect could fail with beziers!" );
1468
1469 sal_uInt16 nCount = mpImplPolygon->mnPoints;
1470 if( ! nCount )
1471 return tools::Rectangle();
1472
1473 tools::Long nXMin, nXMax, nYMin, nYMax;
1474
1475 const Point& pFirstPt = mpImplPolygon->mxPointAry[0];
1476 nXMin = nXMax = pFirstPt.X();
1477 nYMin = nYMax = pFirstPt.Y();
1478
1479 for ( sal_uInt16 i = 0; i < nCount; i++ )
1480 {
1481 const Point& rPt = mpImplPolygon->mxPointAry[i];
1482
1483 if (rPt.X() < nXMin)
1484 nXMin = rPt.X();
1485 if (rPt.X() > nXMax)
1486 nXMax = rPt.X();
1487 if (rPt.Y() < nYMin)
1488 nYMin = rPt.Y();
1489 if (rPt.Y() > nYMax)
1490 nYMax = rPt.Y();
1491 }
1492
1493 return tools::Rectangle( nXMin, nYMin, nXMax, nYMax );
1494 }
1495
IsInside(const Point & rPoint) const1496 bool Polygon::IsInside( const Point& rPoint ) const
1497 {
1498 DBG_ASSERT( !mpImplPolygon->mxFlagAry, "IsInside could fail with beziers!" );
1499
1500 const tools::Rectangle aBound( GetBoundRect() );
1501 const Line aLine( rPoint, Point( aBound.Right() + 100, rPoint.Y() ) );
1502 sal_uInt16 nCount = mpImplPolygon->mnPoints;
1503 sal_uInt16 nPCounter = 0;
1504
1505 if ( ( nCount > 2 ) && aBound.IsInside( rPoint ) )
1506 {
1507 Point aPt1( mpImplPolygon->mxPointAry[ 0 ] );
1508 Point aIntersection;
1509 Point aLastIntersection;
1510
1511 while ( ( aPt1 == mpImplPolygon->mxPointAry[ nCount - 1 ] ) && ( nCount > 3 ) )
1512 nCount--;
1513
1514 for ( sal_uInt16 i = 1; i <= nCount; i++ )
1515 {
1516 const Point& rPt2 = mpImplPolygon->mxPointAry[ ( i < nCount ) ? i : 0 ];
1517
1518 if ( aLine.Intersection( Line( aPt1, rPt2 ), aIntersection ) )
1519 {
1520 // This avoids insertion of double intersections
1521 if ( nPCounter )
1522 {
1523 if ( aIntersection != aLastIntersection )
1524 {
1525 aLastIntersection = aIntersection;
1526 nPCounter++;
1527 }
1528 }
1529 else
1530 {
1531 aLastIntersection = aIntersection;
1532 nPCounter++;
1533 }
1534 }
1535
1536 aPt1 = rPt2;
1537 }
1538 }
1539
1540 // is inside, if number of intersection points is odd
1541 return ( ( nPCounter & 1 ) == 1 );
1542 }
1543
Insert(sal_uInt16 nPos,const Point & rPt)1544 void Polygon::Insert( sal_uInt16 nPos, const Point& rPt )
1545 {
1546 if( nPos >= mpImplPolygon->mnPoints )
1547 nPos = mpImplPolygon->mnPoints;
1548
1549 if (mpImplPolygon->ImplSplit(nPos, 1))
1550 mpImplPolygon->mxPointAry[ nPos ] = rPt;
1551 }
1552
Insert(sal_uInt16 nPos,const tools::Polygon & rPoly)1553 void Polygon::Insert( sal_uInt16 nPos, const tools::Polygon& rPoly )
1554 {
1555 const sal_uInt16 nInsertCount = rPoly.mpImplPolygon->mnPoints;
1556
1557 if( nInsertCount )
1558 {
1559 if( nPos >= mpImplPolygon->mnPoints )
1560 nPos = mpImplPolygon->mnPoints;
1561
1562 if (rPoly.mpImplPolygon->mxFlagAry)
1563 mpImplPolygon->ImplCreateFlagArray();
1564
1565 mpImplPolygon->ImplSplit( nPos, nInsertCount, rPoly.mpImplPolygon.get() );
1566 }
1567 }
1568
operator [](sal_uInt16 nPos)1569 Point& Polygon::operator[]( sal_uInt16 nPos )
1570 {
1571 DBG_ASSERT( nPos < mpImplPolygon->mnPoints, "Polygon::[]: nPos >= nPoints" );
1572
1573 return mpImplPolygon->mxPointAry[nPos];
1574 }
1575
operator =(const tools::Polygon & rPoly)1576 tools::Polygon& Polygon::operator=( const tools::Polygon& rPoly )
1577 {
1578 mpImplPolygon = rPoly.mpImplPolygon;
1579 return *this;
1580 }
1581
operator =(tools::Polygon && rPoly)1582 tools::Polygon& Polygon::operator=( tools::Polygon&& rPoly ) noexcept
1583 {
1584 mpImplPolygon = std::move(rPoly.mpImplPolygon);
1585 return *this;
1586 }
1587
operator ==(const tools::Polygon & rPoly) const1588 bool Polygon::operator==( const tools::Polygon& rPoly ) const
1589 {
1590 return (mpImplPolygon == rPoly.mpImplPolygon);
1591 }
1592
IsEqual(const tools::Polygon & rPoly) const1593 bool Polygon::IsEqual( const tools::Polygon& rPoly ) const
1594 {
1595 bool bIsEqual = true;
1596 sal_uInt16 i;
1597 if ( GetSize() != rPoly.GetSize() )
1598 bIsEqual = false;
1599 else
1600 {
1601 for ( i = 0; i < GetSize(); i++ )
1602 {
1603 if ( ( GetPoint( i ) != rPoly.GetPoint( i ) ) ||
1604 ( GetFlags( i ) != rPoly.GetFlags( i ) ) )
1605 {
1606 bIsEqual = false;
1607 break;
1608 }
1609 }
1610 }
1611 return bIsEqual;
1612 }
1613
ReadPolygon(SvStream & rIStream,tools::Polygon & rPoly)1614 SvStream& ReadPolygon( SvStream& rIStream, tools::Polygon& rPoly )
1615 {
1616 sal_uInt16 nPoints(0);
1617
1618 // read all points and create array
1619 rIStream.ReadUInt16( nPoints );
1620
1621 const size_t nMaxRecordsPossible = rIStream.remainingSize() / (2 * sizeof(sal_Int32));
1622 if (nPoints > nMaxRecordsPossible)
1623 {
1624 SAL_WARN("tools", "Polygon claims " << nPoints << " records, but only " << nMaxRecordsPossible << " possible");
1625 nPoints = nMaxRecordsPossible;
1626 }
1627
1628 rPoly.mpImplPolygon->ImplSetSize( nPoints, false );
1629
1630 for (sal_uInt16 i = 0; i < nPoints; i++)
1631 {
1632 sal_Int32 nTmpX(0), nTmpY(0);
1633 rIStream.ReadInt32(nTmpX).ReadInt32(nTmpY);
1634 rPoly.mpImplPolygon->mxPointAry[i].setX(nTmpX);
1635 rPoly.mpImplPolygon->mxPointAry[i].setY(nTmpY);
1636 }
1637
1638 return rIStream;
1639 }
1640
WritePolygon(SvStream & rOStream,const tools::Polygon & rPoly)1641 SvStream& WritePolygon( SvStream& rOStream, const tools::Polygon& rPoly )
1642 {
1643 sal_uInt16 nPoints = rPoly.GetSize();
1644
1645 // Write number of points
1646 rOStream.WriteUInt16( nPoints );
1647
1648 for (sal_uInt16 i = 0; i < nPoints; i++)
1649 {
1650 rOStream.WriteInt32(rPoly.mpImplPolygon->mxPointAry[i].X())
1651 .WriteInt32(rPoly.mpImplPolygon->mxPointAry[i].Y());
1652 }
1653
1654 return rOStream;
1655 }
1656
ImplRead(SvStream & rIStream)1657 void Polygon::ImplRead( SvStream& rIStream )
1658 {
1659 sal_uInt8 bHasPolyFlags(0);
1660
1661 ReadPolygon( rIStream, *this );
1662 rIStream.ReadUChar( bHasPolyFlags );
1663
1664 if ( bHasPolyFlags )
1665 {
1666 mpImplPolygon->mxFlagAry.reset(new PolyFlags[mpImplPolygon->mnPoints]);
1667 rIStream.ReadBytes(mpImplPolygon->mxFlagAry.get(), mpImplPolygon->mnPoints);
1668 }
1669 }
1670
Read(SvStream & rIStream)1671 void Polygon::Read( SvStream& rIStream )
1672 {
1673 VersionCompatRead aCompat(rIStream);
1674
1675 ImplRead( rIStream );
1676 }
1677
ImplWrite(SvStream & rOStream) const1678 void Polygon::ImplWrite( SvStream& rOStream ) const
1679 {
1680 bool bHasPolyFlags(mpImplPolygon->mxFlagAry);
1681 WritePolygon( rOStream, *this );
1682 rOStream.WriteBool(bHasPolyFlags);
1683
1684 if ( bHasPolyFlags )
1685 rOStream.WriteBytes(mpImplPolygon->mxFlagAry.get(), mpImplPolygon->mnPoints);
1686 }
1687
Write(SvStream & rOStream) const1688 void Polygon::Write( SvStream& rOStream ) const
1689 {
1690 VersionCompatWrite aCompat(rOStream, 1);
1691
1692 ImplWrite( rOStream );
1693 }
1694
1695 // #i74631#/#i115917# numerical correction method for B2DPolygon
impCorrectContinuity(basegfx::B2DPolygon & roPolygon,sal_uInt32 nIndex,PolyFlags nCFlag)1696 static void impCorrectContinuity(basegfx::B2DPolygon& roPolygon, sal_uInt32 nIndex, PolyFlags nCFlag)
1697 {
1698 const sal_uInt32 nPointCount(roPolygon.count());
1699 OSL_ENSURE(nIndex < nPointCount, "impCorrectContinuity: index access out of range (!)");
1700
1701 if(nIndex >= nPointCount || (PolyFlags::Smooth != nCFlag && PolyFlags::Symmetric != nCFlag))
1702 return;
1703
1704 if(!roPolygon.isPrevControlPointUsed(nIndex) || !roPolygon.isNextControlPointUsed(nIndex))
1705 return;
1706
1707 // #i115917# Patch from osnola (modified, thanks for showing the problem)
1708
1709 // The correction is needed because an integer polygon with control points
1710 // is converted to double precision. When C1 or C2 is used the involved vectors
1711 // may not have the same directions/lengths since these come from integer coordinates
1712 // and may have been snapped to different nearest integer coordinates. The snap error
1713 // is in the range of +-1 in y and y, thus 0.0 <= error <= sqrt(2.0). Nonetheless,
1714 // it needs to be corrected to be able to detect the continuity in this points
1715 // correctly.
1716
1717 // We only have the integer data here (already in double precision form, but no mantissa
1718 // used), so the best correction is to use:
1719
1720 // for C1: The longest vector since it potentially has best preserved the original vector.
1721 // Even better the sum of the vectors, weighted by their length. This gives the
1722 // normal vector addition to get the vector itself, lengths need to be preserved.
1723 // for C2: The mediated vector(s) since both should be the same, but mirrored
1724
1725 // extract the point and vectors
1726 const basegfx::B2DPoint aPoint(roPolygon.getB2DPoint(nIndex));
1727 const basegfx::B2DVector aNext(roPolygon.getNextControlPoint(nIndex) - aPoint);
1728 const basegfx::B2DVector aPrev(aPoint - roPolygon.getPrevControlPoint(nIndex));
1729
1730 // calculate common direction vector, normalize
1731 const basegfx::B2DVector aDirection(aNext + aPrev);
1732 const double fDirectionLen = aDirection.getLength();
1733 if (fDirectionLen == 0.0)
1734 return;
1735
1736 if (PolyFlags::Smooth == nCFlag)
1737 {
1738 // C1: apply common direction vector, preserve individual lengths
1739 const double fInvDirectionLen(1.0 / fDirectionLen);
1740 roPolygon.setNextControlPoint(nIndex, basegfx::B2DPoint(aPoint + (aDirection * (aNext.getLength() * fInvDirectionLen))));
1741 roPolygon.setPrevControlPoint(nIndex, basegfx::B2DPoint(aPoint - (aDirection * (aPrev.getLength() * fInvDirectionLen))));
1742 }
1743 else // PolyFlags::Symmetric
1744 {
1745 // C2: get mediated length. Taking half of the unnormalized direction would be
1746 // an approximation, but not correct.
1747 const double fMedLength((aNext.getLength() + aPrev.getLength()) * (0.5 / fDirectionLen));
1748 const basegfx::B2DVector aScaledDirection(aDirection * fMedLength);
1749
1750 // Bring Direction to correct length and apply
1751 roPolygon.setNextControlPoint(nIndex, basegfx::B2DPoint(aPoint + aScaledDirection));
1752 roPolygon.setPrevControlPoint(nIndex, basegfx::B2DPoint(aPoint - aScaledDirection));
1753 }
1754 }
1755
1756 // convert to basegfx::B2DPolygon and return
getB2DPolygon() const1757 basegfx::B2DPolygon Polygon::getB2DPolygon() const
1758 {
1759 basegfx::B2DPolygon aRetval;
1760 const sal_uInt16 nCount(mpImplPolygon->mnPoints);
1761
1762 if (nCount)
1763 {
1764 if (mpImplPolygon->mxFlagAry)
1765 {
1766 // handling for curves. Add start point
1767 const Point aStartPoint(mpImplPolygon->mxPointAry[0]);
1768 PolyFlags nPointFlag(mpImplPolygon->mxFlagAry[0]);
1769 aRetval.append(basegfx::B2DPoint(aStartPoint.X(), aStartPoint.Y()));
1770 Point aControlA, aControlB;
1771
1772 for(sal_uInt16 a(1); a < nCount;)
1773 {
1774 bool bControlA(false);
1775 bool bControlB(false);
1776
1777 if(PolyFlags::Control == mpImplPolygon->mxFlagAry[a])
1778 {
1779 aControlA = mpImplPolygon->mxPointAry[a++];
1780 bControlA = true;
1781 }
1782
1783 if(a < nCount && PolyFlags::Control == mpImplPolygon->mxFlagAry[a])
1784 {
1785 aControlB = mpImplPolygon->mxPointAry[a++];
1786 bControlB = true;
1787 }
1788
1789 // assert invalid polygons
1790 OSL_ENSURE(bControlA == bControlB, "Polygon::getB2DPolygon: Invalid source polygon (!)");
1791
1792 if(a < nCount)
1793 {
1794 const Point aEndPoint(mpImplPolygon->mxPointAry[a]);
1795
1796 if(bControlA)
1797 {
1798 // bezier edge, add
1799 aRetval.appendBezierSegment(
1800 basegfx::B2DPoint(aControlA.X(), aControlA.Y()),
1801 basegfx::B2DPoint(aControlB.X(), aControlB.Y()),
1802 basegfx::B2DPoint(aEndPoint.X(), aEndPoint.Y()));
1803
1804 impCorrectContinuity(aRetval, aRetval.count() - 2, nPointFlag);
1805 }
1806 else
1807 {
1808 // no bezier edge, add end point
1809 aRetval.append(basegfx::B2DPoint(aEndPoint.X(), aEndPoint.Y()));
1810 }
1811
1812 nPointFlag = mpImplPolygon->mxFlagAry[a++];
1813 }
1814 }
1815
1816 // if exist, remove double first/last points, set closed and correct control points
1817 basegfx::utils::checkClosed(aRetval);
1818
1819 if(aRetval.isClosed())
1820 {
1821 // closeWithGeometryChange did really close, so last point(s) were removed.
1822 // Correct the continuity in the changed point
1823 impCorrectContinuity(aRetval, 0, mpImplPolygon->mxFlagAry[0]);
1824 }
1825 }
1826 else
1827 {
1828 // extra handling for non-curves (most-used case) for speedup
1829 for(sal_uInt16 a(0); a < nCount; a++)
1830 {
1831 // get point and add
1832 const Point aPoint(mpImplPolygon->mxPointAry[a]);
1833 aRetval.append(basegfx::B2DPoint(aPoint.X(), aPoint.Y()));
1834 }
1835
1836 // set closed flag
1837 basegfx::utils::checkClosed(aRetval);
1838 }
1839 }
1840
1841 return aRetval;
1842 }
1843
Polygon(const basegfx::B2DPolygon & rPolygon)1844 Polygon::Polygon(const basegfx::B2DPolygon& rPolygon) : mpImplPolygon(ImplPolygon(rPolygon))
1845 {
1846 }
1847
1848 } // namespace tools
1849
1850 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
1851