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