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