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