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