?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
tdf#130857 qt weld: Support mail merge "Server Auth" dialog
[LibreOffice.git] / basegfx / source / polygon / b2dpolygontools.cxx
blobf1b9c169f3455987d081142fc63082822ae5fcc1
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 #include <numeric>
20 #include <algorithm>
21 #include <stack>
22
23 #include <basegfx/numeric/ftools.hxx>
24 #include <basegfx/polygon/b2dpolygontools.hxx>
25 #include <osl/diagnose.h>
26 #include <rtl/math.hxx>
27 #include <sal/log.hxx>
28 #include <basegfx/polygon/b2dpolygon.hxx>
29 #include <basegfx/polygon/b2dpolypolygon.hxx>
30 #include <basegfx/range/b2drange.hxx>
31 #include <basegfx/curve/b2dcubicbezier.hxx>
32 #include <basegfx/point/b3dpoint.hxx>
33 #include <basegfx/matrix/b3dhommatrix.hxx>
34 #include <basegfx/matrix/b2dhommatrix.hxx>
35 #include <basegfx/curve/b2dbeziertools.hxx>
36 #include <basegfx/matrix/b2dhommatrixtools.hxx>
37
38 // #i37443#
39 #define ANGLE_BOUND_START_VALUE (2.25)
40 #define ANGLE_BOUND_MINIMUM_VALUE (0.1)
41 #define STEPSPERQUARTER (3)
42
43 namespace basegfx::utils
44 {
45 void openWithGeometryChange(B2DPolygon& rCandidate)
46 {
47 if(!rCandidate.isClosed())
48 return;
49
50 if(rCandidate.count())
51 {
52 rCandidate.append(rCandidate.getB2DPoint(0));
53
54 if(rCandidate.areControlPointsUsed() && rCandidate.isPrevControlPointUsed(0))
55 {
56 rCandidate.setPrevControlPoint(rCandidate.count() - 1, rCandidate.getPrevControlPoint(0));
57 rCandidate.resetPrevControlPoint(0);
58 }
59 }
60
61 rCandidate.setClosed(false);
62 }
63
64 void closeWithGeometryChange(B2DPolygon& rCandidate)
65 {
66 if(rCandidate.isClosed())
67 return;
68
69 while(rCandidate.count() > 1 && rCandidate.getB2DPoint(0) == rCandidate.getB2DPoint(rCandidate.count() - 1))
70 {
71 if(rCandidate.areControlPointsUsed() && rCandidate.isPrevControlPointUsed(rCandidate.count() - 1))
72 {
73 rCandidate.setPrevControlPoint(0, rCandidate.getPrevControlPoint(rCandidate.count() - 1));
74 }
75
76 rCandidate.remove(rCandidate.count() - 1);
77 }
78
79 rCandidate.setClosed(true);
80 }
81
82 void checkClosed(B2DPolygon& rCandidate)
83 {
84 // #i80172# Removed unnecessary assertion
85 // OSL_ENSURE(!rCandidate.isClosed(), "checkClosed: already closed (!)");
86
87 if(rCandidate.count() > 1 && rCandidate.getB2DPoint(0) == rCandidate.getB2DPoint(rCandidate.count() - 1))
88 {
89 closeWithGeometryChange(rCandidate);
90 }
91 }
92
93 // Get successor and predecessor indices. Returning the same index means there
94 // is none. Same for successor.
95 sal_uInt32 getIndexOfPredecessor(sal_uInt32 nIndex, const B2DPolygon& rCandidate)
96 {
97 OSL_ENSURE(nIndex < rCandidate.count(), "getIndexOfPredecessor: Access to polygon out of range (!)");
98
99 if(nIndex)
100 {
101 return nIndex - 1;
102 }
103 else if(rCandidate.count())
104 {
105 return rCandidate.count() - 1;
106 }
107 else
108 {
109 return nIndex;
110 }
111 }
112
113 sal_uInt32 getIndexOfSuccessor(sal_uInt32 nIndex, const B2DPolygon& rCandidate)
114 {
115 OSL_ENSURE(nIndex < rCandidate.count(), "getIndexOfPredecessor: Access to polygon out of range (!)");
116
117 if(nIndex + 1 < rCandidate.count())
118 {
119 return nIndex + 1;
120 }
121 else if(nIndex + 1 == rCandidate.count())
122 {
123 return 0;
124 }
125 else
126 {
127 return nIndex;
128 }
129 }
130
131 B2VectorOrientation getOrientation(const B2DPolygon& rCandidate)
132 {
133 B2VectorOrientation eRetval(B2VectorOrientation::Neutral);
134
135 if(rCandidate.count() > 2 || rCandidate.areControlPointsUsed())
136 {
137 const double fSignedArea(getSignedArea(rCandidate));
138
139 if(fTools::equalZero(fSignedArea))
140 {
141 // B2VectorOrientation::Neutral, already set
142 }
143 if(fSignedArea > 0.0)
144 {
145 eRetval = B2VectorOrientation::Positive;
146 }
147 else if(fSignedArea < 0.0)
148 {
149 eRetval = B2VectorOrientation::Negative;
150 }
151 }
152
153 return eRetval;
154 }
155
156 B2VectorContinuity getContinuityInPoint(const B2DPolygon& rCandidate, sal_uInt32 nIndex)
157 {
158 return rCandidate.getContinuityInPoint(nIndex);
159 }
160
161 B2DPolygon adaptiveSubdivideByDistance(const B2DPolygon& rCandidate, double fDistanceBound, int nRecurseLimit)
162 {
163 if(rCandidate.areControlPointsUsed())
164 {
165 const sal_uInt32 nPointCount(rCandidate.count());
166 B2DPolygon aRetval;
167
168 if(nPointCount)
169 {
170 // prepare edge-oriented loop
171 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1);
172 B2DCubicBezier aBezier;
173 aBezier.setStartPoint(rCandidate.getB2DPoint(0));
174
175 // perf: try to avoid too many reallocations by guessing the result's pointcount
176 aRetval.reserve(nPointCount*4);
177
178 // add start point (always)
179 aRetval.append(aBezier.getStartPoint());
180
181 for(sal_uInt32 a(0); a < nEdgeCount; a++)
182 {
183 // get next and control points
184 const sal_uInt32 nNextIndex((a + 1) % nPointCount);
185 aBezier.setEndPoint(rCandidate.getB2DPoint(nNextIndex));
186 aBezier.setControlPointA(rCandidate.getNextControlPoint(a));
187 aBezier.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex));
188 aBezier.testAndSolveTrivialBezier();
189
190 if(aBezier.isBezier())
191 {
192 // add curved edge and generate DistanceBound
193 double fBound(0.0);
194
195 if(fDistanceBound == 0.0)
196 {
197 // If not set, use B2DCubicBezier functionality to guess a rough value
198 const double fRoughLength((aBezier.getEdgeLength() + aBezier.getControlPolygonLength()) / 2.0);
199
200 // take 1/100th of the rough curve length
201 fBound = fRoughLength * 0.01;
202 }
203 else
204 {
205 // use given bound value
206 fBound = fDistanceBound;
207 }
208
209 // make sure bound value is not too small. The base units are 1/100th mm, thus
210 // just make sure it's not smaller then 1/100th of that
211 if(fBound < 0.01)
212 {
213 fBound = 0.01;
214 }
215
216 // call adaptive subdivide which adds edges to aRetval accordingly
217 aBezier.adaptiveSubdivideByDistance(aRetval, fBound, nRecurseLimit);
218 }
219 else
220 {
221 // add non-curved edge
222 aRetval.append(aBezier.getEndPoint());
223 }
224
225 // prepare next step
226 aBezier.setStartPoint(aBezier.getEndPoint());
227 }
228
229 if(rCandidate.isClosed())
230 {
231 // set closed flag and correct last point (which is added double now).
232 closeWithGeometryChange(aRetval);
233 }
234 }
235
236 return aRetval;
237 }
238 else
239 {
240 return rCandidate;
241 }
242 }
243
244 B2DPolygon adaptiveSubdivideByAngle(const B2DPolygon& rCandidate, double fAngleBound)
245 {
246 if(rCandidate.areControlPointsUsed())
247 {
248 const sal_uInt32 nPointCount(rCandidate.count());
249 B2DPolygon aRetval;
250
251 if(nPointCount)
252 {
253 // prepare edge-oriented loop
254 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1);
255 B2DCubicBezier aBezier;
256 aBezier.setStartPoint(rCandidate.getB2DPoint(0));
257
258 // perf: try to avoid too many reallocations by guessing the result's pointcount
259 aRetval.reserve(nPointCount*4);
260
261 // add start point (always)
262 aRetval.append(aBezier.getStartPoint());
263
264 // #i37443# prepare convenient AngleBound if none was given
265 if(fAngleBound == 0.0)
266 {
267 fAngleBound = ANGLE_BOUND_START_VALUE;
268 }
269 else if(fTools::less(fAngleBound, ANGLE_BOUND_MINIMUM_VALUE))
270 {
271 fAngleBound = 0.1;
272 }
273
274 for(sal_uInt32 a(0); a < nEdgeCount; a++)
275 {
276 // get next and control points
277 const sal_uInt32 nNextIndex((a + 1) % nPointCount);
278 aBezier.setEndPoint(rCandidate.getB2DPoint(nNextIndex));
279 aBezier.setControlPointA(rCandidate.getNextControlPoint(a));
280 aBezier.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex));
281 aBezier.testAndSolveTrivialBezier();
282
283 if(aBezier.isBezier())
284 {
285 // call adaptive subdivide
286 aBezier.adaptiveSubdivideByAngle(aRetval, fAngleBound);
287 }
288 else
289 {
290 // add non-curved edge
291 aRetval.append(aBezier.getEndPoint());
292 }
293
294 // prepare next step
295 aBezier.setStartPoint(aBezier.getEndPoint());
296 }
297
298 if(rCandidate.isClosed())
299 {
300 // set closed flag and correct last point (which is added double now).
301 closeWithGeometryChange(aRetval);
302 }
303 }
304
305 return aRetval;
306 }
307 else
308 {
309 return rCandidate;
310 }
311 }
312
313 bool isInside(const B2DPolygon& rCandidate, const B2DPoint& rPoint, bool bWithBorder)
314 {
315 const B2DPolygon aCandidate(rCandidate.areControlPointsUsed() ? rCandidate.getDefaultAdaptiveSubdivision() : rCandidate);
316
317 if(bWithBorder && isPointOnPolygon(aCandidate, rPoint))
318 {
319 return true;
320 }
321 else
322 {
323 bool bRetval(false);
324 const sal_uInt32 nPointCount(aCandidate.count());
325
326 if(nPointCount)
327 {
328 B2DPoint aCurrentPoint(aCandidate.getB2DPoint(nPointCount - 1));
329
330 for(sal_uInt32 a(0); a < nPointCount; a++)
331 {
332 const B2DPoint aPreviousPoint(aCurrentPoint);
333 aCurrentPoint = aCandidate.getB2DPoint(a);
334
335 // cross-over in Y? tdf#130150 use full precision, no need for epsilon
336 const bool bCompYA(aPreviousPoint.getY() > rPoint.getY());
337 const bool bCompYB(aCurrentPoint.getY() > rPoint.getY());
338
339 if(bCompYA != bCompYB)
340 {
341 // cross-over in X? tdf#130150 use full precision, no need for epsilon
342 const bool bCompXA(aPreviousPoint.getX() > rPoint.getX());
343 const bool bCompXB(aCurrentPoint.getX() > rPoint.getX());
344
345 if(bCompXA == bCompXB)
346 {
347 if(bCompXA)
348 {
349 bRetval = !bRetval;
350 }
351 }
352 else
353 {
354 const double fCompare(
355 aCurrentPoint.getX() - (aCurrentPoint.getY() - rPoint.getY()) *
356 (aPreviousPoint.getX() - aCurrentPoint.getX()) /
357 (aPreviousPoint.getY() - aCurrentPoint.getY()));
358
359 // tdf#130150 use full precision, no need for epsilon
360 if(fCompare > rPoint.getX())
361 {
362 bRetval = !bRetval;
363 }
364 }
365 }
366 }
367 }
368
369 return bRetval;
370 }
371 }
372
373 bool isInside(const B2DPolygon& rCandidate, const B2DPolygon& rPolygon, bool bWithBorder)
374 {
375 const B2DPolygon aCandidate(rCandidate.areControlPointsUsed() ? rCandidate.getDefaultAdaptiveSubdivision() : rCandidate);
376 const B2DPolygon aPolygon(rPolygon.areControlPointsUsed() ? rPolygon.getDefaultAdaptiveSubdivision() : rPolygon);
377 const sal_uInt32 nPointCount(aPolygon.count());
378
379 for(sal_uInt32 a(0); a < nPointCount; a++)
380 {
381 const B2DPoint aTestPoint(aPolygon.getB2DPoint(a));
382
383 if(!isInside(aCandidate, aTestPoint, bWithBorder))
384 {
385 return false;
386 }
387 }
388
389 return true;
390 }
391
392 B2DRange getRange(const B2DPolygon& rCandidate)
393 {
394 // changed to use internally buffered version at B2DPolygon
395 return rCandidate.getB2DRange();
396 }
397
398 double getSignedArea(const B2DPolygon& rCandidate)
399 {
400 const B2DPolygon aCandidate(rCandidate.areControlPointsUsed() ? rCandidate.getDefaultAdaptiveSubdivision() : rCandidate);
401 double fRetval(0.0);
402 const sal_uInt32 nPointCount(aCandidate.count());
403
404 if(nPointCount > 2)
405 {
406 for(sal_uInt32 a(0); a < nPointCount; a++)
407 {
408 const B2DPoint aPreviousPoint(aCandidate.getB2DPoint((!a) ? nPointCount - 1 : a - 1));
409 const B2DPoint aCurrentPoint(aCandidate.getB2DPoint(a));
410
411 fRetval += aPreviousPoint.getX() * aCurrentPoint.getY();
412 fRetval -= aPreviousPoint.getY() * aCurrentPoint.getX();
413 }
414
415 // correct to zero if small enough. Also test the quadratic
416 // of the result since the precision is near quadratic due to
417 // the algorithm
418 if(fTools::equalZero(fRetval) || fTools::equalZero(fRetval * fRetval))
419 {
420 fRetval = 0.0;
421 }
422 }
423
424 return fRetval;
425 }
426
427 double getArea(const B2DPolygon& rCandidate)
428 {
429 double fRetval(0.0);
430
431 if(rCandidate.count() > 2 || rCandidate.areControlPointsUsed())
432 {
433 fRetval = getSignedArea(rCandidate);
434 const double fZero(0.0);
435
436 if(fTools::less(fRetval, fZero))
437 {
438 fRetval = -fRetval;
439 }
440 }
441
442 return fRetval;
443 }
444
445 double getEdgeLength(const B2DPolygon& rCandidate, sal_uInt32 nIndex)
446 {
447 const sal_uInt32 nPointCount(rCandidate.count());
448 OSL_ENSURE(nIndex < nPointCount, "getEdgeLength: Access to polygon out of range (!)");
449 double fRetval(0.0);
450
451 if(nPointCount)
452 {
453 const sal_uInt32 nNextIndex((nIndex + 1) % nPointCount);
454
455 if(rCandidate.areControlPointsUsed())
456 {
457 B2DCubicBezier aEdge;
458
459 aEdge.setStartPoint(rCandidate.getB2DPoint(nIndex));
460 aEdge.setControlPointA(rCandidate.getNextControlPoint(nIndex));
461 aEdge.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex));
462 aEdge.setEndPoint(rCandidate.getB2DPoint(nNextIndex));
463
464 fRetval = aEdge.getLength();
465 }
466 else
467 {
468 const B2DPoint aCurrent(rCandidate.getB2DPoint(nIndex));
469 const B2DPoint aNext(rCandidate.getB2DPoint(nNextIndex));
470
471 fRetval = B2DVector(aNext - aCurrent).getLength();
472 }
473 }
474
475 return fRetval;
476 }
477
478 double getLength(const B2DPolygon& rCandidate)
479 {
480 double fRetval(0.0);
481 const sal_uInt32 nPointCount(rCandidate.count());
482
483 if(nPointCount)
484 {
485 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1);
486
487 if(rCandidate.areControlPointsUsed())
488 {
489 B2DCubicBezier aEdge;
490 aEdge.setStartPoint(rCandidate.getB2DPoint(0));
491
492 for(sal_uInt32 a(0); a < nEdgeCount; a++)
493 {
494 const sal_uInt32 nNextIndex((a + 1) % nPointCount);
495 aEdge.setControlPointA(rCandidate.getNextControlPoint(a));
496 aEdge.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex));
497 aEdge.setEndPoint(rCandidate.getB2DPoint(nNextIndex));
498
499 fRetval += aEdge.getLength();
500 aEdge.setStartPoint(aEdge.getEndPoint());
501 }
502 }
503 else
504 {
505 B2DPoint aCurrent(rCandidate.getB2DPoint(0));
506
507 for(sal_uInt32 a(0); a < nEdgeCount; a++)
508 {
509 const sal_uInt32 nNextIndex((a + 1) % nPointCount);
510 const B2DPoint aNext(rCandidate.getB2DPoint(nNextIndex));
511
512 fRetval += B2DVector(aNext - aCurrent).getLength();
513 aCurrent = aNext;
514 }
515 }
516 }
517
518 return fRetval;
519 }
520
521 B2DPoint getPositionAbsolute(const B2DPolygon& rCandidate, double fDistance, double fLength)
522 {
523 B2DPoint aRetval;
524 const sal_uInt32 nPointCount(rCandidate.count());
525
526 if( nPointCount == 1 )
527 {
528 // only one point (i.e. no edge) - simply take that point
529 aRetval = rCandidate.getB2DPoint(0);
530 }
531 else if(nPointCount > 1)
532 {
533 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1);
534 sal_uInt32 nIndex(0);
535 bool bIndexDone(false);
536
537 // get length if not given
538 if(fTools::equalZero(fLength))
539 {
540 fLength = getLength(rCandidate);
541 }
542
543 if (fDistance < 0.0)
544 {
545 // handle fDistance < 0.0
546 if(rCandidate.isClosed())
547 {
548 // if fDistance < 0.0 increment with multiple of fLength
549 sal_uInt32 nCount(sal_uInt32(-fDistance / fLength));
550 fDistance += double(nCount + 1) * fLength;
551 }
552 else
553 {
554 // crop to polygon start
555 fDistance = 0.0;
556 bIndexDone = true;
557 }
558 }
559 else if(fTools::moreOrEqual(fDistance, fLength))
560 {
561 // handle fDistance >= fLength
562 if(rCandidate.isClosed())
563 {
564 // if fDistance >= fLength decrement with multiple of fLength
565 sal_uInt32 nCount(sal_uInt32(fDistance / fLength));
566 fDistance -= static_cast<double>(nCount) * fLength;
567 }
568 else
569 {
570 // crop to polygon end
571 fDistance = 0.0;
572 nIndex = nEdgeCount;
573 bIndexDone = true;
574 }
575 }
576
577 // look for correct index. fDistance is now [0.0 .. fLength[
578 double fEdgeLength(getEdgeLength(rCandidate, nIndex));
579
580 while(!bIndexDone)
581 {
582 // edge found must be on the half-open range
583 // [0,fEdgeLength).
584 // Note that in theory, we cannot move beyond
585 // the last polygon point, since fDistance>=fLength
586 // is checked above. Unfortunately, with floating-
587 // point calculations, this case might happen.
588 // Handled by nIndex check below
589 if (nIndex+1 < nEdgeCount && fTools::moreOrEqual(fDistance, fEdgeLength))
590 {
591 // go to next edge
592 fDistance -= fEdgeLength;
593 fEdgeLength = getEdgeLength(rCandidate, ++nIndex);
594 }
595 else
596 {
597 // it's on this edge, stop
598 bIndexDone = true;
599 }
600 }
601
602 // get the point using nIndex
603 aRetval = rCandidate.getB2DPoint(nIndex);
604
605 // if fDistance != 0.0, move that length on the edge. The edge
606 // length is in fEdgeLength.
607 if(!fTools::equalZero(fDistance))
608 {
609 if(fTools::moreOrEqual(fDistance, fEdgeLength))
610 {
611 // end point of chosen edge
612 const sal_uInt32 nNextIndex((nIndex + 1) % nPointCount);
613 aRetval = rCandidate.getB2DPoint(nNextIndex);
614 }
615 else if(fTools::equalZero(fDistance))
616 {
617 // start point of chosen edge
618 }
619 else
620 {
621 // inside edge
622 const sal_uInt32 nNextIndex((nIndex + 1) % nPointCount);
623 const B2DPoint aNextPoint(rCandidate.getB2DPoint(nNextIndex));
624 bool bDone(false);
625
626 // add calculated average value to the return value
627 if(rCandidate.areControlPointsUsed())
628 {
629 // get as bezier segment
630 const B2DCubicBezier aBezierSegment(
631 aRetval, rCandidate.getNextControlPoint(nIndex),
632 rCandidate.getPrevControlPoint(nNextIndex), aNextPoint);
633
634 if(aBezierSegment.isBezier())
635 {
636 // use B2DCubicBezierHelper to bridge the non-linear gap between
637 // length and bezier distances
638 const B2DCubicBezierHelper aBezierSegmentHelper(aBezierSegment);
639 const double fBezierDistance(aBezierSegmentHelper.distanceToRelative(fDistance));
640
641 aRetval = aBezierSegment.interpolatePoint(fBezierDistance);
642 bDone = true;
643 }
644 }
645
646 if(!bDone)
647 {
648 const double fRelativeInEdge(fDistance / fEdgeLength);
649 aRetval = interpolate(aRetval, aNextPoint, fRelativeInEdge);
650 }
651 }
652 }
653 }
654
655 return aRetval;
656 }
657
658 B2DPoint getPositionRelative(const B2DPolygon& rCandidate, double fDistance, double fLength)
659 {
660 // get length if not given
661 if(fTools::equalZero(fLength))
662 {
663 fLength = getLength(rCandidate);
664 }
665
666 // multiply fDistance with real length to get absolute position and
667 // use getPositionAbsolute
668 return getPositionAbsolute(rCandidate, fDistance * fLength, fLength);
669 }
670
671 B2DPolygon getSnippetAbsolute(const B2DPolygon& rCandidate, double fFrom, double fTo, double fLength)
672 {
673 const sal_uInt32 nPointCount(rCandidate.count());
674
675 if(nPointCount)
676 {
677 // get length if not given
678 if(fTools::equalZero(fLength))
679 {
680 fLength = getLength(rCandidate);
681 }
682
683 // test and correct fFrom
684 if (fFrom < 0.0)
685 {
686 fFrom = 0.0;
687 }
688
689 // test and correct fTo
690 if(fTools::more(fTo, fLength))
691 {
692 fTo = fLength;
693 }
694
695 // test and correct relationship of fFrom, fTo
696 if(fTools::more(fFrom, fTo))
697 {
698 fFrom = fTo = (fFrom + fTo) / 2.0;
699 }
700
701 if(fTools::equalZero(fFrom) && fTools::equal(fTo, fLength))
702 {
703 // no change, result is the whole polygon
704 return rCandidate;
705 }
706 else
707 {
708 B2DPolygon aRetval;
709 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1);
710 double fPositionOfStart(0.0);
711 bool bStartDone(false);
712 bool bEndDone(false);
713
714 for(sal_uInt32 a(0); !(bStartDone && bEndDone) && a < nEdgeCount; a++)
715 {
716 const double fEdgeLength(getEdgeLength(rCandidate, a));
717
718 if(!bStartDone)
719 {
720 if(fTools::equalZero(fFrom))
721 {
722 aRetval.append(rCandidate.getB2DPoint(a));
723
724 if(rCandidate.areControlPointsUsed())
725 {
726 aRetval.setNextControlPoint(aRetval.count() - 1, rCandidate.getNextControlPoint(a));
727 }
728
729 bStartDone = true;
730 }
731 else if(fTools::moreOrEqual(fFrom, fPositionOfStart) && fTools::less(fFrom, fPositionOfStart + fEdgeLength))
732 {
733 // calculate and add start point
734 if(fTools::equalZero(fEdgeLength))
735 {
736 aRetval.append(rCandidate.getB2DPoint(a));
737
738 if(rCandidate.areControlPointsUsed())
739 {
740 aRetval.setNextControlPoint(aRetval.count() - 1, rCandidate.getNextControlPoint(a));
741 }
742 }
743 else
744 {
745 const sal_uInt32 nNextIndex((a + 1) % nPointCount);
746 const B2DPoint aStart(rCandidate.getB2DPoint(a));
747 const B2DPoint aEnd(rCandidate.getB2DPoint(nNextIndex));
748 bool bDone(false);
749
750 if(rCandidate.areControlPointsUsed())
751 {
752 const B2DCubicBezier aBezierSegment(
753 aStart, rCandidate.getNextControlPoint(a),
754 rCandidate.getPrevControlPoint(nNextIndex), aEnd);
755
756 if(aBezierSegment.isBezier())
757 {
758 // use B2DCubicBezierHelper to bridge the non-linear gap between
759 // length and bezier distances
760 const B2DCubicBezierHelper aBezierSegmentHelper(aBezierSegment);
761 const double fBezierDistance(aBezierSegmentHelper.distanceToRelative(fFrom - fPositionOfStart));
762 B2DCubicBezier aRight;
763
764 aBezierSegment.split(fBezierDistance, nullptr, &aRight);
765 aRetval.append(aRight.getStartPoint());
766 aRetval.setNextControlPoint(aRetval.count() - 1, aRight.getControlPointA());
767 bDone = true;
768 }
769 }
770
771 if(!bDone)
772 {
773 const double fRelValue((fFrom - fPositionOfStart) / fEdgeLength);
774 aRetval.append(interpolate(aStart, aEnd, fRelValue));
775 }
776 }
777
778 bStartDone = true;
779
780 // if same point, end is done, too.
781 if(rtl::math::approxEqual(fFrom, fTo))
782 {
783 bEndDone = true;
784 }
785 }
786 }
787
788 if(!bEndDone && fTools::moreOrEqual(fTo, fPositionOfStart) && fTools::less(fTo, fPositionOfStart + fEdgeLength))
789 {
790 // calculate and add end point
791 if(fTools::equalZero(fEdgeLength))
792 {
793 const sal_uInt32 nNextIndex((a + 1) % nPointCount);
794 aRetval.append(rCandidate.getB2DPoint(nNextIndex));
795
796 if(rCandidate.areControlPointsUsed())
797 {
798 aRetval.setPrevControlPoint(aRetval.count() - 1, rCandidate.getPrevControlPoint(nNextIndex));
799 }
800 }
801 else
802 {
803 const sal_uInt32 nNextIndex((a + 1) % nPointCount);
804 const B2DPoint aStart(rCandidate.getB2DPoint(a));
805 const B2DPoint aEnd(rCandidate.getB2DPoint(nNextIndex));
806 bool bDone(false);
807
808 if(rCandidate.areControlPointsUsed())
809 {
810 const B2DCubicBezier aBezierSegment(
811 aStart, rCandidate.getNextControlPoint(a),
812 rCandidate.getPrevControlPoint(nNextIndex), aEnd);
813
814 if(aBezierSegment.isBezier())
815 {
816 // use B2DCubicBezierHelper to bridge the non-linear gap between
817 // length and bezier distances
818 const B2DCubicBezierHelper aBezierSegmentHelper(aBezierSegment);
819 const double fBezierDistance(aBezierSegmentHelper.distanceToRelative(fTo - fPositionOfStart));
820 B2DCubicBezier aLeft;
821
822 aBezierSegment.split(fBezierDistance, &aLeft, nullptr);
823 aRetval.append(aLeft.getEndPoint());
824 aRetval.setPrevControlPoint(aRetval.count() - 1, aLeft.getControlPointB());
825 bDone = true;
826 }
827 }
828
829 if(!bDone)
830 {
831 const double fRelValue((fTo - fPositionOfStart) / fEdgeLength);
832 aRetval.append(interpolate(aStart, aEnd, fRelValue));
833 }
834 }
835
836 bEndDone = true;
837 }
838
839 if(!bEndDone)
840 {
841 if(bStartDone)
842 {
843 // add segments end point
844 const sal_uInt32 nNextIndex((a + 1) % nPointCount);
845 aRetval.append(rCandidate.getB2DPoint(nNextIndex));
846
847 if(rCandidate.areControlPointsUsed())
848 {
849 aRetval.setPrevControlPoint(aRetval.count() - 1, rCandidate.getPrevControlPoint(nNextIndex));
850 aRetval.setNextControlPoint(aRetval.count() - 1, rCandidate.getNextControlPoint(nNextIndex));
851 }
852 }
853
854 // increment fPositionOfStart
855 fPositionOfStart += fEdgeLength;
856 }
857 }
858 return aRetval;
859 }
860 }
861 else
862 {
863 return rCandidate;
864 }
865 }
866
867 CutFlagValue findCut(
868 const B2DPoint& rEdge1Start, const B2DVector& rEdge1Delta,
869 const B2DPoint& rEdge2Start, const B2DVector& rEdge2Delta,
870 CutFlagValue aCutFlags,
871 double* pCut1, double* pCut2)
872 {
873 CutFlagValue aRetval(CutFlagValue::NONE);
874 double fCut1(0.0);
875 double fCut2(0.0);
876 bool bFinished(!static_cast<bool>(aCutFlags & CutFlagValue::ALL));
877
878 // test for same points?
879 if(!bFinished
880 && (aCutFlags & (CutFlagValue::START1|CutFlagValue::END1))
881 && (aCutFlags & (CutFlagValue::START2|CutFlagValue::END2)))
882 {
883 // same startpoint?
884 if((aCutFlags & (CutFlagValue::START1|CutFlagValue::START2)) == (CutFlagValue::START1|CutFlagValue::START2))
885 {
886 if(rEdge1Start.equal(rEdge2Start))
887 {
888 bFinished = true;
889 aRetval = (CutFlagValue::START1|CutFlagValue::START2);
890 }
891 }
892
893 // same endpoint?
894 if(!bFinished && (aCutFlags & (CutFlagValue::END1|CutFlagValue::END2)) == (CutFlagValue::END1|CutFlagValue::END2))
895 {
896 const B2DPoint aEnd1(rEdge1Start + rEdge1Delta);
897 const B2DPoint aEnd2(rEdge2Start + rEdge2Delta);
898
899 if(aEnd1.equal(aEnd2))
900 {
901 bFinished = true;
902 aRetval = (CutFlagValue::END1|CutFlagValue::END2);
903 fCut1 = fCut2 = 1.0;
904 }
905 }
906
907 // startpoint1 == endpoint2?
908 if(!bFinished && (aCutFlags & (CutFlagValue::START1|CutFlagValue::END2)) == (CutFlagValue::START1|CutFlagValue::END2))
909 {
910 const B2DPoint aEnd2(rEdge2Start + rEdge2Delta);
911
912 if(rEdge1Start.equal(aEnd2))
913 {
914 bFinished = true;
915 aRetval = (CutFlagValue::START1|CutFlagValue::END2);
916 fCut1 = 0.0;
917 fCut2 = 1.0;
918 }
919 }
920
921 // startpoint2 == endpoint1?
922 if(!bFinished&& (aCutFlags & (CutFlagValue::START2|CutFlagValue::END1)) == (CutFlagValue::START2|CutFlagValue::END1))
923 {
924 const B2DPoint aEnd1(rEdge1Start + rEdge1Delta);
925
926 if(rEdge2Start.equal(aEnd1))
927 {
928 bFinished = true;
929 aRetval = (CutFlagValue::START2|CutFlagValue::END1);
930 fCut1 = 1.0;
931 fCut2 = 0.0;
932 }
933 }
934 }
935
936 if(!bFinished && (aCutFlags & CutFlagValue::LINE))
937 {
938 if(aCutFlags & CutFlagValue::START1)
939 {
940 // start1 on line 2 ?
941 if(isPointOnEdge(rEdge1Start, rEdge2Start, rEdge2Delta, &fCut2))
942 {
943 bFinished = true;
944 aRetval = (CutFlagValue::LINE|CutFlagValue::START1);
945 }
946 }
947
948 if(!bFinished && (aCutFlags & CutFlagValue::START2))
949 {
950 // start2 on line 1 ?
951 if(isPointOnEdge(rEdge2Start, rEdge1Start, rEdge1Delta, &fCut1))
952 {
953 bFinished = true;
954 aRetval = (CutFlagValue::LINE|CutFlagValue::START2);
955 }
956 }
957
958 if(!bFinished && (aCutFlags & CutFlagValue::END1))
959 {
960 // end1 on line 2 ?
961 const B2DPoint aEnd1(rEdge1Start + rEdge1Delta);
962
963 if(isPointOnEdge(aEnd1, rEdge2Start, rEdge2Delta, &fCut2))
964 {
965 bFinished = true;
966 aRetval = (CutFlagValue::LINE|CutFlagValue::END1);
967 }
968 }
969
970 if(!bFinished && (aCutFlags & CutFlagValue::END2))
971 {
972 // end2 on line 1 ?
973 const B2DPoint aEnd2(rEdge2Start + rEdge2Delta);
974
975 if(isPointOnEdge(aEnd2, rEdge1Start, rEdge1Delta, &fCut1))
976 {
977 bFinished = true;
978 aRetval = (CutFlagValue::LINE|CutFlagValue::END2);
979 }
980 }
981
982 if(!bFinished)
983 {
984 // cut in line1, line2 ?
985 fCut1 = (rEdge1Delta.getX() * rEdge2Delta.getY()) - (rEdge1Delta.getY() * rEdge2Delta.getX());
986
987 if(!fTools::equalZero(fCut1))
988 {
989 fCut1 = (rEdge2Delta.getY() * (rEdge2Start.getX() - rEdge1Start.getX())
990 + rEdge2Delta.getX() * (rEdge1Start.getY() - rEdge2Start.getY())) / fCut1;
991
992 const double fZero(0.0);
993 const double fOne(1.0);
994
995 // inside parameter range edge1 AND fCut2 is calculable
996 if(fTools::more(fCut1, fZero) && fTools::less(fCut1, fOne)
997 && (!fTools::equalZero(rEdge2Delta.getX()) || !fTools::equalZero(rEdge2Delta.getY())))
998 {
999 // take the more precise calculation of the two possible
1000 if(fabs(rEdge2Delta.getX()) > fabs(rEdge2Delta.getY()))
1001 {
1002 fCut2 = (rEdge1Start.getX() + fCut1
1003 * rEdge1Delta.getX() - rEdge2Start.getX()) / rEdge2Delta.getX();
1004 }
1005 else
1006 {
1007 fCut2 = (rEdge1Start.getY() + fCut1
1008 * rEdge1Delta.getY() - rEdge2Start.getY()) / rEdge2Delta.getY();
1009 }
1010
1011 // inside parameter range edge2, too
1012 if(fTools::more(fCut2, fZero) && fTools::less(fCut2, fOne))
1013 {
1014 aRetval = CutFlagValue::LINE;
1015 }
1016 }
1017 }
1018 }
1019 }
1020
1021 // copy values if wanted
1022 if(pCut1)
1023 {
1024 *pCut1 = fCut1;
1025 }
1026
1027 if(pCut2)
1028 {
1029 *pCut2 = fCut2;
1030 }
1031
1032 return aRetval;
1033 }
1034
1035 bool isPointOnEdge(
1036 const B2DPoint& rPoint,
1037 const B2DPoint& rEdgeStart,
1038 const B2DVector& rEdgeDelta,
1039 double* pCut)
1040 {
1041 bool bDeltaXIsZero(fTools::equalZero(rEdgeDelta.getX()));
1042 bool bDeltaYIsZero(fTools::equalZero(rEdgeDelta.getY()));
1043 const double fZero(0.0);
1044 const double fOne(1.0);
1045
1046 if(bDeltaXIsZero && bDeltaYIsZero)
1047 {
1048 // no line, just a point
1049 return false;
1050 }
1051 else if(bDeltaXIsZero)
1052 {
1053 // vertical line
1054 if(fTools::equal(rPoint.getX(), rEdgeStart.getX()))
1055 {
1056 double fValue = (rPoint.getY() - rEdgeStart.getY()) / rEdgeDelta.getY();
1057
1058 if(fTools::more(fValue, fZero) && fTools::less(fValue, fOne))
1059 {
1060 if(pCut)
1061 {
1062 *pCut = fValue;
1063 }
1064
1065 return true;
1066 }
1067 }
1068 }
1069 else if(bDeltaYIsZero)
1070 {
1071 // horizontal line
1072 if(fTools::equal(rPoint.getY(), rEdgeStart.getY()))
1073 {
1074 double fValue = (rPoint.getX() - rEdgeStart.getX()) / rEdgeDelta.getX();
1075
1076 if(fTools::more(fValue, fZero) && fTools::less(fValue, fOne))
1077 {
1078 if(pCut)
1079 {
1080 *pCut = fValue;
1081 }
1082
1083 return true;
1084 }
1085 }
1086 }
1087 else
1088 {
1089 // any angle line
1090 double fTOne = (rPoint.getX() - rEdgeStart.getX()) / rEdgeDelta.getX();
1091 double fTTwo = (rPoint.getY() - rEdgeStart.getY()) / rEdgeDelta.getY();
1092
1093 if(fTools::equal(fTOne, fTTwo))
1094 {
1095 // same parameter representation, point is on line. Take
1096 // middle value for better results
1097 double fValue = (fTOne + fTTwo) / 2.0;
1098
1099 if(fTools::more(fValue, fZero) && fTools::less(fValue, fOne))
1100 {
1101 // point is inside line bounds, too
1102 if(pCut)
1103 {
1104 *pCut = fValue;
1105 }
1106
1107 return true;
1108 }
1109 }
1110 }
1111
1112 return false;
1113 }
1114
1115 void applyLineDashing(
1116 const B2DPolygon& rCandidate,
1117 const std::vector<double>& rDotDashArray,
1118 B2DPolyPolygon* pLineTarget,
1119 B2DPolyPolygon* pGapTarget,
1120 double fDotDashLength)
1121 {
1122 // clear targets in any case
1123 if(pLineTarget)
1124 {
1125 pLineTarget->clear();
1126 }
1127
1128 if(pGapTarget)
1129 {
1130 pGapTarget->clear();
1131 }
1132
1133 // call version that uses callbacks
1134 applyLineDashing(
1135 rCandidate,
1136 rDotDashArray,
1137 // provide callbacks as lambdas
1138 (!pLineTarget
1139 ? std::function<void(const basegfx::B2DPolygon&)>()
1140 : [&pLineTarget](const basegfx::B2DPolygon& rSnippet){ pLineTarget->append(rSnippet); }),
1141 (!pGapTarget
1142 ? std::function<void(const basegfx::B2DPolygon&)>()
1143 : [&pGapTarget](const basegfx::B2DPolygon& rSnippet){ pGapTarget->append(rSnippet); }),
1144 fDotDashLength);
1145 }
1146
1147 static void implHandleSnippet(
1148 const B2DPolygon& rSnippet,
1149 const std::function<void(const basegfx::B2DPolygon& rSnippet)>& rTargetCallback,
1150 B2DPolygon& rFirst,
1151 B2DPolygon& rLast)
1152 {
1153 if(rSnippet.isClosed())
1154 {
1155 if(!rFirst.count())
1156 {
1157 rFirst = rSnippet;
1158 }
1159 else
1160 {
1161 if(rLast.count())
1162 {
1163 rTargetCallback(rLast);
1164 }
1165
1166 rLast = rSnippet;
1167 }
1168 }
1169 else
1170 {
1171 rTargetCallback(rSnippet);
1172 }
1173 }
1174
1175 static void implHandleFirstLast(
1176 const std::function<void(const basegfx::B2DPolygon& rSnippet)>& rTargetCallback,
1177 B2DPolygon& rFirst,
1178 B2DPolygon& rLast)
1179 {
1180 if(rFirst.count() && rLast.count()
1181 && rFirst.getB2DPoint(0).equal(rLast.getB2DPoint(rLast.count() - 1)))
1182 {
1183 // start of first and end of last are the same -> merge them
1184 rLast.append(rFirst);
1185 rLast.removeDoublePoints();
1186 rFirst.clear();
1187 }
1188
1189 if(rLast.count())
1190 {
1191 rTargetCallback(rLast);
1192 }
1193
1194 if(rFirst.count())
1195 {
1196 rTargetCallback(rFirst);
1197 }
1198 }
1199
1200 void applyLineDashing(
1201 const B2DPolygon& rCandidate,
1202 const std::vector<double>& rDotDashArray,
1203 const std::function<void(const basegfx::B2DPolygon& rSnippet)>& rLineTargetCallback,
1204 const std::function<void(const basegfx::B2DPolygon& rSnippet)>& rGapTargetCallback,
1205 double fDotDashLength)
1206 {
1207 const sal_uInt32 nPointCount(rCandidate.count());
1208 const sal_uInt32 nDotDashCount(rDotDashArray.size());
1209
1210 if(fDotDashLength <= 0.0)
1211 {
1212 fDotDashLength = std::accumulate(rDotDashArray.begin(), rDotDashArray.end(), 0.0);
1213 }
1214
1215 if(fDotDashLength <= 0.0 || (!rLineTargetCallback && !rGapTargetCallback) || !nPointCount)
1216 {
1217 // parameters make no sense, just add source to targets
1218 if (rLineTargetCallback)
1219 rLineTargetCallback(rCandidate);
1220
1221 if (rGapTargetCallback)
1222 rGapTargetCallback(rCandidate);
1223
1224 return;
1225 }
1226
1227 // precalculate maximal acceptable length of candidate polygon assuming
1228 // we want to create a maximum of fNumberOfAllowedSnippets. For
1229 // fNumberOfAllowedSnippets use ca. 65536, double due to line & gap.
1230 static const double fNumberOfAllowedSnippets(65535.0 * 2.0);
1231 const double fAllowedLength((fNumberOfAllowedSnippets * fDotDashLength) / double(rDotDashArray.size()));
1232 const double fCandidateLength(basegfx::utils::getLength(rCandidate));
1233 std::vector<double> aDotDashArray(rDotDashArray);
1234
1235 if(fCandidateLength > fAllowedLength)
1236 {
1237 // we would produce more than fNumberOfAllowedSnippets, so
1238 // adapt aDotDashArray to exactly produce assumed number. Also
1239 // assert this to let the caller know about it.
1240 // If this asserts: Please think about checking your DotDashArray
1241 // before calling this function or evtl. use the callback version
1242 // to *not* produce that much of data. Even then, you may still
1243 // think about producing too much runtime (!)
1244 assert(true && "applyLineDashing: potentially too expensive to do the requested dismantle - please consider stretched LineDash pattern (!)");
1245
1246 // calculate correcting factor, apply to aDotDashArray and fDotDashLength
1247 // to enlarge these as needed
1248 const double fFactor(fCandidateLength / fAllowedLength);
1249 std::for_each(aDotDashArray.begin(), aDotDashArray.end(), [&fFactor](double &f){ f *= fFactor; });
1250 }
1251
1252 // prepare current edge's start
1253 B2DCubicBezier aCurrentEdge;
1254 const bool bIsClosed(rCandidate.isClosed());
1255 const sal_uInt32 nEdgeCount(bIsClosed ? nPointCount : nPointCount - 1);
1256 aCurrentEdge.setStartPoint(rCandidate.getB2DPoint(0));
1257
1258 // prepare DotDashArray iteration and the line/gap switching bool
1259 sal_uInt32 nDotDashIndex(0);
1260 bool bIsLine(true);
1261 double fDotDashMovingLength(aDotDashArray[0]);
1262 B2DPolygon aSnippet;
1263
1264 // remember 1st and last snippets to try to merge after execution
1265 // is complete and hand to callback
1266 B2DPolygon aFirstLine, aLastLine;
1267 B2DPolygon aFirstGap, aLastGap;
1268
1269 // iterate over all edges
1270 for(sal_uInt32 a(0); a < nEdgeCount; a++)
1271 {
1272 // update current edge (fill in C1, C2 and end point)
1273 double fLastDotDashMovingLength(0.0);
1274 const sal_uInt32 nNextIndex((a + 1) % nPointCount);
1275 aCurrentEdge.setControlPointA(rCandidate.getNextControlPoint(a));
1276 aCurrentEdge.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex));
1277 aCurrentEdge.setEndPoint(rCandidate.getB2DPoint(nNextIndex));
1278
1279 // check if we have a trivial bezier segment -> possible fallback to edge
1280 aCurrentEdge.testAndSolveTrivialBezier();
1281
1282 if(aCurrentEdge.isBezier())
1283 {
1284 // bezier segment
1285 const B2DCubicBezierHelper aCubicBezierHelper(aCurrentEdge);
1286 const double fEdgeLength(aCubicBezierHelper.getLength());
1287
1288 if(!fTools::equalZero(fEdgeLength))
1289 {
1290 while(fTools::less(fDotDashMovingLength, fEdgeLength))
1291 {
1292 // new split is inside edge, create and append snippet [fLastDotDashMovingLength, fDotDashMovingLength]
1293 const bool bHandleLine(bIsLine && rLineTargetCallback);
1294 const bool bHandleGap(!bIsLine && rGapTargetCallback);
1295
1296 if(bHandleLine || bHandleGap)
1297 {
1298 const double fBezierSplitStart(aCubicBezierHelper.distanceToRelative(fLastDotDashMovingLength));
1299 const double fBezierSplitEnd(aCubicBezierHelper.distanceToRelative(fDotDashMovingLength));
1300 B2DCubicBezier aBezierSnippet(aCurrentEdge.snippet(fBezierSplitStart, fBezierSplitEnd));
1301
1302 if(!aSnippet.count())
1303 {
1304 aSnippet.append(aBezierSnippet.getStartPoint());
1305 }
1306
1307 aSnippet.appendBezierSegment(aBezierSnippet.getControlPointA(), aBezierSnippet.getControlPointB(), aBezierSnippet.getEndPoint());
1308
1309 if(bHandleLine)
1310 {
1311 implHandleSnippet(aSnippet, rLineTargetCallback, aFirstLine, aLastLine);
1312 }
1313
1314 if(bHandleGap)
1315 {
1316 implHandleSnippet(aSnippet, rGapTargetCallback, aFirstGap, aLastGap);
1317 }
1318
1319 aSnippet.clear();
1320 }
1321
1322 // prepare next DotDashArray step and flip line/gap flag
1323 fLastDotDashMovingLength = fDotDashMovingLength;
1324 fDotDashMovingLength += aDotDashArray[(++nDotDashIndex) % nDotDashCount];
1325 bIsLine = !bIsLine;
1326 }
1327
1328 // append closing snippet [fLastDotDashMovingLength, fEdgeLength]
1329 const bool bHandleLine(bIsLine && rLineTargetCallback);
1330 const bool bHandleGap(!bIsLine && rGapTargetCallback);
1331
1332 if(bHandleLine || bHandleGap)
1333 {
1334 B2DCubicBezier aRight;
1335 const double fBezierSplit(aCubicBezierHelper.distanceToRelative(fLastDotDashMovingLength));
1336
1337 aCurrentEdge.split(fBezierSplit, nullptr, &aRight);
1338
1339 if(!aSnippet.count())
1340 {
1341 aSnippet.append(aRight.getStartPoint());
1342 }
1343
1344 aSnippet.appendBezierSegment(aRight.getControlPointA(), aRight.getControlPointB(), aRight.getEndPoint());
1345 }
1346
1347 // prepare move to next edge
1348 fDotDashMovingLength -= fEdgeLength;
1349 }
1350 }
1351 else
1352 {
1353 // simple edge
1354 const double fEdgeLength(aCurrentEdge.getEdgeLength());
1355
1356 if(!fTools::equalZero(fEdgeLength))
1357 {
1358 while(fTools::less(fDotDashMovingLength, fEdgeLength))
1359 {
1360 // new split is inside edge, create and append snippet [fLastDotDashMovingLength, fDotDashMovingLength]
1361 const bool bHandleLine(bIsLine && rLineTargetCallback);
1362 const bool bHandleGap(!bIsLine && rGapTargetCallback);
1363
1364 if(bHandleLine || bHandleGap)
1365 {
1366 if(!aSnippet.count())
1367 {
1368 aSnippet.append(interpolate(aCurrentEdge.getStartPoint(), aCurrentEdge.getEndPoint(), fLastDotDashMovingLength / fEdgeLength));
1369 }
1370
1371 aSnippet.append(interpolate(aCurrentEdge.getStartPoint(), aCurrentEdge.getEndPoint(), fDotDashMovingLength / fEdgeLength));
1372
1373 if(bHandleLine)
1374 {
1375 implHandleSnippet(aSnippet, rLineTargetCallback, aFirstLine, aLastLine);
1376 }
1377
1378 if(bHandleGap)
1379 {
1380 implHandleSnippet(aSnippet, rGapTargetCallback, aFirstGap, aLastGap);
1381 }
1382
1383 aSnippet.clear();
1384 }
1385
1386 // prepare next DotDashArray step and flip line/gap flag
1387 fLastDotDashMovingLength = fDotDashMovingLength;
1388 fDotDashMovingLength += aDotDashArray[(++nDotDashIndex) % nDotDashCount];
1389 bIsLine = !bIsLine;
1390 }
1391
1392 // append snippet [fLastDotDashMovingLength, fEdgeLength]
1393 const bool bHandleLine(bIsLine && rLineTargetCallback);
1394 const bool bHandleGap(!bIsLine && rGapTargetCallback);
1395
1396 if(bHandleLine || bHandleGap)
1397 {
1398 if(!aSnippet.count())
1399 {
1400 aSnippet.append(interpolate(aCurrentEdge.getStartPoint(), aCurrentEdge.getEndPoint(), fLastDotDashMovingLength / fEdgeLength));
1401 }
1402
1403 aSnippet.append(aCurrentEdge.getEndPoint());
1404 }
1405
1406 // prepare move to next edge
1407 fDotDashMovingLength -= fEdgeLength;
1408 }
1409 }
1410
1411 // prepare next edge step (end point gets new start point)
1412 aCurrentEdge.setStartPoint(aCurrentEdge.getEndPoint());
1413 }
1414
1415 // append last intermediate results (if exists)
1416 if(aSnippet.count())
1417 {
1418 const bool bHandleLine(bIsLine && rLineTargetCallback);
1419 const bool bHandleGap(!bIsLine && rGapTargetCallback);
1420
1421 if(bHandleLine)
1422 {
1423 implHandleSnippet(aSnippet, rLineTargetCallback, aFirstLine, aLastLine);
1424 }
1425
1426 if(bHandleGap)
1427 {
1428 implHandleSnippet(aSnippet, rGapTargetCallback, aFirstGap, aLastGap);
1429 }
1430 }
1431
1432 if(bIsClosed && rLineTargetCallback)
1433 {
1434 implHandleFirstLast(rLineTargetCallback, aFirstLine, aLastLine);
1435 }
1436
1437 if(bIsClosed && rGapTargetCallback)
1438 {
1439 implHandleFirstLast(rGapTargetCallback, aFirstGap, aLastGap);
1440 }
1441 }
1442
1443 // test if point is inside epsilon-range around an edge defined
1444 // by the two given points. Can be used for HitTesting. The epsilon-range
1445 // is defined to be the rectangle centered to the given edge, using height
1446 // 2 x fDistance, and the circle around both points with radius fDistance.
1447 bool isInEpsilonRange(const B2DPoint& rEdgeStart, const B2DPoint& rEdgeEnd, const B2DPoint& rTestPosition, double fDistance)
1448 {
1449 // build edge vector
1450 const B2DVector aEdge(rEdgeEnd - rEdgeStart);
1451 bool bDoDistanceTestStart(false);
1452 bool bDoDistanceTestEnd(false);
1453
1454 if(aEdge.equalZero())
1455 {
1456 // no edge, just a point. Do one of the distance tests.
1457 bDoDistanceTestStart = true;
1458 }
1459 else
1460 {
1461 // edge has a length. Create perpendicular vector.
1462 const B2DVector aPerpend(getPerpendicular(aEdge));
1463 double fCut(
1464 (aPerpend.getY() * (rTestPosition.getX() - rEdgeStart.getX())
1465 + aPerpend.getX() * (rEdgeStart.getY() - rTestPosition.getY())) /
1466 (aEdge.getX() * aEdge.getX() + aEdge.getY() * aEdge.getY()));
1467 const double fZero(0.0);
1468 const double fOne(1.0);
1469
1470 if(fTools::less(fCut, fZero))
1471 {
1472 // left of rEdgeStart
1473 bDoDistanceTestStart = true;
1474 }
1475 else if(fTools::more(fCut, fOne))
1476 {
1477 // right of rEdgeEnd
1478 bDoDistanceTestEnd = true;
1479 }
1480 else
1481 {
1482 // inside line [0.0 .. 1.0]
1483 const B2DPoint aCutPoint(interpolate(rEdgeStart, rEdgeEnd, fCut));
1484 const B2DVector aDelta(rTestPosition - aCutPoint);
1485 const double fDistanceSquare(aDelta.scalar(aDelta));
1486
1487 return fDistanceSquare <= fDistance * fDistance;
1488 }
1489 }
1490
1491 if(bDoDistanceTestStart)
1492 {
1493 const B2DVector aDelta(rTestPosition - rEdgeStart);
1494 const double fDistanceSquare(aDelta.scalar(aDelta));
1495
1496 if(fDistanceSquare <= fDistance * fDistance)
1497 {
1498 return true;
1499 }
1500 }
1501 else if(bDoDistanceTestEnd)
1502 {
1503 const B2DVector aDelta(rTestPosition - rEdgeEnd);
1504 const double fDistanceSquare(aDelta.scalar(aDelta));
1505
1506 if(fDistanceSquare <= fDistance * fDistance)
1507 {
1508 return true;
1509 }
1510 }
1511
1512 return false;
1513 }
1514
1515 // test if point is inside epsilon-range around the given Polygon. Can be used
1516 // for HitTesting. The epsilon-range is defined to be the tube around the polygon
1517 // with distance fDistance and rounded edges (start and end point).
1518 bool isInEpsilonRange(const B2DPolygon& rCandidate, const B2DPoint& rTestPosition, double fDistance)
1519 {
1520 // force to non-bezier polygon
1521 const B2DPolygon& aCandidate(rCandidate.getDefaultAdaptiveSubdivision());
1522 const sal_uInt32 nPointCount(aCandidate.count());
1523
1524 if(!nPointCount)
1525 return false;
1526
1527 const sal_uInt32 nEdgeCount(aCandidate.isClosed() ? nPointCount : nPointCount - 1);
1528 B2DPoint aCurrent(aCandidate.getB2DPoint(0));
1529
1530 if(nEdgeCount)
1531 {
1532 // edges
1533 for(sal_uInt32 a(0); a < nEdgeCount; a++)
1534 {
1535 const sal_uInt32 nNextIndex((a + 1) % nPointCount);
1536 const B2DPoint aNext(aCandidate.getB2DPoint(nNextIndex));
1537
1538 if(isInEpsilonRange(aCurrent, aNext, rTestPosition, fDistance))
1539 {
1540 return true;
1541 }
1542
1543 // prepare next step
1544 aCurrent = aNext;
1545 }
1546 }
1547 else
1548 {
1549 // no edges, but points -> not closed. Check single point. Just
1550 // use isInEpsilonRange with twice the same point, it handles those well
1551 if(isInEpsilonRange(aCurrent, aCurrent, rTestPosition, fDistance))
1552 {
1553 return true;
1554 }
1555 }
1556
1557 return false;
1558 }
1559
1560 // Calculates distance of curve point to its control point for a Bézier curve, that
1561 // approximates a unit circle arc. fAngle is the center angle of the circle arc. The
1562 // constrain 0<=fAngle<=pi/2 must not be violated to give a useful accuracy. For details
1563 // and alternatives read document "ApproxCircleInfo.odt", attachment of bug tdf#121425.
1564 static double impDistanceBezierPointToControl(double fAngle)
1565 {
1566 SAL_WARN_IF(fAngle < 0 || fAngle > M_PI_2,"basegfx","angle not suitable for approximate circle");
1567 if (0 <= fAngle && fAngle <= M_PI_2)
1568 {
1569 return 4.0/3.0 * ( tan(fAngle/4.0));
1570 }
1571 else
1572 return 0;
1573 }
1574
1575 B2DPolygon createPolygonFromRect( const B2DRectangle& rRect, double fRadiusX, double fRadiusY )
1576 {
1577 const double fZero(0.0);
1578 const double fOne(1.0);
1579
1580 fRadiusX = std::clamp(fRadiusX, 0.0, 1.0);
1581 fRadiusY = std::clamp(fRadiusY, 0.0, 1.0);
1582
1583 if(rtl::math::approxEqual(fZero, fRadiusX) || rtl::math::approxEqual(fZero, fRadiusY))
1584 {
1585 // at least in one direction no radius, use rectangle.
1586 // Do not use createPolygonFromRect() here since original
1587 // creator (historical reasons) still creates a start point at the
1588 // bottom center, so do the same here to get the same line patterns.
1589 // Due to this the order of points is different, too.
1590 const B2DPoint aBottomCenter(rRect.getCenter().getX(), rRect.getMaxY());
1591 B2DPolygon aPolygon {
1592 aBottomCenter,
1593 { rRect.getMinX(), rRect.getMaxY() },
1594 { rRect.getMinX(), rRect.getMinY() },
1595 { rRect.getMaxX(), rRect.getMinY() },
1596 { rRect.getMaxX(), rRect.getMaxY() }
1597 };
1598
1599 // close
1600 aPolygon.setClosed( true );
1601
1602 return aPolygon;
1603 }
1604 else if(rtl::math::approxEqual(fOne, fRadiusX) && rtl::math::approxEqual(fOne, fRadiusY))
1605 {
1606 // in both directions full radius, use ellipse
1607 const B2DPoint aCenter(rRect.getCenter());
1608 const double fRectRadiusX(rRect.getWidth() / 2.0);
1609 const double fRectRadiusY(rRect.getHeight() / 2.0);
1610
1611 return createPolygonFromEllipse( aCenter, fRectRadiusX, fRectRadiusY );
1612 }
1613 else
1614 {
1615 B2DPolygon aRetval;
1616 const double fBowX((rRect.getWidth() / 2.0) * fRadiusX);
1617 const double fBowY((rRect.getHeight() / 2.0) * fRadiusY);
1618 const double fKappa(impDistanceBezierPointToControl(M_PI_2));
1619
1620 // create start point at bottom center
1621 if(!rtl::math::approxEqual(fOne, fRadiusX))
1622 {
1623 const B2DPoint aBottomCenter(rRect.getCenter().getX(), rRect.getMaxY());
1624 aRetval.append(aBottomCenter);
1625 }
1626
1627 // create first bow
1628 {
1629 const B2DPoint aBottomRight(rRect.getMaxX(), rRect.getMaxY());
1630 const B2DPoint aStart(aBottomRight + B2DPoint(-fBowX, 0.0));
1631 const B2DPoint aStop(aBottomRight + B2DPoint(0.0, -fBowY));
1632 aRetval.append(aStart);
1633 aRetval.appendBezierSegment(interpolate(aStart, aBottomRight, fKappa), interpolate(aStop, aBottomRight, fKappa), aStop);
1634 }
1635
1636 // create second bow
1637 {
1638 const B2DPoint aTopRight(rRect.getMaxX(), rRect.getMinY());
1639 const B2DPoint aStart(aTopRight + B2DPoint(0.0, fBowY));
1640 const B2DPoint aStop(aTopRight + B2DPoint(-fBowX, 0.0));
1641 aRetval.append(aStart);
1642 aRetval.appendBezierSegment(interpolate(aStart, aTopRight, fKappa), interpolate(aStop, aTopRight, fKappa), aStop);
1643 }
1644
1645 // create third bow
1646 {
1647 const B2DPoint aTopLeft(rRect.getMinX(), rRect.getMinY());
1648 const B2DPoint aStart(aTopLeft + B2DPoint(fBowX, 0.0));
1649 const B2DPoint aStop(aTopLeft + B2DPoint(0.0, fBowY));
1650 aRetval.append(aStart);
1651 aRetval.appendBezierSegment(interpolate(aStart, aTopLeft, fKappa), interpolate(aStop, aTopLeft, fKappa), aStop);
1652 }
1653
1654 // create forth bow
1655 {
1656 const B2DPoint aBottomLeft(rRect.getMinX(), rRect.getMaxY());
1657 const B2DPoint aStart(aBottomLeft + B2DPoint(0.0, -fBowY));
1658 const B2DPoint aStop(aBottomLeft + B2DPoint(fBowX, 0.0));
1659 aRetval.append(aStart);
1660 aRetval.appendBezierSegment(interpolate(aStart, aBottomLeft, fKappa), interpolate(aStop, aBottomLeft, fKappa), aStop);
1661 }
1662
1663 // close
1664 aRetval.setClosed( true );
1665
1666 // remove double created points if there are extreme radii involved
1667 if(rtl::math::approxEqual(fOne, fRadiusX) || rtl::math::approxEqual(fOne, fRadiusY))
1668 {
1669 aRetval.removeDoublePoints();
1670 }
1671
1672 return aRetval;
1673 }
1674 }
1675
1676 B2DPolygon createPolygonFromRect( const B2DRectangle& rRect )
1677 {
1678 B2DPolygon aPolygon {
1679 { rRect.getMinX(), rRect.getMinY() },
1680 { rRect.getMaxX(), rRect.getMinY() },
1681 { rRect.getMaxX(), rRect.getMaxY() },
1682 { rRect.getMinX(), rRect.getMaxY() }
1683 };
1684
1685 // close
1686 aPolygon.setClosed( true );
1687
1688 return aPolygon;
1689 }
1690
1691 B2DPolygon const & createUnitPolygon()
1692 {
1693 static auto const singleton = [] {
1694 B2DPolygon aPolygon {
1695 { 0.0, 0.0 },
1696 { 1.0, 0.0 },
1697 { 1.0, 1.0 },
1698 { 0.0, 1.0 }
1699 };
1700
1701 // close
1702 aPolygon.setClosed( true );
1703
1704 return aPolygon;
1705 }();
1706 return singleton;
1707 }
1708
1709 B2DPolygon createPolygonFromCircle( const B2DPoint& rCenter, double fRadius )
1710 {
1711 return createPolygonFromEllipse( rCenter, fRadius, fRadius );
1712 }
1713
1714 static B2DPolygon impCreateUnitCircle(sal_uInt32 nStartQuadrant)
1715 {
1716 B2DPolygon aUnitCircle;
1717 const double fSegmentKappa = impDistanceBezierPointToControl(M_PI_2 / STEPSPERQUARTER);
1718 const B2DHomMatrix aRotateMatrix(createRotateB2DHomMatrix(M_PI_2 / STEPSPERQUARTER));
1719
1720 B2DPoint aPoint(1.0, 0.0);
1721 B2DPoint aForward(1.0, fSegmentKappa);
1722 B2DPoint aBackward(1.0, -fSegmentKappa);
1723
1724 if(nStartQuadrant != 0)
1725 {
1726 const B2DHomMatrix aQuadrantMatrix(createRotateB2DHomMatrix(M_PI_2 * (nStartQuadrant % 4)));
1727 aPoint *= aQuadrantMatrix;
1728 aBackward *= aQuadrantMatrix;
1729 aForward *= aQuadrantMatrix;
1730 }
1731
1732 aUnitCircle.append(aPoint);
1733
1734 for(sal_uInt32 a(0); a < STEPSPERQUARTER * 4; a++)
1735 {
1736 aPoint *= aRotateMatrix;
1737 aBackward *= aRotateMatrix;
1738 aUnitCircle.appendBezierSegment(aForward, aBackward, aPoint);
1739 aForward *= aRotateMatrix;
1740 }
1741
1742 aUnitCircle.setClosed(true);
1743 aUnitCircle.removeDoublePoints();
1744
1745 return aUnitCircle;
1746 }
1747
1748 B2DPolygon const & createHalfUnitCircle()
1749 {
1750 static auto const singleton = [] {
1751 B2DPolygon aUnitHalfCircle;
1752 const double fSegmentKappa(impDistanceBezierPointToControl(M_PI_2 / STEPSPERQUARTER));
1753 const B2DHomMatrix aRotateMatrix(createRotateB2DHomMatrix(M_PI_2 / STEPSPERQUARTER));
1754 B2DPoint aPoint(1.0, 0.0);
1755 B2DPoint aForward(1.0, fSegmentKappa);
1756 B2DPoint aBackward(1.0, -fSegmentKappa);
1757
1758 aUnitHalfCircle.append(aPoint);
1759
1760 for(sal_uInt32 a(0); a < STEPSPERQUARTER * 2; a++)
1761 {
1762 aPoint *= aRotateMatrix;
1763 aBackward *= aRotateMatrix;
1764 aUnitHalfCircle.appendBezierSegment(aForward, aBackward, aPoint);
1765 aForward *= aRotateMatrix;
1766 }
1767 return aUnitHalfCircle;
1768 }();
1769 return singleton;
1770 }
1771
1772 B2DPolygon const & createPolygonFromUnitCircle(sal_uInt32 nStartQuadrant)
1773 {
1774 switch(nStartQuadrant % 4)
1775 {
1776 case 1 :
1777 {
1778 static auto const singleton = impCreateUnitCircle(1);
1779 return singleton;
1780 }
1781
1782 case 2 :
1783 {
1784 static auto const singleton = impCreateUnitCircle(2);
1785 return singleton;
1786 }
1787
1788 case 3 :
1789 {
1790 static auto const singleton = impCreateUnitCircle(3);
1791 return singleton;
1792 }
1793
1794 default : // case 0 :
1795 {
1796 static auto const singleton = impCreateUnitCircle(0);
1797 return singleton;
1798 }
1799 }
1800 }
1801
1802 B2DPolygon createPolygonFromEllipse( const B2DPoint& rCenter, double fRadiusX, double fRadiusY, sal_uInt32 nStartQuadrant)
1803 {
1804 B2DPolygon aRetval(createPolygonFromUnitCircle(nStartQuadrant));
1805 const B2DHomMatrix aMatrix(createScaleTranslateB2DHomMatrix(fRadiusX, fRadiusY, rCenter.getX(), rCenter.getY()));
1806
1807 aRetval.transform(aMatrix);
1808
1809 return aRetval;
1810 }
1811
1812 B2DPolygon createPolygonFromUnitEllipseSegment( double fStart, double fEnd )
1813 {
1814 B2DPolygon aRetval;
1815
1816 // truncate fStart, fEnd to a range of [0.0 .. 2PI[ where 2PI
1817 // falls back to 0.0 to ensure a unique definition
1818 if(fStart < 0.0)
1819 {
1820 fStart = 0.0;
1821 }
1822
1823 if(fTools::moreOrEqual(fStart, 2 * M_PI))
1824 {
1825 fStart = 0.0;
1826 }
1827
1828 if(fEnd < 0.0)
1829 {
1830 fEnd = 0.0;
1831 }
1832
1833 if(fTools::moreOrEqual(fEnd, 2 * M_PI))
1834 {
1835 fEnd = 0.0;
1836 }
1837
1838 if(fTools::equal(fStart, fEnd))
1839 {
1840 // same start and end angle, add single point
1841 aRetval.append(B2DPoint(cos(fStart), sin(fStart)));
1842 }
1843 else
1844 {
1845 const sal_uInt32 nSegments(STEPSPERQUARTER * 4);
1846 const double fAnglePerSegment(M_PI_2 / STEPSPERQUARTER);
1847 const sal_uInt32 nStartSegment(sal_uInt32(fStart / fAnglePerSegment) % nSegments);
1848 const sal_uInt32 nEndSegment(sal_uInt32(fEnd / fAnglePerSegment) % nSegments);
1849 const double fSegmentKappa(impDistanceBezierPointToControl(fAnglePerSegment));
1850
1851 B2DPoint aSegStart(cos(fStart), sin(fStart));
1852 aRetval.append(aSegStart);
1853
1854 if(nStartSegment == nEndSegment && fTools::more(fEnd, fStart))
1855 {
1856 // start and end in one sector and in the right order, create in one segment
1857 const B2DPoint aSegEnd(cos(fEnd), sin(fEnd));
1858 const double fFactor(impDistanceBezierPointToControl(fEnd - fStart));
1859
1860 aRetval.appendBezierSegment(
1861 aSegStart + (B2DPoint(-aSegStart.getY(), aSegStart.getX()) * fFactor),
1862 aSegEnd - (B2DPoint(-aSegEnd.getY(), aSegEnd.getX()) * fFactor),
1863 aSegEnd);
1864 }
1865 else
1866 {
1867 double fSegEndRad((nStartSegment + 1) * fAnglePerSegment);
1868 double fFactor(impDistanceBezierPointToControl(fSegEndRad - fStart));
1869 B2DPoint aSegEnd(cos(fSegEndRad), sin(fSegEndRad));
1870
1871 aRetval.appendBezierSegment(
1872 aSegStart + (B2DPoint(-aSegStart.getY(), aSegStart.getX()) * fFactor),
1873 aSegEnd - (B2DPoint(-aSegEnd.getY(), aSegEnd.getX()) * fFactor),
1874 aSegEnd);
1875
1876 sal_uInt32 nSegment((nStartSegment + 1) % nSegments);
1877 aSegStart = aSegEnd;
1878
1879 while(nSegment != nEndSegment)
1880 {
1881 // No end in this sector, add full sector.
1882 fSegEndRad = (nSegment + 1) * fAnglePerSegment;
1883 aSegEnd = B2DPoint(cos(fSegEndRad), sin(fSegEndRad));
1884
1885 aRetval.appendBezierSegment(
1886 aSegStart + (B2DPoint(-aSegStart.getY(), aSegStart.getX()) * fSegmentKappa),
1887 aSegEnd - (B2DPoint(-aSegEnd.getY(), aSegEnd.getX()) * fSegmentKappa),
1888 aSegEnd);
1889
1890 nSegment = (nSegment + 1) % nSegments;
1891 aSegStart = aSegEnd;
1892 }
1893
1894 // End in this sector
1895 const double fSegStartRad(nSegment * fAnglePerSegment);
1896 fFactor= impDistanceBezierPointToControl(fEnd - fSegStartRad);
1897 aSegEnd = B2DPoint(cos(fEnd), sin(fEnd));
1898
1899 aRetval.appendBezierSegment(
1900 aSegStart + (B2DPoint(-aSegStart.getY(), aSegStart.getX()) * fFactor),
1901 aSegEnd - (B2DPoint(-aSegEnd.getY(), aSegEnd.getX()) * fFactor),
1902 aSegEnd);
1903 }
1904 }
1905
1906 // remove double points between segments created by segmented creation
1907 aRetval.removeDoublePoints();
1908
1909 return aRetval;
1910 }
1911
1912 B2DPolygon createPolygonFromEllipseSegment( const B2DPoint& rCenter, double fRadiusX, double fRadiusY, double fStart, double fEnd )
1913 {
1914 B2DPolygon aRetval(createPolygonFromUnitEllipseSegment(fStart, fEnd));
1915 const B2DHomMatrix aMatrix(createScaleTranslateB2DHomMatrix(fRadiusX, fRadiusY, rCenter.getX(), rCenter.getY()));
1916
1917 aRetval.transform(aMatrix);
1918
1919 return aRetval;
1920 }
1921
1922 bool hasNeutralPoints(const B2DPolygon& rCandidate)
1923 {
1924 OSL_ENSURE(!rCandidate.areControlPointsUsed(), "hasNeutralPoints: ATM works not for curves (!)");
1925 const sal_uInt32 nPointCount(rCandidate.count());
1926
1927 if(nPointCount <= 2)
1928 return false;
1929
1930 B2DPoint aPrevPoint(rCandidate.getB2DPoint(nPointCount - 1));
1931 B2DPoint aCurrPoint(rCandidate.getB2DPoint(0));
1932
1933 for(sal_uInt32 a(0); a < nPointCount; a++)
1934 {
1935 const B2DPoint aNextPoint(rCandidate.getB2DPoint((a + 1) % nPointCount));
1936 const B2DVector aPrevVec(aPrevPoint - aCurrPoint);
1937 const B2DVector aNextVec(aNextPoint - aCurrPoint);
1938 const B2VectorOrientation aOrientation(getOrientation(aNextVec, aPrevVec));
1939
1940 if(aOrientation == B2VectorOrientation::Neutral)
1941 {
1942 // current has neutral orientation
1943 return true;
1944 }
1945 else
1946 {
1947 // prepare next
1948 aPrevPoint = aCurrPoint;
1949 aCurrPoint = aNextPoint;
1950 }
1951 }
1952
1953 return false;
1954 }
1955
1956 B2DPolygon removeNeutralPoints(const B2DPolygon& rCandidate)
1957 {
1958 if(hasNeutralPoints(rCandidate))
1959 {
1960 const sal_uInt32 nPointCount(rCandidate.count());
1961 B2DPolygon aRetval;
1962 B2DPoint aPrevPoint(rCandidate.getB2DPoint(nPointCount - 1));
1963 B2DPoint aCurrPoint(rCandidate.getB2DPoint(0));
1964
1965 for(sal_uInt32 a(0); a < nPointCount; a++)
1966 {
1967 const B2DPoint aNextPoint(rCandidate.getB2DPoint((a + 1) % nPointCount));
1968 const B2DVector aPrevVec(aPrevPoint - aCurrPoint);
1969 const B2DVector aNextVec(aNextPoint - aCurrPoint);
1970 const B2VectorOrientation aOrientation(getOrientation(aNextVec, aPrevVec));
1971
1972 if(aOrientation == B2VectorOrientation::Neutral)
1973 {
1974 // current has neutral orientation, leave it out and prepare next
1975 aCurrPoint = aNextPoint;
1976 }
1977 else
1978 {
1979 // add current point
1980 aRetval.append(aCurrPoint);
1981
1982 // prepare next
1983 aPrevPoint = aCurrPoint;
1984 aCurrPoint = aNextPoint;
1985 }
1986 }
1987
1988 while(aRetval.count() && getOrientationForIndex(aRetval, 0) == B2VectorOrientation::Neutral)
1989 {
1990 aRetval.remove(0);
1991 }
1992
1993 // copy closed state
1994 aRetval.setClosed(rCandidate.isClosed());
1995
1996 return aRetval;
1997 }
1998 else
1999 {
2000 return rCandidate;
2001 }
2002 }
2003
2004 bool isConvex(const B2DPolygon& rCandidate)
2005 {
2006 OSL_ENSURE(!rCandidate.areControlPointsUsed(), "isConvex: ATM works not for curves (!)");
2007 const sal_uInt32 nPointCount(rCandidate.count());
2008
2009 if(nPointCount <= 2)
2010 return true;
2011
2012 const B2DPoint aPrevPoint(rCandidate.getB2DPoint(nPointCount - 1));
2013 B2DPoint aCurrPoint(rCandidate.getB2DPoint(0));
2014 B2DVector aCurrVec(aPrevPoint - aCurrPoint);
2015 B2VectorOrientation aOrientation(B2VectorOrientation::Neutral);
2016
2017 for(sal_uInt32 a(0); a < nPointCount; a++)
2018 {
2019 const B2DPoint aNextPoint(rCandidate.getB2DPoint((a + 1) % nPointCount));
2020 const B2DVector aNextVec(aNextPoint - aCurrPoint);
2021 const B2VectorOrientation aCurrentOrientation(getOrientation(aNextVec, aCurrVec));
2022
2023 if(aOrientation == B2VectorOrientation::Neutral)
2024 {
2025 // set start value, maybe neutral again
2026 aOrientation = aCurrentOrientation;
2027 }
2028 else
2029 {
2030 if(aCurrentOrientation != B2VectorOrientation::Neutral && aCurrentOrientation != aOrientation)
2031 {
2032 // different orientations found, that's it
2033 return false;
2034 }
2035 }
2036
2037 // prepare next
2038 aCurrPoint = aNextPoint;
2039 aCurrVec = -aNextVec;
2040 }
2041
2042 return true;
2043 }
2044
2045 B2VectorOrientation getOrientationForIndex(const B2DPolygon& rCandidate, sal_uInt32 nIndex)
2046 {
2047 OSL_ENSURE(nIndex < rCandidate.count(), "getOrientationForIndex: index out of range (!)");
2048 const B2DPoint aPrev(rCandidate.getB2DPoint(getIndexOfPredecessor(nIndex, rCandidate)));
2049 const B2DPoint aCurr(rCandidate.getB2DPoint(nIndex));
2050 const B2DPoint aNext(rCandidate.getB2DPoint(getIndexOfSuccessor(nIndex, rCandidate)));
2051 const B2DVector aBack(aPrev - aCurr);
2052 const B2DVector aForw(aNext - aCurr);
2053
2054 return getOrientation(aForw, aBack);
2055 }
2056
2057 bool isPointOnLine(const B2DPoint& rStart, const B2DPoint& rEnd, const B2DPoint& rCandidate, bool bWithPoints)
2058 {
2059 if(rCandidate.equal(rStart) || rCandidate.equal(rEnd))
2060 {
2061 // candidate is in epsilon around start or end -> inside
2062 return bWithPoints;
2063 }
2064 else if(rStart.equal(rEnd))
2065 {
2066 // start and end are equal, but candidate is outside their epsilon -> outside
2067 return false;
2068 }
2069 else
2070 {
2071 const B2DVector aEdgeVector(rEnd - rStart);
2072 const B2DVector aTestVector(rCandidate - rStart);
2073
2074 if(areParallel(aEdgeVector, aTestVector))
2075 {
2076 const double fZero(0.0);
2077 const double fOne(1.0);
2078 const double fParamTestOnCurr(fabs(aEdgeVector.getX()) > fabs(aEdgeVector.getY())
2079 ? aTestVector.getX() / aEdgeVector.getX()
2080 : aTestVector.getY() / aEdgeVector.getY());
2081
2082 if(fTools::more(fParamTestOnCurr, fZero) && fTools::less(fParamTestOnCurr, fOne))
2083 {
2084 return true;
2085 }
2086 }
2087
2088 return false;
2089 }
2090 }
2091
2092 bool isPointOnPolygon(const B2DPolygon& rCandidate, const B2DPoint& rPoint, bool bWithPoints)
2093 {
2094 const B2DPolygon aCandidate(rCandidate.areControlPointsUsed() ? rCandidate.getDefaultAdaptiveSubdivision() : rCandidate);
2095 const sal_uInt32 nPointCount(aCandidate.count());
2096
2097 if(nPointCount > 1)
2098 {
2099 const sal_uInt32 nLoopCount(aCandidate.isClosed() ? nPointCount : nPointCount - 1);
2100 B2DPoint aCurrentPoint(aCandidate.getB2DPoint(0));
2101
2102 for(sal_uInt32 a(0); a < nLoopCount; a++)
2103 {
2104 const B2DPoint aNextPoint(aCandidate.getB2DPoint((a + 1) % nPointCount));
2105
2106 if(isPointOnLine(aCurrentPoint, aNextPoint, rPoint, bWithPoints))
2107 {
2108 return true;
2109 }
2110
2111 aCurrentPoint = aNextPoint;
2112 }
2113 }
2114 else if(nPointCount && bWithPoints)
2115 {
2116 return rPoint.equal(aCandidate.getB2DPoint(0));
2117 }
2118
2119 return false;
2120 }
2121
2122 bool isPointInTriangle(const B2DPoint& rA, const B2DPoint& rB, const B2DPoint& rC, const B2DPoint& rCandidate, bool bWithBorder)
2123 {
2124 if(arePointsOnSameSideOfLine(rA, rB, rC, rCandidate, bWithBorder))
2125 {
2126 if(arePointsOnSameSideOfLine(rB, rC, rA, rCandidate, bWithBorder))
2127 {
2128 if(arePointsOnSameSideOfLine(rC, rA, rB, rCandidate, bWithBorder))
2129 {
2130 return true;
2131 }
2132 }
2133 }
2134
2135 return false;
2136 }
2137
2138 bool arePointsOnSameSideOfLine(const B2DPoint& rStart, const B2DPoint& rEnd, const B2DPoint& rCandidateA, const B2DPoint& rCandidateB, bool bWithLine)
2139 {
2140 const B2DVector aLineVector(rEnd - rStart);
2141 const B2DVector aVectorToA(rEnd - rCandidateA);
2142 const double fCrossA(aLineVector.cross(aVectorToA));
2143
2144 // tdf#88352 increase numerical correctness and use rtl::math::approxEqual
2145 // instead of fTools::equalZero which compares with a fixed small value
2146 if(fCrossA == 0.0)
2147 {
2148 // one point on the line
2149 return bWithLine;
2150 }
2151
2152 const B2DVector aVectorToB(rEnd - rCandidateB);
2153 const double fCrossB(aLineVector.cross(aVectorToB));
2154
2155 // increase numerical correctness
2156 if(fCrossB == 0.0)
2157 {
2158 // one point on the line
2159 return bWithLine;
2160 }
2161
2162 // return true if they both have the same sign
2163 return ((fCrossA > 0.0) == (fCrossB > 0.0));
2164 }
2165
2166 void addTriangleFan(
2167 const B2DPolygon& rCandidate,
2168 triangulator::B2DTriangleVector& rTarget)
2169 {
2170 const sal_uInt32 nCount(rCandidate.count());
2171
2172 if(nCount <= 2)
2173 return;
2174
2175 const B2DPoint aStart(rCandidate.getB2DPoint(0));
2176 B2DPoint aLast(rCandidate.getB2DPoint(1));
2177
2178 for(sal_uInt32 a(2); a < nCount; a++)
2179 {
2180 const B2DPoint aCurrent(rCandidate.getB2DPoint(a));
2181 rTarget.emplace_back(
2182 aStart,
2183 aLast,
2184 aCurrent);
2185
2186 // prepare next
2187 aLast = aCurrent;
2188 }
2189 }
2190
2191 namespace
2192 {
2193 /// return 0 for input of 0, -1 for negative and 1 for positive input
2194 int lcl_sgn( const double n )
2195 {
2196 return n == 0.0 ? 0 : 1 - 2*int(std::signbit(n));
2197 }
2198 }
2199
2200 bool isRectangle( const B2DPolygon& rPoly )
2201 {
2202 // polygon must be closed to resemble a rect, and contain
2203 // at least four points.
2204 if( !rPoly.isClosed() ||
2205 rPoly.count() < 4 ||
2206 rPoly.areControlPointsUsed() )
2207 {
2208 return false;
2209 }
2210
2211 // number of 90 degree turns the polygon has taken
2212 int nNumTurns(0);
2213
2214 int nVerticalEdgeType=0;
2215 int nHorizontalEdgeType=0;
2216 bool bNullVertex(true);
2217 bool bCWPolygon(false); // when true, polygon is CW
2218 // oriented, when false, CCW
2219 bool bOrientationSet(false); // when false, polygon
2220 // orientation has not yet
2221 // been determined.
2222
2223 // scan all _edges_ (which involves coming back to point 0
2224 // for the last edge - thus the modulo operation below)
2225 const sal_Int32 nCount( rPoly.count() );
2226 for( sal_Int32 i=0; i<nCount; ++i )
2227 {
2228 const B2DPoint& rPoint0( rPoly.getB2DPoint(i % nCount) );
2229 const B2DPoint& rPoint1( rPoly.getB2DPoint((i+1) % nCount) );
2230
2231 // is 0 for zero direction vector, 1 for south edge and -1
2232 // for north edge (standard screen coordinate system)
2233 int nCurrVerticalEdgeType( lcl_sgn( rPoint1.getY() - rPoint0.getY() ) );
2234
2235 // is 0 for zero direction vector, 1 for east edge and -1
2236 // for west edge (standard screen coordinate system)
2237 int nCurrHorizontalEdgeType( lcl_sgn(rPoint1.getX() - rPoint0.getX()) );
2238
2239 if( nCurrVerticalEdgeType && nCurrHorizontalEdgeType )
2240 return false; // oblique edge - for sure no rect
2241
2242 const bool bCurrNullVertex( !nCurrVerticalEdgeType && !nCurrHorizontalEdgeType );
2243
2244 // current vertex is equal to previous - just skip,
2245 // until we have a real edge
2246 if( bCurrNullVertex )
2247 continue;
2248
2249 // if previous edge has two identical points, because
2250 // no previous edge direction was available, simply
2251 // take this first non-null edge as the start
2252 // direction. That's what will happen here, if
2253 // bNullVertex is false
2254 if( !bNullVertex )
2255 {
2256 // 2D cross product - is 1 for CW and -1 for CCW turns
2257 const int nCrossProduct( nHorizontalEdgeType*nCurrVerticalEdgeType -
2258 nVerticalEdgeType*nCurrHorizontalEdgeType );
2259
2260 if( !nCrossProduct )
2261 continue; // no change in orientation -
2262 // collinear edges - just go on
2263
2264 // if polygon orientation is not set, we'll
2265 // determine it now
2266 if( !bOrientationSet )
2267 {
2268 bCWPolygon = nCrossProduct == 1;
2269 bOrientationSet = true;
2270 }
2271 else
2272 {
2273 // if current turn orientation is not equal
2274 // initial orientation, this is not a
2275 // rectangle (as rectangles have consistent
2276 // orientation).
2277 if( (nCrossProduct == 1) != bCWPolygon )
2278 return false;
2279 }
2280
2281 ++nNumTurns;
2282
2283 // More than four 90 degree turns are an
2284 // indication that this must not be a rectangle.
2285 if( nNumTurns > 4 )
2286 return false;
2287 }
2288
2289 // store current state for the next turn
2290 nVerticalEdgeType = nCurrVerticalEdgeType;
2291 nHorizontalEdgeType = nCurrHorizontalEdgeType;
2292 bNullVertex = false; // won't reach this line,
2293 // if bCurrNullVertex is
2294 // true - see above
2295 }
2296
2297 return true;
2298 }
2299
2300 B3DPolygon createB3DPolygonFromB2DPolygon(const B2DPolygon& rCandidate, double fZCoordinate)
2301 {
2302 if(rCandidate.areControlPointsUsed())
2303 {
2304 // call myself recursively with subdivided input
2305 const B2DPolygon aCandidate(adaptiveSubdivideByAngle(rCandidate));
2306 return createB3DPolygonFromB2DPolygon(aCandidate, fZCoordinate);
2307 }
2308 else
2309 {
2310 B3DPolygon aRetval;
2311
2312 for(sal_uInt32 a(0); a < rCandidate.count(); a++)
2313 {
2314 B2DPoint aPoint(rCandidate.getB2DPoint(a));
2315 aRetval.append(B3DPoint(aPoint.getX(), aPoint.getY(), fZCoordinate));
2316 }
2317
2318 // copy closed state
2319 aRetval.setClosed(rCandidate.isClosed());
2320
2321 return aRetval;
2322 }
2323 }
2324
2325 B2DPolygon createB2DPolygonFromB3DPolygon(const B3DPolygon& rCandidate, const B3DHomMatrix& rMat)
2326 {
2327 B2DPolygon aRetval;
2328 const sal_uInt32 nCount(rCandidate.count());
2329 const bool bIsIdentity(rMat.isIdentity());
2330
2331 for(sal_uInt32 a(0); a < nCount; a++)
2332 {
2333 B3DPoint aCandidate(rCandidate.getB3DPoint(a));
2334
2335 if(!bIsIdentity)
2336 {
2337 aCandidate *= rMat;
2338 }
2339
2340 aRetval.append(B2DPoint(aCandidate.getX(), aCandidate.getY()));
2341 }
2342
2343 // copy closed state
2344 aRetval.setClosed(rCandidate.isClosed());
2345
2346 return aRetval;
2347 }
2348
2349 double getSmallestDistancePointToEdge(const B2DPoint& rPointA, const B2DPoint& rPointB, const B2DPoint& rTestPoint, double& rCut)
2350 {
2351 if(rPointA.equal(rPointB))
2352 {
2353 rCut = 0.0;
2354 const B2DVector aVector(rTestPoint - rPointA);
2355 return aVector.getLength();
2356 }
2357 else
2358 {
2359 // get the relative cut value on line vector (Vector1) for cut with perpendicular through TestPoint
2360 const B2DVector aVector1(rPointB - rPointA);
2361 const B2DVector aVector2(rTestPoint - rPointA);
2362 const double fDividend((aVector2.getX() * aVector1.getX()) + (aVector2.getY() * aVector1.getY()));
2363 const double fDivisor((aVector1.getX() * aVector1.getX()) + (aVector1.getY() * aVector1.getY()));
2364 const double fCut(fDividend / fDivisor);
2365
2366 if(fCut < 0.0)
2367 {
2368 // not in line range, get distance to PointA
2369 rCut = 0.0;
2370 return aVector2.getLength();
2371 }
2372 else if(fCut > 1.0)
2373 {
2374 // not in line range, get distance to PointB
2375 rCut = 1.0;
2376 const B2DVector aVector(rTestPoint - rPointB);
2377 return aVector.getLength();
2378 }
2379 else
2380 {
2381 // in line range
2382 const B2DPoint aCutPoint(rPointA + fCut * aVector1);
2383 const B2DVector aVector(rTestPoint - aCutPoint);
2384 rCut = fCut;
2385 return aVector.getLength();
2386 }
2387 }
2388 }
2389
2390 double getSmallestDistancePointToPolygon(const B2DPolygon& rCandidate, const B2DPoint& rTestPoint, sal_uInt32& rEdgeIndex, double& rCut)
2391 {
2392 double fRetval(DBL_MAX);
2393 const sal_uInt32 nPointCount(rCandidate.count());
2394
2395 if(nPointCount > 1)
2396 {
2397 const double fZero(0.0);
2398 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1);
2399 B2DCubicBezier aBezier;
2400 aBezier.setStartPoint(rCandidate.getB2DPoint(0));
2401
2402 for(sal_uInt32 a(0); a < nEdgeCount; a++)
2403 {
2404 const sal_uInt32 nNextIndex((a + 1) % nPointCount);
2405 aBezier.setEndPoint(rCandidate.getB2DPoint(nNextIndex));
2406 double fEdgeDist;
2407 double fNewCut(0.0);
2408 bool bEdgeIsCurve(false);
2409
2410 if(rCandidate.areControlPointsUsed())
2411 {
2412 aBezier.setControlPointA(rCandidate.getNextControlPoint(a));
2413 aBezier.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex));
2414 aBezier.testAndSolveTrivialBezier();
2415 bEdgeIsCurve = aBezier.isBezier();
2416 }
2417
2418 if(bEdgeIsCurve)
2419 {
2420 fEdgeDist = aBezier.getSmallestDistancePointToBezierSegment(rTestPoint, fNewCut);
2421 }
2422 else
2423 {
2424 fEdgeDist = getSmallestDistancePointToEdge(aBezier.getStartPoint(), aBezier.getEndPoint(), rTestPoint, fNewCut);
2425 }
2426
2427 if(fRetval == DBL_MAX || fEdgeDist < fRetval)
2428 {
2429 fRetval = fEdgeDist;
2430 rEdgeIndex = a;
2431 rCut = fNewCut;
2432
2433 if(fTools::equal(fRetval, fZero))
2434 {
2435 // already found zero distance, cannot get better. Ensure numerical zero value and end loop.
2436 fRetval = 0.0;
2437 break;
2438 }
2439 }
2440
2441 // prepare next step
2442 aBezier.setStartPoint(aBezier.getEndPoint());
2443 }
2444
2445 if(rtl::math::approxEqual(1.0, rCut))
2446 {
2447 // correct rEdgeIndex when not last point
2448 if(rCandidate.isClosed())
2449 {
2450 rEdgeIndex = getIndexOfSuccessor(rEdgeIndex, rCandidate);
2451 rCut = 0.0;
2452 }
2453 else
2454 {
2455 if(rEdgeIndex != nEdgeCount - 1)
2456 {
2457 rEdgeIndex++;
2458 rCut = 0.0;
2459 }
2460 }
2461 }
2462 }
2463
2464 return fRetval;
2465 }
2466
2467 B2DPoint distort(const B2DPoint& rCandidate, const B2DRange& rOriginal, const B2DPoint& rTopLeft, const B2DPoint& rTopRight, const B2DPoint& rBottomLeft, const B2DPoint& rBottomRight)
2468 {
2469 if(fTools::equalZero(rOriginal.getWidth()) || fTools::equalZero(rOriginal.getHeight()))
2470 {
2471 return rCandidate;
2472 }
2473 else
2474 {
2475 const double fRelativeX((rCandidate.getX() - rOriginal.getMinX()) / rOriginal.getWidth());
2476 const double fRelativeY((rCandidate.getY() - rOriginal.getMinY()) / rOriginal.getHeight());
2477 const double fOneMinusRelativeX(1.0 - fRelativeX);
2478 const double fOneMinusRelativeY(1.0 - fRelativeY);
2479 const double fNewX(fOneMinusRelativeY * (fOneMinusRelativeX * rTopLeft.getX() + fRelativeX * rTopRight.getX()) +
2480 fRelativeY * (fOneMinusRelativeX * rBottomLeft.getX() + fRelativeX * rBottomRight.getX()));
2481 const double fNewY(fOneMinusRelativeX * (fOneMinusRelativeY * rTopLeft.getY() + fRelativeY * rBottomLeft.getY()) +
2482 fRelativeX * (fOneMinusRelativeY * rTopRight.getY() + fRelativeY * rBottomRight.getY()));
2483
2484 return B2DPoint(fNewX, fNewY);
2485 }
2486 }
2487
2488 B2DPolygon distort(const B2DPolygon& rCandidate, const B2DRange& rOriginal, const B2DPoint& rTopLeft, const B2DPoint& rTopRight, const B2DPoint& rBottomLeft, const B2DPoint& rBottomRight)
2489 {
2490 const sal_uInt32 nPointCount(rCandidate.count());
2491
2492 if(nPointCount && rOriginal.getWidth() != 0.0 && rOriginal.getHeight() != 0.0)
2493 {
2494 B2DPolygon aRetval;
2495
2496 for(sal_uInt32 a(0); a < nPointCount; a++)
2497 {
2498 aRetval.append(distort(rCandidate.getB2DPoint(a), rOriginal, rTopLeft, rTopRight, rBottomLeft, rBottomRight));
2499
2500 if(rCandidate.areControlPointsUsed())
2501 {
2502 if(!rCandidate.getPrevControlPoint(a).equalZero())
2503 {
2504 aRetval.setPrevControlPoint(a, distort(rCandidate.getPrevControlPoint(a), rOriginal, rTopLeft, rTopRight, rBottomLeft, rBottomRight));
2505 }
2506
2507 if(!rCandidate.getNextControlPoint(a).equalZero())
2508 {
2509 aRetval.setNextControlPoint(a, distort(rCandidate.getNextControlPoint(a), rOriginal, rTopLeft, rTopRight, rBottomLeft, rBottomRight));
2510 }
2511 }
2512 }
2513
2514 aRetval.setClosed(rCandidate.isClosed());
2515 return aRetval;
2516 }
2517 else
2518 {
2519 return rCandidate;
2520 }
2521 }
2522
2523 B2DPolygon expandToCurve(const B2DPolygon& rCandidate)
2524 {
2525 B2DPolygon aRetval(rCandidate);
2526
2527 for(sal_uInt32 a(0); a < rCandidate.count(); a++)
2528 {
2529 expandToCurveInPoint(aRetval, a);
2530 }
2531
2532 return aRetval;
2533 }
2534
2535 bool expandToCurveInPoint(B2DPolygon& rCandidate, sal_uInt32 nIndex)
2536 {
2537 OSL_ENSURE(nIndex < rCandidate.count(), "expandToCurveInPoint: Access to polygon out of range (!)");
2538 bool bRetval(false);
2539 const sal_uInt32 nPointCount(rCandidate.count());
2540
2541 if(nPointCount)
2542 {
2543 // predecessor
2544 if(!rCandidate.isPrevControlPointUsed(nIndex))
2545 {
2546 if(!rCandidate.isClosed() && nIndex == 0)
2547 {
2548 // do not create previous vector for start point of open polygon
2549 }
2550 else
2551 {
2552 const sal_uInt32 nPrevIndex((nIndex + (nPointCount - 1)) % nPointCount);
2553 rCandidate.setPrevControlPoint(nIndex, interpolate(rCandidate.getB2DPoint(nIndex), rCandidate.getB2DPoint(nPrevIndex), 1.0 / 3.0));
2554 bRetval = true;
2555 }
2556 }
2557
2558 // successor
2559 if(!rCandidate.isNextControlPointUsed(nIndex))
2560 {
2561 if(!rCandidate.isClosed() && nIndex + 1 == nPointCount)
2562 {
2563 // do not create next vector for end point of open polygon
2564 }
2565 else
2566 {
2567 const sal_uInt32 nNextIndex((nIndex + 1) % nPointCount);
2568 rCandidate.setNextControlPoint(nIndex, interpolate(rCandidate.getB2DPoint(nIndex), rCandidate.getB2DPoint(nNextIndex), 1.0 / 3.0));
2569 bRetval = true;
2570 }
2571 }
2572 }
2573
2574 return bRetval;
2575 }
2576
2577 bool setContinuityInPoint(B2DPolygon& rCandidate, sal_uInt32 nIndex, B2VectorContinuity eContinuity)
2578 {
2579 OSL_ENSURE(nIndex < rCandidate.count(), "setContinuityInPoint: Access to polygon out of range (!)");
2580 bool bRetval(false);
2581 const sal_uInt32 nPointCount(rCandidate.count());
2582
2583 if(nPointCount)
2584 {
2585 const B2DPoint aCurrentPoint(rCandidate.getB2DPoint(nIndex));
2586
2587 switch(eContinuity)
2588 {
2589 case B2VectorContinuity::NONE :
2590 {
2591 if(rCandidate.isPrevControlPointUsed(nIndex))
2592 {
2593 if(!rCandidate.isClosed() && nIndex == 0)
2594 {
2595 // remove existing previous vector for start point of open polygon
2596 rCandidate.resetPrevControlPoint(nIndex);
2597 }
2598 else
2599 {
2600 const sal_uInt32 nPrevIndex((nIndex + (nPointCount - 1)) % nPointCount);
2601 rCandidate.setPrevControlPoint(nIndex, interpolate(aCurrentPoint, rCandidate.getB2DPoint(nPrevIndex), 1.0 / 3.0));
2602 }
2603
2604 bRetval = true;
2605 }
2606
2607 if(rCandidate.isNextControlPointUsed(nIndex))
2608 {
2609 if(!rCandidate.isClosed() && nIndex == nPointCount + 1)
2610 {
2611 // remove next vector for end point of open polygon
2612 rCandidate.resetNextControlPoint(nIndex);
2613 }
2614 else
2615 {
2616 const sal_uInt32 nNextIndex((nIndex + 1) % nPointCount);
2617 rCandidate.setNextControlPoint(nIndex, interpolate(aCurrentPoint, rCandidate.getB2DPoint(nNextIndex), 1.0 / 3.0));
2618 }
2619
2620 bRetval = true;
2621 }
2622
2623 break;
2624 }
2625 case B2VectorContinuity::C1 :
2626 {
2627 if(rCandidate.isPrevControlPointUsed(nIndex) && rCandidate.isNextControlPointUsed(nIndex))
2628 {
2629 // lengths both exist since both are used
2630 B2DVector aVectorPrev(rCandidate.getPrevControlPoint(nIndex) - aCurrentPoint);
2631 B2DVector aVectorNext(rCandidate.getNextControlPoint(nIndex) - aCurrentPoint);
2632 const double fLenPrev(aVectorPrev.getLength());
2633 const double fLenNext(aVectorNext.getLength());
2634 aVectorPrev.normalize();
2635 aVectorNext.normalize();
2636 const B2VectorOrientation aOrientation(getOrientation(aVectorPrev, aVectorNext));
2637
2638 if(aOrientation == B2VectorOrientation::Neutral && aVectorPrev.scalar(aVectorNext) < 0.0)
2639 {
2640 // parallel and opposite direction; check length
2641 if(fTools::equal(fLenPrev, fLenNext))
2642 {
2643 // this would be even C2, but we want C1. Use the lengths of the corresponding edges.
2644 const sal_uInt32 nPrevIndex((nIndex + (nPointCount - 1)) % nPointCount);
2645 const sal_uInt32 nNextIndex((nIndex + 1) % nPointCount);
2646 const double fLenPrevEdge(B2DVector(rCandidate.getB2DPoint(nPrevIndex) - aCurrentPoint).getLength() * (1.0 / 3.0));
2647 const double fLenNextEdge(B2DVector(rCandidate.getB2DPoint(nNextIndex) - aCurrentPoint).getLength() * (1.0 / 3.0));
2648
2649 rCandidate.setControlPoints(nIndex,
2650 aCurrentPoint + (aVectorPrev * fLenPrevEdge),
2651 aCurrentPoint + (aVectorNext * fLenNextEdge));
2652 bRetval = true;
2653 }
2654 }
2655 else
2656 {
2657 // not parallel or same direction, set vectors and length
2658 const B2DVector aNormalizedPerpendicular(getNormalizedPerpendicular(aVectorPrev + aVectorNext));
2659
2660 if(aOrientation == B2VectorOrientation::Positive)
2661 {
2662 rCandidate.setControlPoints(nIndex,
2663 aCurrentPoint - (aNormalizedPerpendicular * fLenPrev),
2664 aCurrentPoint + (aNormalizedPerpendicular * fLenNext));
2665 }
2666 else
2667 {
2668 rCandidate.setControlPoints(nIndex,
2669 aCurrentPoint + (aNormalizedPerpendicular * fLenPrev),
2670 aCurrentPoint - (aNormalizedPerpendicular * fLenNext));
2671 }
2672
2673 bRetval = true;
2674 }
2675 }
2676 break;
2677 }
2678 case B2VectorContinuity::C2 :
2679 {
2680 if(rCandidate.isPrevControlPointUsed(nIndex) && rCandidate.isNextControlPointUsed(nIndex))
2681 {
2682 // lengths both exist since both are used
2683 B2DVector aVectorPrev(rCandidate.getPrevControlPoint(nIndex) - aCurrentPoint);
2684 B2DVector aVectorNext(rCandidate.getNextControlPoint(nIndex) - aCurrentPoint);
2685 const double fCommonLength((aVectorPrev.getLength() + aVectorNext.getLength()) / 2.0);
2686 aVectorPrev.normalize();
2687 aVectorNext.normalize();
2688 const B2VectorOrientation aOrientation(getOrientation(aVectorPrev, aVectorNext));
2689
2690 if(aOrientation == B2VectorOrientation::Neutral && aVectorPrev.scalar(aVectorNext) < 0.0)
2691 {
2692 // parallel and opposite direction; set length. Use one direction for better numerical correctness
2693 const B2DVector aScaledDirection(aVectorPrev * fCommonLength);
2694
2695 rCandidate.setControlPoints(nIndex,
2696 aCurrentPoint + aScaledDirection,
2697 aCurrentPoint - aScaledDirection);
2698 }
2699 else
2700 {
2701 // not parallel or same direction, set vectors and length
2702 const B2DVector aNormalizedPerpendicular(getNormalizedPerpendicular(aVectorPrev + aVectorNext));
2703 const B2DVector aPerpendicular(aNormalizedPerpendicular * fCommonLength);
2704
2705 if(aOrientation == B2VectorOrientation::Positive)
2706 {
2707 rCandidate.setControlPoints(nIndex,
2708 aCurrentPoint - aPerpendicular,
2709 aCurrentPoint + aPerpendicular);
2710 }
2711 else
2712 {
2713 rCandidate.setControlPoints(nIndex,
2714 aCurrentPoint + aPerpendicular,
2715 aCurrentPoint - aPerpendicular);
2716 }
2717 }
2718
2719 bRetval = true;
2720 }
2721 break;
2722 }
2723 }
2724 }
2725
2726 return bRetval;
2727 }
2728
2729 B2DPolygon growInNormalDirection(const B2DPolygon& rCandidate, double fValue)
2730 {
2731 if(fValue != 0.0)
2732 {
2733 if(rCandidate.areControlPointsUsed())
2734 {
2735 // call myself recursively with subdivided input
2736 const B2DPolygon aCandidate(adaptiveSubdivideByAngle(rCandidate));
2737 return growInNormalDirection(aCandidate, fValue);
2738 }
2739 else
2740 {
2741 B2DPolygon aRetval;
2742 const sal_uInt32 nPointCount(rCandidate.count());
2743
2744 if(nPointCount)
2745 {
2746 B2DPoint aPrev(rCandidate.getB2DPoint(nPointCount - 1));
2747 B2DPoint aCurrent(rCandidate.getB2DPoint(0));
2748
2749 for(sal_uInt32 a(0); a < nPointCount; a++)
2750 {
2751 const B2DPoint aNext(rCandidate.getB2DPoint(a + 1 == nPointCount ? 0 : a + 1));
2752 const B2DVector aBack(aPrev - aCurrent);
2753 const B2DVector aForw(aNext - aCurrent);
2754 const B2DVector aPerpBack(getNormalizedPerpendicular(aBack));
2755 const B2DVector aPerpForw(getNormalizedPerpendicular(aForw));
2756 B2DVector aDirection(aPerpBack - aPerpForw);
2757 aDirection.normalize();
2758 aDirection *= fValue;
2759 aRetval.append(aCurrent + aDirection);
2760
2761 // prepare next step
2762 aPrev = aCurrent;
2763 aCurrent = aNext;
2764 }
2765 }
2766
2767 // copy closed state
2768 aRetval.setClosed(rCandidate.isClosed());
2769
2770 return aRetval;
2771 }
2772 }
2773 else
2774 {
2775 return rCandidate;
2776 }
2777 }
2778
2779 B2DPolygon reSegmentPolygon(const B2DPolygon& rCandidate, sal_uInt32 nSegments)
2780 {
2781 B2DPolygon aRetval;
2782 const sal_uInt32 nPointCount(rCandidate.count());
2783
2784 if(nPointCount && nSegments)
2785 {
2786 // get current segment count
2787 const sal_uInt32 nSegmentCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1);
2788
2789 if(nSegmentCount == nSegments)
2790 {
2791 aRetval = rCandidate;
2792 }
2793 else
2794 {
2795 const double fLength(getLength(rCandidate));
2796 const sal_uInt32 nLoopCount(rCandidate.isClosed() ? nSegments : nSegments + 1);
2797
2798 for(sal_uInt32 a(0); a < nLoopCount; a++)
2799 {
2800 const double fRelativePos(static_cast<double>(a) / static_cast<double>(nSegments)); // 0.0 .. 1.0
2801 const B2DPoint aNewPoint(getPositionRelative(rCandidate, fRelativePos, fLength));
2802 aRetval.append(aNewPoint);
2803 }
2804
2805 // copy closed flag
2806 aRetval.setClosed(rCandidate.isClosed());
2807 }
2808 }
2809
2810 return aRetval;
2811 }
2812
2813 B2DPolygon interpolate(const B2DPolygon& rOld1, const B2DPolygon& rOld2, double t)
2814 {
2815 OSL_ENSURE(rOld1.count() == rOld2.count(), "B2DPolygon interpolate: Different geometry (!)");
2816
2817 if(t <= 0.0 || rOld1 == rOld2)
2818 {
2819 return rOld1;
2820 }
2821 else if(fTools::moreOrEqual(t, 1.0))
2822 {
2823 return rOld2;
2824 }
2825 else
2826 {
2827 B2DPolygon aRetval;
2828 const bool bInterpolateVectors(rOld1.areControlPointsUsed() || rOld2.areControlPointsUsed());
2829 aRetval.setClosed(rOld1.isClosed() && rOld2.isClosed());
2830
2831 for(sal_uInt32 a(0); a < rOld1.count(); a++)
2832 {
2833 aRetval.append(interpolate(rOld1.getB2DPoint(a), rOld2.getB2DPoint(a), t));
2834
2835 if(bInterpolateVectors)
2836 {
2837 aRetval.setPrevControlPoint(a, interpolate(rOld1.getPrevControlPoint(a), rOld2.getPrevControlPoint(a), t));
2838 aRetval.setNextControlPoint(a, interpolate(rOld1.getNextControlPoint(a), rOld2.getNextControlPoint(a), t));
2839 }
2840 }
2841
2842 return aRetval;
2843 }
2844 }
2845
2846 // #i76891#
2847 B2DPolygon simplifyCurveSegments(const B2DPolygon& rCandidate)
2848 {
2849 const sal_uInt32 nPointCount(rCandidate.count());
2850
2851 if(nPointCount && rCandidate.areControlPointsUsed())
2852 {
2853 // prepare loop
2854 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1);
2855 B2DPolygon aRetval;
2856 B2DCubicBezier aBezier;
2857 aBezier.setStartPoint(rCandidate.getB2DPoint(0));
2858
2859 // try to avoid costly reallocations
2860 aRetval.reserve( nEdgeCount+1);
2861
2862 // add start point
2863 aRetval.append(aBezier.getStartPoint());
2864
2865 for(sal_uInt32 a(0); a < nEdgeCount; a++)
2866 {
2867 // get values for edge
2868 const sal_uInt32 nNextIndex((a + 1) % nPointCount);
2869 aBezier.setEndPoint(rCandidate.getB2DPoint(nNextIndex));
2870 aBezier.setControlPointA(rCandidate.getNextControlPoint(a));
2871 aBezier.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex));
2872 aBezier.testAndSolveTrivialBezier();
2873
2874 // still bezier?
2875 if(aBezier.isBezier())
2876 {
2877 // add edge with control vectors
2878 aRetval.appendBezierSegment(aBezier.getControlPointA(), aBezier.getControlPointB(), aBezier.getEndPoint());
2879 }
2880 else
2881 {
2882 // add edge
2883 aRetval.append(aBezier.getEndPoint());
2884 }
2885
2886 // next point
2887 aBezier.setStartPoint(aBezier.getEndPoint());
2888 }
2889
2890 if(rCandidate.isClosed())
2891 {
2892 // set closed flag, rescue control point and correct last double point
2893 closeWithGeometryChange(aRetval);
2894 }
2895
2896 return aRetval;
2897 }
2898 else
2899 {
2900 return rCandidate;
2901 }
2902 }
2903
2904 // makes the given indexed point the new polygon start point. To do that, the points in the
2905 // polygon will be rotated. This is only valid for closed polygons, for non-closed ones
2906 // an assertion will be triggered
2907 B2DPolygon makeStartPoint(const B2DPolygon& rCandidate, sal_uInt32 nIndexOfNewStatPoint)
2908 {
2909 const sal_uInt32 nPointCount(rCandidate.count());
2910
2911 if(nPointCount > 2 && nIndexOfNewStatPoint != 0 && nIndexOfNewStatPoint < nPointCount)
2912 {
2913 OSL_ENSURE(rCandidate.isClosed(), "makeStartPoint: only valid for closed polygons (!)");
2914 B2DPolygon aRetval;
2915
2916 for(sal_uInt32 a(0); a < nPointCount; a++)
2917 {
2918 const sal_uInt32 nSourceIndex((a + nIndexOfNewStatPoint) % nPointCount);
2919 aRetval.append(rCandidate.getB2DPoint(nSourceIndex));
2920
2921 if(rCandidate.areControlPointsUsed())
2922 {
2923 aRetval.setPrevControlPoint(a, rCandidate.getPrevControlPoint(nSourceIndex));
2924 aRetval.setNextControlPoint(a, rCandidate.getNextControlPoint(nSourceIndex));
2925 }
2926 }
2927
2928 return aRetval;
2929 }
2930
2931 return rCandidate;
2932 }
2933
2934 B2DPolygon createEdgesOfGivenLength(const B2DPolygon& rCandidate, double fLength, double fStart, double fEnd)
2935 {
2936 B2DPolygon aRetval;
2937
2938 if(fLength < 0.0)
2939 {
2940 fLength = 0.0;
2941 }
2942
2943 if(!fTools::equalZero(fLength))
2944 {
2945 if(fStart < 0.0)
2946 {
2947 fStart = 0.0;
2948 }
2949
2950 if(fEnd < 0.0)
2951 {
2952 fEnd = 0.0;
2953 }
2954
2955 if(fEnd < fStart)
2956 {
2957 fEnd = fStart;
2958 }
2959
2960 // iterate and consume pieces with fLength. First subdivide to reduce input to line segments
2961 const B2DPolygon aCandidate(rCandidate.areControlPointsUsed() ? rCandidate.getDefaultAdaptiveSubdivision() : rCandidate);
2962 const sal_uInt32 nPointCount(aCandidate.count());
2963
2964 if(nPointCount > 1)
2965 {
2966 const bool bEndActive(!fTools::equalZero(fEnd));
2967 const sal_uInt32 nEdgeCount(aCandidate.isClosed() ? nPointCount : nPointCount - 1);
2968 B2DPoint aCurrent(aCandidate.getB2DPoint(0));
2969 double fPositionInEdge(fStart);
2970 double fAbsolutePosition(fStart);
2971
2972 for(sal_uInt32 a(0); a < nEdgeCount; a++)
2973 {
2974 const sal_uInt32 nNextIndex((a + 1) % nPointCount);
2975 const B2DPoint aNext(aCandidate.getB2DPoint(nNextIndex));
2976 const B2DVector aEdge(aNext - aCurrent);
2977 double fEdgeLength(aEdge.getLength());
2978
2979 if(!fTools::equalZero(fEdgeLength))
2980 {
2981 while(fTools::less(fPositionInEdge, fEdgeLength))
2982 {
2983 // move position on edge forward as long as on edge
2984 const double fScalar(fPositionInEdge / fEdgeLength);
2985 aRetval.append(aCurrent + (aEdge * fScalar));
2986 fPositionInEdge += fLength;
2987
2988 if(bEndActive)
2989 {
2990 fAbsolutePosition += fLength;
2991
2992 if(fTools::more(fAbsolutePosition, fEnd))
2993 {
2994 break;
2995 }
2996 }
2997 }
2998
2999 // subtract length of current edge
3000 fPositionInEdge -= fEdgeLength;
3001 }
3002
3003 if(bEndActive && fTools::more(fAbsolutePosition, fEnd))
3004 {
3005 break;
3006 }
3007
3008 // prepare next step
3009 aCurrent = aNext;
3010 }
3011
3012 // keep closed state
3013 aRetval.setClosed(aCandidate.isClosed());
3014 }
3015 else
3016 {
3017 // source polygon has only one point, return unchanged
3018 aRetval = aCandidate;
3019 }
3020 }
3021
3022 return aRetval;
3023 }
3024
3025 B2DPolygon createWaveline(const B2DPolygon& rCandidate, double fWaveWidth, double fWaveHeight)
3026 {
3027 B2DPolygon aRetval;
3028
3029 if(fWaveWidth < 0.0)
3030 {
3031 fWaveWidth = 0.0;
3032 }
3033
3034 if(fWaveHeight < 0.0)
3035 {
3036 fWaveHeight = 0.0;
3037 }
3038
3039 const bool bHasWidth(!fTools::equalZero(fWaveWidth));
3040
3041 if(bHasWidth)
3042 {
3043 const bool bHasHeight(!fTools::equalZero(fWaveHeight));
3044 if(bHasHeight)
3045 {
3046 // width and height, create waveline. First subdivide to reduce input to line segments
3047 // of WaveWidth. Last segment may be missing. If this turns out to be a problem, it
3048 // may be added here again using the original last point from rCandidate. It may
3049 // also be the case that rCandidate was closed. To simplify things it is handled here
3050 // as if it was opened.
3051 // Result from createEdgesOfGivenLength contains no curved segments, handle as straight
3052 // edges.
3053 const B2DPolygon aEqualLenghEdges(createEdgesOfGivenLength(rCandidate, fWaveWidth));
3054 const sal_uInt32 nPointCount(aEqualLenghEdges.count());
3055
3056 if(nPointCount > 1)
3057 {
3058 // iterate over straight edges, add start point
3059 B2DPoint aCurrent(aEqualLenghEdges.getB2DPoint(0));
3060 aRetval.append(aCurrent);
3061
3062 for(sal_uInt32 a(0); a < nPointCount - 1; a++)
3063 {
3064 const sal_uInt32 nNextIndex((a + 1) % nPointCount);
3065 const B2DPoint aNext(aEqualLenghEdges.getB2DPoint(nNextIndex));
3066 const B2DVector aEdge(aNext - aCurrent);
3067 const B2DVector aPerpendicular(getNormalizedPerpendicular(aEdge));
3068 const B2DVector aControlOffset((aEdge * 0.467308) - (aPerpendicular * fWaveHeight));
3069
3070 // add curve segment
3071 aRetval.appendBezierSegment(
3072 aCurrent + aControlOffset,
3073 aNext - aControlOffset,
3074 aNext);
3075
3076 // prepare next step
3077 aCurrent = aNext;
3078 }
3079 }
3080 }
3081 else
3082 {
3083 // width but no height -> return original polygon
3084 aRetval = rCandidate;
3085 }
3086 }
3087 else
3088 {
3089 // no width -> no waveline, stay empty and return
3090 }
3091
3092 return aRetval;
3093 }
3094
3095 // snap points of horizontal or vertical edges to discrete values
3096 B2DPolygon snapPointsOfHorizontalOrVerticalEdges(const B2DPolygon& rCandidate)
3097 {
3098 const sal_uInt32 nPointCount(rCandidate.count());
3099
3100 if(nPointCount > 1)
3101 {
3102 // Start by copying the source polygon to get a writeable copy. The closed state is
3103 // copied by aRetval's initialisation, too, so no need to copy it in this method
3104 B2DPolygon aRetval(rCandidate);
3105
3106 // prepare geometry data. Get rounded from original
3107 B2ITuple aPrevTuple(basegfx::fround(rCandidate.getB2DPoint(nPointCount - 1)));
3108 B2DPoint aCurrPoint(rCandidate.getB2DPoint(0));
3109 B2ITuple aCurrTuple(basegfx::fround(aCurrPoint));
3110
3111 // loop over all points. This will also snap the implicit closing edge
3112 // even when not closed, but that's no problem here
3113 for(sal_uInt32 a(0); a < nPointCount; a++)
3114 {
3115 // get next point. Get rounded from original
3116 const bool bLastRun(a + 1 == nPointCount);
3117 const sal_uInt32 nNextIndex(bLastRun ? 0 : a + 1);
3118 const B2DPoint aNextPoint(rCandidate.getB2DPoint(nNextIndex));
3119 const B2ITuple aNextTuple(basegfx::fround(aNextPoint));
3120
3121 // get the states
3122 const bool bPrevVertical(aPrevTuple.getX() == aCurrTuple.getX());
3123 const bool bNextVertical(aNextTuple.getX() == aCurrTuple.getX());
3124 const bool bPrevHorizontal(aPrevTuple.getY() == aCurrTuple.getY());
3125 const bool bNextHorizontal(aNextTuple.getY() == aCurrTuple.getY());
3126 const bool bSnapX(bPrevVertical || bNextVertical);
3127 const bool bSnapY(bPrevHorizontal || bNextHorizontal);
3128
3129 if(bSnapX || bSnapY)
3130 {
3131 const B2DPoint aSnappedPoint(
3132 bSnapX ? aCurrTuple.getX() : aCurrPoint.getX(),
3133 bSnapY ? aCurrTuple.getY() : aCurrPoint.getY());
3134
3135 aRetval.setB2DPoint(a, aSnappedPoint);
3136 }
3137
3138 // prepare next point
3139 if(!bLastRun)
3140 {
3141 aPrevTuple = aCurrTuple;
3142 aCurrPoint = aNextPoint;
3143 aCurrTuple = aNextTuple;
3144 }
3145 }
3146
3147 return aRetval;
3148 }
3149 else
3150 {
3151 return rCandidate;
3152 }
3153 }
3154
3155 B2DVector getTangentEnteringPoint(const B2DPolygon& rCandidate, sal_uInt32 nIndex)
3156 {
3157 B2DVector aRetval(0.0, 0.0);
3158 const sal_uInt32 nCount(rCandidate.count());
3159
3160 if(nIndex >= nCount)
3161 {
3162 // out of range
3163 return aRetval;
3164 }
3165
3166 // start immediately at prev point compared to nIndex
3167 const bool bClosed(rCandidate.isClosed());
3168 sal_uInt32 nPrev(bClosed ? (nIndex + nCount - 1) % nCount : nIndex ? nIndex - 1 : nIndex);
3169
3170 if(nPrev == nIndex)
3171 {
3172 // no previous, done
3173 return aRetval;
3174 }
3175
3176 B2DCubicBezier aSegment;
3177
3178 // go backward in the polygon; if closed, maximal back to start index (nIndex); if not closed,
3179 // until zero. Use nIndex as stop criteria
3180 while(nPrev != nIndex)
3181 {
3182 // get BezierSegment and tangent at the *end* of segment
3183 rCandidate.getBezierSegment(nPrev, aSegment);
3184 aRetval = aSegment.getTangent(1.0);
3185
3186 if(!aRetval.equalZero())
3187 {
3188 // if we have a tangent, return it
3189 return aRetval;
3190 }
3191
3192 // prepare index before checked one
3193 nPrev = bClosed ? (nPrev + nCount - 1) % nCount : nPrev ? nPrev - 1 : nIndex;
3194 }
3195
3196 return aRetval;
3197 }
3198
3199 B2DVector getTangentLeavingPoint(const B2DPolygon& rCandidate, sal_uInt32 nIndex)
3200 {
3201 B2DVector aRetval(0.0, 0.0);
3202 const sal_uInt32 nCount(rCandidate.count());
3203
3204 if(nIndex >= nCount)
3205 {
3206 // out of range
3207 return aRetval;
3208 }
3209
3210 // start at nIndex
3211 const bool bClosed(rCandidate.isClosed());
3212 sal_uInt32 nCurrent(nIndex);
3213 B2DCubicBezier aSegment;
3214
3215 // go forward; if closed, do this until once around and back at start index (nIndex); if not
3216 // closed, until last point (nCount - 1). Use nIndex as stop criteria
3217 do
3218 {
3219 // get BezierSegment and tangent at the *beginning* of segment
3220 rCandidate.getBezierSegment(nCurrent, aSegment);
3221 aRetval = aSegment.getTangent(0.0);
3222
3223 if(!aRetval.equalZero())
3224 {
3225 // if we have a tangent, return it
3226 return aRetval;
3227 }
3228
3229 // prepare next index
3230 nCurrent = bClosed ? (nCurrent + 1) % nCount : nCurrent + 1 < nCount ? nCurrent + 1 : nIndex;
3231 }
3232 while(nCurrent != nIndex);
3233
3234 return aRetval;
3235 }
3236
3237 // converters for css::drawing::PointSequence
3238
3239 B2DPolygon UnoPointSequenceToB2DPolygon(
3240 const css::drawing::PointSequence& rPointSequenceSource)
3241 {
3242 B2DPolygon aRetval;
3243 const sal_uInt32 nLength(rPointSequenceSource.getLength());
3244
3245 if(nLength)
3246 {
3247 aRetval.reserve(nLength);
3248
3249 for(auto& point : rPointSequenceSource)
3250 {
3251 aRetval.append(B2DPoint(point.X, point.Y));
3252 }
3253
3254 // check for closed state flag
3255 utils::checkClosed(aRetval);
3256 }
3257
3258 return aRetval;
3259 }
3260
3261 void B2DPolygonToUnoPointSequence(
3262 const B2DPolygon& rPolygon,
3263 css::drawing::PointSequence& rPointSequenceRetval)
3264 {
3265 B2DPolygon aPolygon(rPolygon);
3266
3267 if(aPolygon.areControlPointsUsed())
3268 {
3269 OSL_ENSURE(false, "B2DPolygonToUnoPointSequence: Source contains bezier segments, wrong UNO API data type may be used (!)");
3270 aPolygon = aPolygon.getDefaultAdaptiveSubdivision();
3271 }
3272
3273 const sal_uInt32 nPointCount(aPolygon.count());
3274
3275 if(nPointCount)
3276 {
3277 // Take closed state into account, the API polygon still uses the old closed definition
3278 // with last/first point are identical (cannot hold information about open polygons with identical
3279 // first and last point, though)
3280 const bool bIsClosed(aPolygon.isClosed());
3281
3282 rPointSequenceRetval.realloc(bIsClosed ? nPointCount + 1 : nPointCount);
3283 css::awt::Point* pSequence = rPointSequenceRetval.getArray();
3284
3285 for(sal_uInt32 b(0); b < nPointCount; b++)
3286 {
3287 const B2DPoint aPoint(aPolygon.getB2DPoint(b));
3288 const css::awt::Point aAPIPoint(fround(aPoint.getX()), fround(aPoint.getY()));
3289
3290 *pSequence = aAPIPoint;
3291 pSequence++;
3292 }
3293
3294 // copy first point if closed
3295 if(bIsClosed)
3296 {
3297 *pSequence = rPointSequenceRetval[0];
3298 }
3299 }
3300 else
3301 {
3302 rPointSequenceRetval.realloc(0);
3303 }
3304 }
3305
3306 // converters for css::drawing::PointSequence and
3307 // css::drawing::FlagSequence to B2DPolygon (curved polygons)
3308
3309 B2DPolygon UnoPolygonBezierCoordsToB2DPolygon(
3310 const css::drawing::PointSequence& rPointSequenceSource,
3311 const css::drawing::FlagSequence& rFlagSequenceSource)
3312 {
3313 const sal_Int32 nCount(rPointSequenceSource.getLength());
3314 OSL_ENSURE(nCount == rFlagSequenceSource.getLength(),
3315 "UnoPolygonBezierCoordsToB2DPolygon: Unequal count of Points and Flags (!)");
3316
3317 // prepare new polygon
3318 B2DPolygon aRetval;
3319
3320 if(0 != nCount)
3321 {
3322 aRetval.reserve(nCount);
3323
3324 // get first point and flag
3325 B2DPoint aNewCoordinatePair(rPointSequenceSource[0].X, rPointSequenceSource[0].Y);
3326 B2DPoint aControlA;
3327 B2DPoint aControlB;
3328
3329 // first point is not allowed to be a control point
3330 OSL_ENSURE(rFlagSequenceSource[0] != css::drawing::PolygonFlags_CONTROL,
3331 "UnoPolygonBezierCoordsToB2DPolygon: Start point is a control point, illegal input polygon (!)");
3332
3333 // add first point as start point
3334 aRetval.append(aNewCoordinatePair);
3335
3336 for(sal_Int32 b(1); b < nCount;)
3337 {
3338 // prepare loop
3339 bool bControlA(false);
3340 bool bControlB(false);
3341
3342 // get next point and flag
3343 aNewCoordinatePair = B2DPoint(rPointSequenceSource[b].X, rPointSequenceSource[b].Y);
3344 css::drawing::PolygonFlags ePolygonFlag = rFlagSequenceSource[b];
3345 b++;
3346
3347 if(b < nCount && ePolygonFlag == css::drawing::PolygonFlags_CONTROL)
3348 {
3349 aControlA = aNewCoordinatePair;
3350 bControlA = true;
3351
3352 // get next point and flag
3353 aNewCoordinatePair = B2DPoint(rPointSequenceSource[b].X, rPointSequenceSource[b].Y);
3354 ePolygonFlag = rFlagSequenceSource[b];
3355 b++;
3356 }
3357
3358 if(b < nCount && ePolygonFlag == css::drawing::PolygonFlags_CONTROL)
3359 {
3360 aControlB = aNewCoordinatePair;
3361 bControlB = true;
3362
3363 // get next point and flag
3364 aNewCoordinatePair = B2DPoint(rPointSequenceSource[b].X, rPointSequenceSource[b].Y);
3365 ePolygonFlag = rFlagSequenceSource[b];
3366 b++;
3367 }
3368
3369 // two or no control points are consumed, another one would be an error.
3370 // It's also an error if only one control point was read
3371 SAL_WARN_IF(ePolygonFlag == css::drawing::PolygonFlags_CONTROL || bControlA != bControlB,
3372 "basegfx", "UnoPolygonBezierCoordsToB2DPolygon: Illegal source polygon (!)");
3373
3374 // the previous writes used the B2DPolyPolygon -> utils::PolyPolygon converter
3375 // which did not create minimal PolyPolygons, but created all control points
3376 // as null vectors (identical points). Because of the former P(CA)(CB)-norm of
3377 // B2DPolygon and it's unused sign of being the zero-vector and CA and CB being
3378 // relative to P, an empty edge was exported as P == CA == CB. Luckily, the new
3379 // export format can be read without errors by the old OOo-versions, so we need only
3380 // to correct here at read and do not need to export a wrong but compatible version
3381 // for the future.
3382 if(bControlA
3383 && aControlA.equal(aControlB)
3384 && aControlA.equal(aRetval.getB2DPoint(aRetval.count() - 1)))
3385 {
3386 bControlA = false;
3387 }
3388
3389 if(bControlA)
3390 {
3391 // add bezier edge
3392 aRetval.appendBezierSegment(aControlA, aControlB, aNewCoordinatePair);
3393 }
3394 else
3395 {
3396 // add edge
3397 aRetval.append(aNewCoordinatePair);
3398 }
3399 }
3400
3401 // #i72807# API import uses old line start/end-equal definition for closed,
3402 // so we need to correct this to closed state here
3403 checkClosed(aRetval);
3404 }
3405
3406 return aRetval;
3407 }
3408
3409 void B2DPolygonToUnoPolygonBezierCoords(
3410 const B2DPolygon& rPolygon,
3411 css::drawing::PointSequence& rPointSequenceRetval,
3412 css::drawing::FlagSequence& rFlagSequenceRetval)
3413 {
3414 const sal_uInt32 nPointCount(rPolygon.count());
3415
3416 if(nPointCount)
3417 {
3418 const bool bCurve(rPolygon.areControlPointsUsed());
3419 const bool bClosed(rPolygon.isClosed());
3420
3421 if(bCurve)
3422 {
3423 // calculate target point count
3424 const sal_uInt32 nLoopCount(bClosed ? nPointCount : nPointCount - 1);
3425
3426 if(nLoopCount)
3427 {
3428 // prepare target data. The real needed number of target points (and flags)
3429 // could only be calculated by using two loops, so use dynamic memory
3430 std::vector< css::awt::Point > aCollectPoints;
3431 std::vector< css::drawing::PolygonFlags > aCollectFlags;
3432
3433 // reserve maximum creatable points
3434 const sal_uInt32 nMaxTargetCount((nLoopCount * 3) + 1);
3435 aCollectPoints.reserve(nMaxTargetCount);
3436 aCollectFlags.reserve(nMaxTargetCount);
3437
3438 // prepare current bezier segment by setting start point
3439 B2DCubicBezier aBezierSegment;
3440 aBezierSegment.setStartPoint(rPolygon.getB2DPoint(0));
3441
3442 for(sal_uInt32 a(0); a < nLoopCount; a++)
3443 {
3444 // add current point (always) and remember StartPointIndex for evtl. later corrections
3445 const sal_uInt32 nStartPointIndex(aCollectPoints.size());
3446 aCollectPoints.emplace_back(
3447 fround(aBezierSegment.getStartPoint().getX()),
3448 fround(aBezierSegment.getStartPoint().getY()));
3449 aCollectFlags.push_back(css::drawing::PolygonFlags_NORMAL);
3450
3451 // prepare next segment
3452 const sal_uInt32 nNextIndex((a + 1) % nPointCount);
3453 aBezierSegment.setEndPoint(rPolygon.getB2DPoint(nNextIndex));
3454 aBezierSegment.setControlPointA(rPolygon.getNextControlPoint(a));
3455 aBezierSegment.setControlPointB(rPolygon.getPrevControlPoint(nNextIndex));
3456
3457 if(aBezierSegment.isBezier())
3458 {
3459 // if bezier is used, add always two control points due to the old schema
3460 aCollectPoints.emplace_back(
3461 fround(aBezierSegment.getControlPointA().getX()),
3462 fround(aBezierSegment.getControlPointA().getY()));
3463 aCollectFlags.push_back(css::drawing::PolygonFlags_CONTROL);
3464
3465 aCollectPoints.emplace_back(
3466 fround(aBezierSegment.getControlPointB().getX()),
3467 fround(aBezierSegment.getControlPointB().getY()));
3468 aCollectFlags.push_back(css::drawing::PolygonFlags_CONTROL);
3469 }
3470
3471 // test continuity with previous control point to set flag value
3472 if(aBezierSegment.getControlPointA() != aBezierSegment.getStartPoint() && (bClosed || a))
3473 {
3474 const B2VectorContinuity eCont(rPolygon.getContinuityInPoint(a));
3475
3476 if(eCont == B2VectorContinuity::C1)
3477 {
3478 aCollectFlags[nStartPointIndex] = css::drawing::PolygonFlags_SMOOTH;
3479 }
3480 else if(eCont == B2VectorContinuity::C2)
3481 {
3482 aCollectFlags[nStartPointIndex] = css::drawing::PolygonFlags_SYMMETRIC;
3483 }
3484 }
3485
3486 // prepare next loop
3487 aBezierSegment.setStartPoint(aBezierSegment.getEndPoint());
3488 }
3489
3490 if(bClosed)
3491 {
3492 // add first point again as closing point due to old definition
3493 aCollectPoints.push_back(aCollectPoints[0]);
3494 aCollectFlags.push_back(css::drawing::PolygonFlags_NORMAL);
3495 }
3496 else
3497 {
3498 // add last point as closing point
3499 const B2DPoint aClosingPoint(rPolygon.getB2DPoint(nPointCount - 1));
3500 aCollectPoints.emplace_back(
3501 fround(aClosingPoint.getX()),
3502 fround(aClosingPoint.getY()));
3503 aCollectFlags.push_back(css::drawing::PolygonFlags_NORMAL);
3504 }
3505
3506 // copy collected data to target arrays
3507 const sal_uInt32 nTargetCount(aCollectPoints.size());
3508 OSL_ENSURE(nTargetCount == aCollectFlags.size(), "Unequal Point and Flag count (!)");
3509
3510 rPointSequenceRetval.realloc(static_cast<sal_Int32>(nTargetCount));
3511 rFlagSequenceRetval.realloc(static_cast<sal_Int32>(nTargetCount));
3512 css::awt::Point* pPointSequence = rPointSequenceRetval.getArray();
3513 css::drawing::PolygonFlags* pFlagSequence = rFlagSequenceRetval.getArray();
3514
3515 for(sal_uInt32 a(0); a < nTargetCount; a++)
3516 {
3517 *pPointSequence = aCollectPoints[a];
3518 *pFlagSequence = aCollectFlags[a];
3519 pPointSequence++;
3520 pFlagSequence++;
3521 }
3522 }
3523 }
3524 else
3525 {
3526 // straightforward point list creation
3527 const sal_uInt32 nTargetCount(nPointCount + (bClosed ? 1 : 0));
3528
3529 rPointSequenceRetval.realloc(static_cast<sal_Int32>(nTargetCount));
3530 rFlagSequenceRetval.realloc(static_cast<sal_Int32>(nTargetCount));
3531
3532 css::awt::Point* pPointSequence = rPointSequenceRetval.getArray();
3533 css::drawing::PolygonFlags* pFlagSequence = rFlagSequenceRetval.getArray();
3534
3535 for(sal_uInt32 a(0); a < nPointCount; a++)
3536 {
3537 const B2DPoint aB2DPoint(rPolygon.getB2DPoint(a));
3538 const css::awt::Point aAPIPoint(
3539 fround(aB2DPoint.getX()),
3540 fround(aB2DPoint.getY()));
3541
3542 *pPointSequence = aAPIPoint;
3543 *pFlagSequence = css::drawing::PolygonFlags_NORMAL;
3544 pPointSequence++;
3545 pFlagSequence++;
3546 }
3547
3548 if(bClosed)
3549 {
3550 // add first point as closing point
3551 *pPointSequence = rPointSequenceRetval[0];
3552 *pFlagSequence = css::drawing::PolygonFlags_NORMAL;
3553 }
3554 }
3555 }
3556 else
3557 {
3558 rPointSequenceRetval.realloc(0);
3559 rFlagSequenceRetval.realloc(0);
3560 }
3561 }
3562
3563 B2DPolygon createSimplifiedPolygon(const B2DPolygon& rCandidate, const double fTolerance)
3564 {
3565 const sal_uInt32 nPointCount(rCandidate.count());
3566 if (nPointCount < 3 || rCandidate.areControlPointsUsed())
3567 return rCandidate;
3568
3569 // The solution does not use recursion directly, since this could lead to a stack overflow if
3570 // nPointCount is very large. Instead, an own stack is used. This does not contain points, but
3571 // pairs of low and high index of a range in rCandidate. A parallel boolean vector is used to note
3572 // whether a point of rCandidate belongs to the output polygon or not.
3573 std::vector<bool> bIsKeptVec(nPointCount, false);
3574 bIsKeptVec[0] = true;
3575 bIsKeptVec[nPointCount - 1] = true;
3576 sal_uInt32 nKept = 2;
3577 std::stack<std::pair<sal_uInt32, sal_uInt32>> aUnfinishedRangesStack;
3578
3579 // The RDP algorithm draws a straight line from the first point to the last point of a range.
3580 // Then, from the inner points of the range, the point that has the largest distance to the line
3581 // is determined. If the distance is greater than the tolerance, this point is kept and the lower
3582 // and upper sub-segments of the range are treated in the same way. If the distance is smaller
3583 // than the tolerance, none of the inner points will be kept.
3584 sal_uInt32 nLowIndex = 0;
3585 sal_uInt32 nHighIndex = nPointCount - 1;
3586 bool bContinue = true;
3587 do
3588 {
3589 bContinue = false;
3590 if (nHighIndex - nLowIndex < 2) // maximal two points, range is finished.
3591 {
3592 // continue with sibling upper range if any
3593 if (!aUnfinishedRangesStack.empty())
3594 {
3595 std::pair<sal_uInt32, sal_uInt32> aIndexPair = aUnfinishedRangesStack.top();
3596 aUnfinishedRangesStack.pop();
3597 nLowIndex = aIndexPair.first;
3598 nHighIndex = aIndexPair.second;
3599 bContinue = true;
3600 }
3601 }
3602 else // the range needs examine the max distance
3603 {
3604 // Get maximal distance of inner points of the range to the straight line from start to
3605 // end point of the range.
3606 // For calculation of the distance we use the Hesse normal form of the straight line.
3607 B2DPoint aLowPoint = rCandidate.getB2DPoint(nLowIndex);
3608 B2DPoint aHighPoint = rCandidate.getB2DPoint(nHighIndex);
3609 B2DVector aNormalVec
3610 = basegfx::getNormalizedPerpendicular(B2DVector(aHighPoint) - B2DVector(aLowPoint));
3611 double fLineOriginDistance = aNormalVec.scalar(B2DVector(aLowPoint));
3612 double fMaxDist = 0;
3613 sal_uInt32 nMaxPointIndex = nLowIndex;
3614 for (sal_uInt32 i = nLowIndex + 1; i < nHighIndex; i++)
3615 {
3616 double fDistance
3617 = aNormalVec.scalar(B2DVector(rCandidate.getB2DPoint(i))) - fLineOriginDistance;
3618 if (std::fabs(fDistance) > fMaxDist)
3619 {
3620 fMaxDist = std::fabs(fDistance);
3621 nMaxPointIndex = i;
3622 }
3623 }
3624
3625 if (fMaxDist >= fTolerance)
3626 {
3627 // We need to divide the current range into two sub ranges.
3628 bIsKeptVec[nMaxPointIndex] = true;
3629 nKept++;
3630 // continue with lower sub range and push upper sub range to stack
3631 aUnfinishedRangesStack.push(std::make_pair(nMaxPointIndex, nHighIndex));
3632 nHighIndex = nMaxPointIndex;
3633 bContinue = true;
3634 }
3635 else
3636 {
3637 // We do not keep any of the inner points of the current range.
3638 // continue with sibling upper range if any
3639 if (!aUnfinishedRangesStack.empty())
3640 {
3641 std::pair<sal_uInt32, sal_uInt32> aIndexPair = aUnfinishedRangesStack.top();
3642 aUnfinishedRangesStack.pop();
3643 nLowIndex = aIndexPair.first;
3644 nHighIndex = aIndexPair.second;
3645 bContinue = true;
3646 }
3647 }
3648 }
3649 } while (bContinue);
3650
3651 // Put all points which are marked as "keep" into the result polygon
3652 B2DPolygon aResultPolygon;
3653 aResultPolygon.reserve(nKept);
3654 for (sal_uInt32 i = 0; i < nPointCount; i++)
3655 {
3656 if (bIsKeptVec[i])
3657 aResultPolygon.append(rCandidate.getB2DPoint(i));
3658 }
3659 return aResultPolygon;
3660 }
3661
3662 } // end of namespace
3663
3664 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
FREE OFFICE SUITE