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