?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
fdo#74697 Add Bluez 5 support for impress remote.
[LibreOffice.git] / basegfx / source / polygon / b2dpolygontools.cxx
blob24affdfb84c9b3fd72b7dbbd595819d4b6b965e0
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 fRetval /= 2.0;
493
494 // correct to zero if small enough. Also test the quadratic
495 // of the result since the precision is near quadratic due to
496 // the algorithm
497 if(fTools::equalZero(fRetval) || fTools::equalZero(fRetval * fRetval))
498 {
499 fRetval = 0.0;
500 }
501 }
502
503 return fRetval;
504 }
505
506 double getArea(const B2DPolygon& rCandidate)
507 {
508 double fRetval(0.0);
509
510 if(rCandidate.count() > 2 || rCandidate.areControlPointsUsed())
511 {
512 fRetval = getSignedArea(rCandidate);
513 const double fZero(0.0);
514
515 if(fTools::less(fRetval, fZero))
516 {
517 fRetval = -fRetval;
518 }
519 }
520
521 return fRetval;
522 }
523
524 double getEdgeLength(const B2DPolygon& rCandidate, sal_uInt32 nIndex)
525 {
526 const sal_uInt32 nPointCount(rCandidate.count());
527 OSL_ENSURE(nIndex < nPointCount, "getEdgeLength: Access to polygon out of range (!)");
528 double fRetval(0.0);
529
530 if(nPointCount)
531 {
532 const sal_uInt32 nNextIndex((nIndex + 1) % nPointCount);
533
534 if(rCandidate.areControlPointsUsed())
535 {
536 B2DCubicBezier aEdge;
537
538 aEdge.setStartPoint(rCandidate.getB2DPoint(nIndex));
539 aEdge.setControlPointA(rCandidate.getNextControlPoint(nIndex));
540 aEdge.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex));
541 aEdge.setEndPoint(rCandidate.getB2DPoint(nNextIndex));
542
543 fRetval = aEdge.getLength();
544 }
545 else
546 {
547 const B2DPoint aCurrent(rCandidate.getB2DPoint(nIndex));
548 const B2DPoint aNext(rCandidate.getB2DPoint(nNextIndex));
549
550 fRetval = B2DVector(aNext - aCurrent).getLength();
551 }
552 }
553
554 return fRetval;
555 }
556
557 double getLength(const B2DPolygon& rCandidate)
558 {
559 double fRetval(0.0);
560 const sal_uInt32 nPointCount(rCandidate.count());
561
562 if(nPointCount)
563 {
564 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1L);
565
566 if(rCandidate.areControlPointsUsed())
567 {
568 B2DCubicBezier aEdge;
569 aEdge.setStartPoint(rCandidate.getB2DPoint(0));
570
571 for(sal_uInt32 a(0); a < nEdgeCount; a++)
572 {
573 const sal_uInt32 nNextIndex((a + 1) % nPointCount);
574 aEdge.setControlPointA(rCandidate.getNextControlPoint(a));
575 aEdge.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex));
576 aEdge.setEndPoint(rCandidate.getB2DPoint(nNextIndex));
577
578 fRetval += aEdge.getLength();
579 aEdge.setStartPoint(aEdge.getEndPoint());
580 }
581 }
582 else
583 {
584 B2DPoint aCurrent(rCandidate.getB2DPoint(0));
585
586 for(sal_uInt32 a(0); a < nEdgeCount; a++)
587 {
588 const sal_uInt32 nNextIndex((a + 1) % nPointCount);
589 const B2DPoint aNext(rCandidate.getB2DPoint(nNextIndex));
590
591 fRetval += B2DVector(aNext - aCurrent).getLength();
592 aCurrent = aNext;
593 }
594 }
595 }
596
597 return fRetval;
598 }
599
600 B2DPoint getPositionAbsolute(const B2DPolygon& rCandidate, double fDistance, double fLength)
601 {
602 B2DPoint aRetval;
603 const sal_uInt32 nPointCount(rCandidate.count());
604
605 if( 1L == nPointCount )
606 {
607 // only one point (i.e. no edge) - simply take that point
608 aRetval = rCandidate.getB2DPoint(0);
609 }
610 else if(nPointCount > 1L)
611 {
612 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1);
613 sal_uInt32 nIndex(0L);
614 bool bIndexDone(false);
615
616 // get length if not given
617 if(fTools::equalZero(fLength))
618 {
619 fLength = getLength(rCandidate);
620 }
621
622 if(fTools::less(fDistance, 0.0))
623 {
624 // handle fDistance < 0.0
625 if(rCandidate.isClosed())
626 {
627 // if fDistance < 0.0 increment with multiple of fLength
628 sal_uInt32 nCount(sal_uInt32(-fDistance / fLength));
629 fDistance += double(nCount + 1L) * fLength;
630 }
631 else
632 {
633 // crop to polygon start
634 fDistance = 0.0;
635 bIndexDone = true;
636 }
637 }
638 else if(fTools::moreOrEqual(fDistance, fLength))
639 {
640 // handle fDistance >= fLength
641 if(rCandidate.isClosed())
642 {
643 // if fDistance >= fLength decrement with multiple of fLength
644 sal_uInt32 nCount(sal_uInt32(fDistance / fLength));
645 fDistance -= (double)(nCount) * fLength;
646 }
647 else
648 {
649 // crop to polygon end
650 fDistance = 0.0;
651 nIndex = nEdgeCount;
652 bIndexDone = true;
653 }
654 }
655
656 // look for correct index. fDistance is now [0.0 .. fLength[
657 double fEdgeLength(getEdgeLength(rCandidate, nIndex));
658
659 while(!bIndexDone)
660 {
661 // edge found must be on the half-open range
662 // [0,fEdgeLength).
663 // Note that in theory, we cannot move beyond
664 // the last polygon point, since fDistance>=fLength
665 // is checked above. Unfortunately, with floating-
666 // point calculations, this case might happen.
667 // Handled by nIndex check below
668 if(nIndex < nEdgeCount && fTools::moreOrEqual(fDistance, fEdgeLength))
669 {
670 // go to next edge
671 fDistance -= fEdgeLength;
672 fEdgeLength = getEdgeLength(rCandidate, ++nIndex);
673 }
674 else
675 {
676 // it's on this edge, stop
677 bIndexDone = true;
678 }
679 }
680
681 // get the point using nIndex
682 aRetval = rCandidate.getB2DPoint(nIndex);
683
684 // if fDistance != 0.0, move that length on the edge. The edge
685 // length is in fEdgeLength.
686 if(!fTools::equalZero(fDistance))
687 {
688 if(fTools::moreOrEqual(fDistance, fEdgeLength))
689 {
690 // end point of choosen edge
691 const sal_uInt32 nNextIndex((nIndex + 1) % nPointCount);
692 aRetval = rCandidate.getB2DPoint(nNextIndex);
693 }
694 else if(fTools::equalZero(fDistance))
695 {
696 // start point of choosen edge
697 aRetval = aRetval;
698 }
699 else
700 {
701 // inside edge
702 const sal_uInt32 nNextIndex((nIndex + 1) % nPointCount);
703 const B2DPoint aNextPoint(rCandidate.getB2DPoint(nNextIndex));
704 bool bDone(false);
705
706 // add calculated average value to the return value
707 if(rCandidate.areControlPointsUsed())
708 {
709 // get as bezier segment
710 const B2DCubicBezier aBezierSegment(
711 aRetval, rCandidate.getNextControlPoint(nIndex),
712 rCandidate.getPrevControlPoint(nNextIndex), aNextPoint);
713
714 if(aBezierSegment.isBezier())
715 {
716 // use B2DCubicBezierHelper to bridge the non-linear gap between
717 // length and bezier distances
718 const B2DCubicBezierHelper aBezierSegmentHelper(aBezierSegment);
719 const double fBezierDistance(aBezierSegmentHelper.distanceToRelative(fDistance));
720
721 aRetval = aBezierSegment.interpolatePoint(fBezierDistance);
722 bDone = true;
723 }
724 }
725
726 if(!bDone)
727 {
728 const double fRelativeInEdge(fDistance / fEdgeLength);
729 aRetval = interpolate(aRetval, aNextPoint, fRelativeInEdge);
730 }
731 }
732 }
733 }
734
735 return aRetval;
736 }
737
738 B2DPoint getPositionRelative(const B2DPolygon& rCandidate, double fDistance, double fLength)
739 {
740 // get length if not given
741 if(fTools::equalZero(fLength))
742 {
743 fLength = getLength(rCandidate);
744 }
745
746 // multiply fDistance with real length to get absolute position and
747 // use getPositionAbsolute
748 return getPositionAbsolute(rCandidate, fDistance * fLength, fLength);
749 }
750
751 B2DPolygon getSnippetAbsolute(const B2DPolygon& rCandidate, double fFrom, double fTo, double fLength)
752 {
753 const sal_uInt32 nPointCount(rCandidate.count());
754
755 if(nPointCount)
756 {
757 // get length if not given
758 if(fTools::equalZero(fLength))
759 {
760 fLength = getLength(rCandidate);
761 }
762
763 // test and correct fFrom
764 if(fTools::less(fFrom, 0.0))
765 {
766 fFrom = 0.0;
767 }
768
769 // test and correct fTo
770 if(fTools::more(fTo, fLength))
771 {
772 fTo = fLength;
773 }
774
775 // test and correct relationship of fFrom, fTo
776 if(fTools::more(fFrom, fTo))
777 {
778 fFrom = fTo = (fFrom + fTo) / 2.0;
779 }
780
781 if(fTools::equalZero(fFrom) && fTools::equal(fTo, fLength))
782 {
783 // no change, result is the whole polygon
784 return rCandidate;
785 }
786 else
787 {
788 B2DPolygon aRetval;
789 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1);
790 double fPositionOfStart(0.0);
791 bool bStartDone(false);
792 bool bEndDone(false);
793
794 for(sal_uInt32 a(0L); !(bStartDone && bEndDone) && a < nEdgeCount; a++)
795 {
796 const double fEdgeLength(getEdgeLength(rCandidate, a));
797
798 if(!bStartDone)
799 {
800 if(fTools::equalZero(fFrom))
801 {
802 aRetval.append(rCandidate.getB2DPoint(a));
803
804 if(rCandidate.areControlPointsUsed())
805 {
806 aRetval.setNextControlPoint(aRetval.count() - 1, rCandidate.getNextControlPoint(a));
807 }
808
809 bStartDone = true;
810 }
811 else if(fTools::moreOrEqual(fFrom, fPositionOfStart) && fTools::less(fFrom, fPositionOfStart + fEdgeLength))
812 {
813 // calculate and add start point
814 if(fTools::equalZero(fEdgeLength))
815 {
816 aRetval.append(rCandidate.getB2DPoint(a));
817
818 if(rCandidate.areControlPointsUsed())
819 {
820 aRetval.setNextControlPoint(aRetval.count() - 1, rCandidate.getNextControlPoint(a));
821 }
822 }
823 else
824 {
825 const sal_uInt32 nNextIndex((a + 1) % nPointCount);
826 const B2DPoint aStart(rCandidate.getB2DPoint(a));
827 const B2DPoint aEnd(rCandidate.getB2DPoint(nNextIndex));
828 bool bDone(false);
829
830 if(rCandidate.areControlPointsUsed())
831 {
832 const B2DCubicBezier aBezierSegment(
833 aStart, rCandidate.getNextControlPoint(a),
834 rCandidate.getPrevControlPoint(nNextIndex), aEnd);
835
836 if(aBezierSegment.isBezier())
837 {
838 // use B2DCubicBezierHelper to bridge the non-linear gap between
839 // length and bezier distances
840 const B2DCubicBezierHelper aBezierSegmentHelper(aBezierSegment);
841 const double fBezierDistance(aBezierSegmentHelper.distanceToRelative(fFrom - fPositionOfStart));
842 B2DCubicBezier aRight;
843
844 aBezierSegment.split(fBezierDistance, 0, &aRight);
845 aRetval.append(aRight.getStartPoint());
846 aRetval.setNextControlPoint(aRetval.count() - 1, aRight.getControlPointA());
847 bDone = true;
848 }
849 }
850
851 if(!bDone)
852 {
853 const double fRelValue((fFrom - fPositionOfStart) / fEdgeLength);
854 aRetval.append(interpolate(aStart, aEnd, fRelValue));
855 }
856 }
857
858 bStartDone = true;
859
860 // if same point, end is done, too.
861 if(fFrom == fTo)
862 {
863 bEndDone = true;
864 }
865 }
866 }
867
868 if(!bEndDone && fTools::moreOrEqual(fTo, fPositionOfStart) && fTools::less(fTo, fPositionOfStart + fEdgeLength))
869 {
870 // calculate and add end point
871 if(fTools::equalZero(fEdgeLength))
872 {
873 const sal_uInt32 nNextIndex((a + 1) % nPointCount);
874 aRetval.append(rCandidate.getB2DPoint(nNextIndex));
875
876 if(rCandidate.areControlPointsUsed())
877 {
878 aRetval.setPrevControlPoint(aRetval.count() - 1, rCandidate.getPrevControlPoint(nNextIndex));
879 }
880 }
881 else
882 {
883 const sal_uInt32 nNextIndex((a + 1) % nPointCount);
884 const B2DPoint aStart(rCandidate.getB2DPoint(a));
885 const B2DPoint aEnd(rCandidate.getB2DPoint(nNextIndex));
886 bool bDone(false);
887
888 if(rCandidate.areControlPointsUsed())
889 {
890 const B2DCubicBezier aBezierSegment(
891 aStart, rCandidate.getNextControlPoint(a),
892 rCandidate.getPrevControlPoint(nNextIndex), aEnd);
893
894 if(aBezierSegment.isBezier())
895 {
896 // use B2DCubicBezierHelper to bridge the non-linear gap between
897 // length and bezier distances
898 const B2DCubicBezierHelper aBezierSegmentHelper(aBezierSegment);
899 const double fBezierDistance(aBezierSegmentHelper.distanceToRelative(fTo - fPositionOfStart));
900 B2DCubicBezier aLeft;
901
902 aBezierSegment.split(fBezierDistance, &aLeft, 0);
903 aRetval.append(aLeft.getEndPoint());
904 aRetval.setPrevControlPoint(aRetval.count() - 1, aLeft.getControlPointB());
905 bDone = true;
906 }
907 }
908
909 if(!bDone)
910 {
911 const double fRelValue((fTo - fPositionOfStart) / fEdgeLength);
912 aRetval.append(interpolate(aStart, aEnd, fRelValue));
913 }
914 }
915
916 bEndDone = true;
917 }
918
919 if(!bEndDone)
920 {
921 if(bStartDone)
922 {
923 // add segments end point
924 const sal_uInt32 nNextIndex((a + 1) % nPointCount);
925 aRetval.append(rCandidate.getB2DPoint(nNextIndex));
926
927 if(rCandidate.areControlPointsUsed())
928 {
929 aRetval.setPrevControlPoint(aRetval.count() - 1, rCandidate.getPrevControlPoint(nNextIndex));
930 aRetval.setNextControlPoint(aRetval.count() - 1, rCandidate.getNextControlPoint(nNextIndex));
931 }
932 }
933
934 // increment fPositionOfStart
935 fPositionOfStart += fEdgeLength;
936 }
937 }
938 return aRetval;
939 }
940 }
941 else
942 {
943 return rCandidate;
944 }
945 }
946
947 CutFlagValue findCut(
948 const B2DPoint& rEdge1Start, const B2DVector& rEdge1Delta,
949 const B2DPoint& rEdge2Start, const B2DVector& rEdge2Delta,
950 CutFlagValue aCutFlags,
951 double* pCut1, double* pCut2)
952 {
953 CutFlagValue aRetval(CUTFLAG_NONE);
954 double fCut1(0.0);
955 double fCut2(0.0);
956 bool bFinished(!((bool)(aCutFlags & CUTFLAG_ALL)));
957
958 // test for same points?
959 if(!bFinished
960 && (aCutFlags & (CUTFLAG_START1|CUTFLAG_END1))
961 && (aCutFlags & (CUTFLAG_START2|CUTFLAG_END2)))
962 {
963 // same startpoint?
964 if(!bFinished && (aCutFlags & (CUTFLAG_START1|CUTFLAG_START2)) == (CUTFLAG_START1|CUTFLAG_START2))
965 {
966 if(rEdge1Start.equal(rEdge2Start))
967 {
968 bFinished = true;
969 aRetval = (CUTFLAG_START1|CUTFLAG_START2);
970 }
971 }
972
973 // same endpoint?
974 if(!bFinished && (aCutFlags & (CUTFLAG_END1|CUTFLAG_END2)) == (CUTFLAG_END1|CUTFLAG_END2))
975 {
976 const B2DPoint aEnd1(rEdge1Start + rEdge1Delta);
977 const B2DPoint aEnd2(rEdge2Start + rEdge2Delta);
978
979 if(aEnd1.equal(aEnd2))
980 {
981 bFinished = true;
982 aRetval = (CUTFLAG_END1|CUTFLAG_END2);
983 fCut1 = fCut2 = 1.0;
984 }
985 }
986
987 // startpoint1 == endpoint2?
988 if(!bFinished && (aCutFlags & (CUTFLAG_START1|CUTFLAG_END2)) == (CUTFLAG_START1|CUTFLAG_END2))
989 {
990 const B2DPoint aEnd2(rEdge2Start + rEdge2Delta);
991
992 if(rEdge1Start.equal(aEnd2))
993 {
994 bFinished = true;
995 aRetval = (CUTFLAG_START1|CUTFLAG_END2);
996 fCut1 = 0.0;
997 fCut2 = 1.0;
998 }
999 }
1000
1001 // startpoint2 == endpoint1?
1002 if(!bFinished&& (aCutFlags & (CUTFLAG_START2|CUTFLAG_END1)) == (CUTFLAG_START2|CUTFLAG_END1))
1003 {
1004 const B2DPoint aEnd1(rEdge1Start + rEdge1Delta);
1005
1006 if(rEdge2Start.equal(aEnd1))
1007 {
1008 bFinished = true;
1009 aRetval = (CUTFLAG_START2|CUTFLAG_END1);
1010 fCut1 = 1.0;
1011 fCut2 = 0.0;
1012 }
1013 }
1014 }
1015
1016 if(!bFinished && (aCutFlags & CUTFLAG_LINE))
1017 {
1018 if(!bFinished && (aCutFlags & CUTFLAG_START1))
1019 {
1020 // start1 on line 2 ?
1021 if(isPointOnEdge(rEdge1Start, rEdge2Start, rEdge2Delta, &fCut2))
1022 {
1023 bFinished = true;
1024 aRetval = (CUTFLAG_LINE|CUTFLAG_START1);
1025 }
1026 }
1027
1028 if(!bFinished && (aCutFlags & CUTFLAG_START2))
1029 {
1030 // start2 on line 1 ?
1031 if(isPointOnEdge(rEdge2Start, rEdge1Start, rEdge1Delta, &fCut1))
1032 {
1033 bFinished = true;
1034 aRetval = (CUTFLAG_LINE|CUTFLAG_START2);
1035 }
1036 }
1037
1038 if(!bFinished && (aCutFlags & CUTFLAG_END1))
1039 {
1040 // end1 on line 2 ?
1041 const B2DPoint aEnd1(rEdge1Start + rEdge1Delta);
1042
1043 if(isPointOnEdge(aEnd1, rEdge2Start, rEdge2Delta, &fCut2))
1044 {
1045 bFinished = true;
1046 aRetval = (CUTFLAG_LINE|CUTFLAG_END1);
1047 }
1048 }
1049
1050 if(!bFinished && (aCutFlags & CUTFLAG_END2))
1051 {
1052 // end2 on line 1 ?
1053 const B2DPoint aEnd2(rEdge2Start + rEdge2Delta);
1054
1055 if(isPointOnEdge(aEnd2, rEdge1Start, rEdge1Delta, &fCut1))
1056 {
1057 bFinished = true;
1058 aRetval = (CUTFLAG_LINE|CUTFLAG_END2);
1059 }
1060 }
1061
1062 if(!bFinished)
1063 {
1064 // cut in line1, line2 ?
1065 fCut1 = (rEdge1Delta.getX() * rEdge2Delta.getY()) - (rEdge1Delta.getY() * rEdge2Delta.getX());
1066
1067 if(!fTools::equalZero(fCut1))
1068 {
1069 fCut1 = (rEdge2Delta.getY() * (rEdge2Start.getX() - rEdge1Start.getX())
1070 + rEdge2Delta.getX() * (rEdge1Start.getY() - rEdge2Start.getY())) / fCut1;
1071
1072 const double fZero(0.0);
1073 const double fOne(1.0);
1074
1075 // inside parameter range edge1 AND fCut2 is calcable
1076 if(fTools::more(fCut1, fZero) && fTools::less(fCut1, fOne)
1077 && (!fTools::equalZero(rEdge2Delta.getX()) || !fTools::equalZero(rEdge2Delta.getY())))
1078 {
1079 // take the mopre precise calculation of the two possible
1080 if(fabs(rEdge2Delta.getX()) > fabs(rEdge2Delta.getY()))
1081 {
1082 fCut2 = (rEdge1Start.getX() + fCut1
1083 * rEdge1Delta.getX() - rEdge2Start.getX()) / rEdge2Delta.getX();
1084 }
1085 else
1086 {
1087 fCut2 = (rEdge1Start.getY() + fCut1
1088 * rEdge1Delta.getY() - rEdge2Start.getY()) / rEdge2Delta.getY();
1089 }
1090
1091 // inside parameter range edge2, too
1092 if(fTools::more(fCut2, fZero) && fTools::less(fCut2, fOne))
1093 {
1094 bFinished = true;
1095 aRetval = CUTFLAG_LINE;
1096 }
1097 }
1098 }
1099 }
1100 }
1101
1102 // copy values if wanted
1103 if(pCut1)
1104 {
1105 *pCut1 = fCut1;
1106 }
1107
1108 if(pCut2)
1109 {
1110 *pCut2 = fCut2;
1111 }
1112
1113 return aRetval;
1114 }
1115
1116 bool isPointOnEdge(
1117 const B2DPoint& rPoint,
1118 const B2DPoint& rEdgeStart,
1119 const B2DVector& rEdgeDelta,
1120 double* pCut)
1121 {
1122 bool bDeltaXIsZero(fTools::equalZero(rEdgeDelta.getX()));
1123 bool bDeltaYIsZero(fTools::equalZero(rEdgeDelta.getY()));
1124 const double fZero(0.0);
1125 const double fOne(1.0);
1126
1127 if(bDeltaXIsZero && bDeltaYIsZero)
1128 {
1129 // no line, just a point
1130 return false;
1131 }
1132 else if(bDeltaXIsZero)
1133 {
1134 // vertical line
1135 if(fTools::equal(rPoint.getX(), rEdgeStart.getX()))
1136 {
1137 double fValue = (rPoint.getY() - rEdgeStart.getY()) / rEdgeDelta.getY();
1138
1139 if(fTools::more(fValue, fZero) && fTools::less(fValue, fOne))
1140 {
1141 if(pCut)
1142 {
1143 *pCut = fValue;
1144 }
1145
1146 return true;
1147 }
1148 }
1149 }
1150 else if(bDeltaYIsZero)
1151 {
1152 // horizontal line
1153 if(fTools::equal(rPoint.getY(), rEdgeStart.getY()))
1154 {
1155 double fValue = (rPoint.getX() - rEdgeStart.getX()) / rEdgeDelta.getX();
1156
1157 if(fTools::more(fValue, fZero) && fTools::less(fValue, fOne))
1158 {
1159 if(pCut)
1160 {
1161 *pCut = fValue;
1162 }
1163
1164 return true;
1165 }
1166 }
1167 }
1168 else
1169 {
1170 // any angle line
1171 double fTOne = (rPoint.getX() - rEdgeStart.getX()) / rEdgeDelta.getX();
1172 double fTTwo = (rPoint.getY() - rEdgeStart.getY()) / rEdgeDelta.getY();
1173
1174 if(fTools::equal(fTOne, fTTwo))
1175 {
1176 // same parameter representation, point is on line. Take
1177 // middle value for better results
1178 double fValue = (fTOne + fTTwo) / 2.0;
1179
1180 if(fTools::more(fValue, fZero) && fTools::less(fValue, fOne))
1181 {
1182 // point is inside line bounds, too
1183 if(pCut)
1184 {
1185 *pCut = fValue;
1186 }
1187
1188 return true;
1189 }
1190 }
1191 }
1192
1193 return false;
1194 }
1195
1196 void applyLineDashing(const B2DPolygon& rCandidate, const ::std::vector<double>& rDotDashArray, B2DPolyPolygon* pLineTarget, B2DPolyPolygon* pGapTarget, double fDotDashLength)
1197 {
1198 const sal_uInt32 nPointCount(rCandidate.count());
1199 const sal_uInt32 nDotDashCount(rDotDashArray.size());
1200
1201 if(fTools::lessOrEqual(fDotDashLength, 0.0))
1202 {
1203 fDotDashLength = ::std::accumulate(rDotDashArray.begin(), rDotDashArray.end(), 0.0);
1204 }
1205
1206 if(fTools::more(fDotDashLength, 0.0) && (pLineTarget || pGapTarget) && nPointCount)
1207 {
1208 // clear targets
1209 if(pLineTarget)
1210 {
1211 pLineTarget->clear();
1212 }
1213
1214 if(pGapTarget)
1215 {
1216 pGapTarget->clear();
1217 }
1218
1219 // prepare current edge's start
1220 B2DCubicBezier aCurrentEdge;
1221 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1);
1222 aCurrentEdge.setStartPoint(rCandidate.getB2DPoint(0));
1223
1224 // prepare DotDashArray iteration and the line/gap switching bool
1225 sal_uInt32 nDotDashIndex(0);
1226 bool bIsLine(true);
1227 double fDotDashMovingLength(rDotDashArray[0]);
1228 B2DPolygon aSnippet;
1229
1230 // iterate over all edges
1231 for(sal_uInt32 a(0); a < nEdgeCount; a++)
1232 {
1233 // update current edge (fill in C1, C2 and end point)
1234 double fLastDotDashMovingLength(0.0);
1235 const sal_uInt32 nNextIndex((a + 1) % nPointCount);
1236 aCurrentEdge.setControlPointA(rCandidate.getNextControlPoint(a));
1237 aCurrentEdge.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex));
1238 aCurrentEdge.setEndPoint(rCandidate.getB2DPoint(nNextIndex));
1239
1240 // check if we have a trivial bezier segment -> possible fallback to edge
1241 aCurrentEdge.testAndSolveTrivialBezier();
1242
1243 if(aCurrentEdge.isBezier())
1244 {
1245 // bezier segment
1246 const B2DCubicBezierHelper aCubicBezierHelper(aCurrentEdge);
1247 const double fEdgeLength(aCubicBezierHelper.getLength());
1248
1249 if(!fTools::equalZero(fEdgeLength))
1250 {
1251 while(fTools::less(fDotDashMovingLength, fEdgeLength))
1252 {
1253 // new split is inside edge, create and append snippet [fLastDotDashMovingLength, fDotDashMovingLength]
1254 const bool bHandleLine(bIsLine && pLineTarget);
1255 const bool bHandleGap(!bIsLine && pGapTarget);
1256
1257 if(bHandleLine || bHandleGap)
1258 {
1259 const double fBezierSplitStart(aCubicBezierHelper.distanceToRelative(fLastDotDashMovingLength));
1260 const double fBezierSplitEnd(aCubicBezierHelper.distanceToRelative(fDotDashMovingLength));
1261 B2DCubicBezier aBezierSnippet(aCurrentEdge.snippet(fBezierSplitStart, fBezierSplitEnd));
1262
1263 if(!aSnippet.count())
1264 {
1265 aSnippet.append(aBezierSnippet.getStartPoint());
1266 }
1267
1268 aSnippet.appendBezierSegment(aBezierSnippet.getControlPointA(), aBezierSnippet.getControlPointB(), aBezierSnippet.getEndPoint());
1269
1270 if(bHandleLine)
1271 {
1272 pLineTarget->append(aSnippet);
1273 }
1274 else
1275 {
1276 pGapTarget->append(aSnippet);
1277 }
1278
1279 aSnippet.clear();
1280 }
1281
1282 // prepare next DotDashArray step and flip line/gap flag
1283 fLastDotDashMovingLength = fDotDashMovingLength;
1284 fDotDashMovingLength += rDotDashArray[(++nDotDashIndex) % nDotDashCount];
1285 bIsLine = !bIsLine;
1286 }
1287
1288 // append closing snippet [fLastDotDashMovingLength, fEdgeLength]
1289 const bool bHandleLine(bIsLine && pLineTarget);
1290 const bool bHandleGap(!bIsLine && pGapTarget);
1291
1292 if(bHandleLine || bHandleGap)
1293 {
1294 B2DCubicBezier aRight;
1295 const double fBezierSplit(aCubicBezierHelper.distanceToRelative(fLastDotDashMovingLength));
1296
1297 aCurrentEdge.split(fBezierSplit, 0, &aRight);
1298
1299 if(!aSnippet.count())
1300 {
1301 aSnippet.append(aRight.getStartPoint());
1302 }
1303
1304 aSnippet.appendBezierSegment(aRight.getControlPointA(), aRight.getControlPointB(), aRight.getEndPoint());
1305 }
1306
1307 // prepare move to next edge
1308 fDotDashMovingLength -= fEdgeLength;
1309 }
1310 }
1311 else
1312 {
1313 // simple edge
1314 const double fEdgeLength(aCurrentEdge.getEdgeLength());
1315
1316 if(!fTools::equalZero(fEdgeLength))
1317 {
1318 while(fTools::less(fDotDashMovingLength, fEdgeLength))
1319 {
1320 // new split is inside edge, create and append snippet [fLastDotDashMovingLength, fDotDashMovingLength]
1321 const bool bHandleLine(bIsLine && pLineTarget);
1322 const bool bHandleGap(!bIsLine && pGapTarget);
1323
1324 if(bHandleLine || bHandleGap)
1325 {
1326 if(!aSnippet.count())
1327 {
1328 aSnippet.append(interpolate(aCurrentEdge.getStartPoint(), aCurrentEdge.getEndPoint(), fLastDotDashMovingLength / fEdgeLength));
1329 }
1330
1331 aSnippet.append(interpolate(aCurrentEdge.getStartPoint(), aCurrentEdge.getEndPoint(), fDotDashMovingLength / fEdgeLength));
1332
1333 if(bHandleLine)
1334 {
1335 pLineTarget->append(aSnippet);
1336 }
1337 else
1338 {
1339 pGapTarget->append(aSnippet);
1340 }
1341
1342 aSnippet.clear();
1343 }
1344
1345 // prepare next DotDashArray step and flip line/gap flag
1346 fLastDotDashMovingLength = fDotDashMovingLength;
1347 fDotDashMovingLength += rDotDashArray[(++nDotDashIndex) % nDotDashCount];
1348 bIsLine = !bIsLine;
1349 }
1350
1351 // append snippet [fLastDotDashMovingLength, fEdgeLength]
1352 const bool bHandleLine(bIsLine && pLineTarget);
1353 const bool bHandleGap(!bIsLine && pGapTarget);
1354
1355 if(bHandleLine || bHandleGap)
1356 {
1357 if(!aSnippet.count())
1358 {
1359 aSnippet.append(interpolate(aCurrentEdge.getStartPoint(), aCurrentEdge.getEndPoint(), fLastDotDashMovingLength / fEdgeLength));
1360 }
1361
1362 aSnippet.append(aCurrentEdge.getEndPoint());
1363 }
1364
1365 // prepare move to next edge
1366 fDotDashMovingLength -= fEdgeLength;
1367 }
1368 }
1369
1370 // prepare next edge step (end point gets new start point)
1371 aCurrentEdge.setStartPoint(aCurrentEdge.getEndPoint());
1372 }
1373
1374 // append last intermediate results (if exists)
1375 if(aSnippet.count())
1376 {
1377 if(bIsLine && pLineTarget)
1378 {
1379 pLineTarget->append(aSnippet);
1380 }
1381 else if(!bIsLine && pGapTarget)
1382 {
1383 pGapTarget->append(aSnippet);
1384 }
1385 }
1386
1387 // check if start and end polygon may be merged
1388 if(pLineTarget)
1389 {
1390 const sal_uInt32 nCount(pLineTarget->count());
1391
1392 if(nCount > 1)
1393 {
1394 // these polygons were created above, there exists none with less than two points,
1395 // thus dircet point access below is allowed
1396 const B2DPolygon aFirst(pLineTarget->getB2DPolygon(0));
1397 B2DPolygon aLast(pLineTarget->getB2DPolygon(nCount - 1));
1398
1399 if(aFirst.getB2DPoint(0).equal(aLast.getB2DPoint(aLast.count() - 1)))
1400 {
1401 // start of first and end of last are the same -> merge them
1402 aLast.append(aFirst);
1403 aLast.removeDoublePoints();
1404 pLineTarget->setB2DPolygon(0, aLast);
1405 pLineTarget->remove(nCount - 1);
1406 }
1407 }
1408 }
1409
1410 if(pGapTarget)
1411 {
1412 const sal_uInt32 nCount(pGapTarget->count());
1413
1414 if(nCount > 1)
1415 {
1416 // these polygons were created above, there exists none with less than two points,
1417 // thus dircet point access below is allowed
1418 const B2DPolygon aFirst(pGapTarget->getB2DPolygon(0));
1419 B2DPolygon aLast(pGapTarget->getB2DPolygon(nCount - 1));
1420
1421 if(aFirst.getB2DPoint(0).equal(aLast.getB2DPoint(aLast.count() - 1)))
1422 {
1423 // start of first and end of last are the same -> merge them
1424 aLast.append(aFirst);
1425 aLast.removeDoublePoints();
1426 pGapTarget->setB2DPolygon(0, aLast);
1427 pGapTarget->remove(nCount - 1);
1428 }
1429 }
1430 }
1431 }
1432 else
1433 {
1434 // parameters make no sense, just add source to targets
1435 if(pLineTarget)
1436 {
1437 pLineTarget->append(rCandidate);
1438 }
1439
1440 if(pGapTarget)
1441 {
1442 pGapTarget->append(rCandidate);
1443 }
1444 }
1445 }
1446
1447 // test if point is inside epsilon-range around an edge defined
1448 // by the two given points. Can be used for HitTesting. The epsilon-range
1449 // is defined to be the rectangle centered to the given edge, using height
1450 // 2 x fDistance, and the circle around both points with radius fDistance.
1451 bool isInEpsilonRange(const B2DPoint& rEdgeStart, const B2DPoint& rEdgeEnd, const B2DPoint& rTestPosition, double fDistance)
1452 {
1453 // build edge vector
1454 const B2DVector aEdge(rEdgeEnd - rEdgeStart);
1455 bool bDoDistanceTestStart(false);
1456 bool bDoDistanceTestEnd(false);
1457
1458 if(aEdge.equalZero())
1459 {
1460 // no edge, just a point. Do one of the distance tests.
1461 bDoDistanceTestStart = true;
1462 }
1463 else
1464 {
1465 // edge has a length. Create perpendicular vector.
1466 const B2DVector aPerpend(getPerpendicular(aEdge));
1467 double fCut(
1468 (aPerpend.getY() * (rTestPosition.getX() - rEdgeStart.getX())
1469 + aPerpend.getX() * (rEdgeStart.getY() - rTestPosition.getY())) /
1470 (aEdge.getX() * aEdge.getX() + aEdge.getY() * aEdge.getY()));
1471 const double fZero(0.0);
1472 const double fOne(1.0);
1473
1474 if(fTools::less(fCut, fZero))
1475 {
1476 // left of rEdgeStart
1477 bDoDistanceTestStart = true;
1478 }
1479 else if(fTools::more(fCut, fOne))
1480 {
1481 // right of rEdgeEnd
1482 bDoDistanceTestEnd = true;
1483 }
1484 else
1485 {
1486 // inside line [0.0 .. 1.0]
1487 const B2DPoint aCutPoint(interpolate(rEdgeStart, rEdgeEnd, fCut));
1488 const B2DVector aDelta(rTestPosition - aCutPoint);
1489 const double fDistanceSquare(aDelta.scalar(aDelta));
1490
1491 if(fDistanceSquare <= fDistance * fDistance)
1492 {
1493 return true;
1494 }
1495 else
1496 {
1497 return false;
1498 }
1499 }
1500 }
1501
1502 if(bDoDistanceTestStart)
1503 {
1504 const B2DVector aDelta(rTestPosition - rEdgeStart);
1505 const double fDistanceSquare(aDelta.scalar(aDelta));
1506
1507 if(fDistanceSquare <= fDistance * fDistance)
1508 {
1509 return true;
1510 }
1511 }
1512 else if(bDoDistanceTestEnd)
1513 {
1514 const B2DVector aDelta(rTestPosition - rEdgeEnd);
1515 const double fDistanceSquare(aDelta.scalar(aDelta));
1516
1517 if(fDistanceSquare <= fDistance * fDistance)
1518 {
1519 return true;
1520 }
1521 }
1522
1523 return false;
1524 }
1525
1526 // test if point is inside epsilon-range around the given Polygon. Can be used
1527 // for HitTesting. The epsilon-range is defined to be the tube around the polygon
1528 // with distance fDistance and rounded edges (start and end point).
1529 bool isInEpsilonRange(const B2DPolygon& rCandidate, const B2DPoint& rTestPosition, double fDistance)
1530 {
1531 // force to non-bezier polygon
1532 const B2DPolygon aCandidate(rCandidate.getDefaultAdaptiveSubdivision());
1533 const sal_uInt32 nPointCount(aCandidate.count());
1534
1535 if(nPointCount)
1536 {
1537 const sal_uInt32 nEdgeCount(aCandidate.isClosed() ? nPointCount : nPointCount - 1L);
1538 B2DPoint aCurrent(aCandidate.getB2DPoint(0));
1539
1540 if(nEdgeCount)
1541 {
1542 // edges
1543 for(sal_uInt32 a(0); a < nEdgeCount; a++)
1544 {
1545 const sal_uInt32 nNextIndex((a + 1) % nPointCount);
1546 const B2DPoint aNext(aCandidate.getB2DPoint(nNextIndex));
1547
1548 if(isInEpsilonRange(aCurrent, aNext, rTestPosition, fDistance))
1549 {
1550 return true;
1551 }
1552
1553 // prepare next step
1554 aCurrent = aNext;
1555 }
1556 }
1557 else
1558 {
1559 // no edges, but points -> not closed. Check single point. Just
1560 // use isInEpsilonRange with twice the same point, it handles those well
1561 if(isInEpsilonRange(aCurrent, aCurrent, rTestPosition, fDistance))
1562 {
1563 return true;
1564 }
1565 }
1566 }
1567
1568 return false;
1569 }
1570
1571 B2DPolygon createPolygonFromRect( const B2DRectangle& rRect, double fRadiusX, double fRadiusY )
1572 {
1573 const double fZero(0.0);
1574 const double fOne(1.0);
1575
1576 // crop to useful values
1577 if(fTools::less(fRadiusX, fZero))
1578 {
1579 fRadiusX = fZero;
1580 }
1581 else if(fTools::more(fRadiusX, fOne))
1582 {
1583 fRadiusX = fOne;
1584 }
1585
1586 if(fTools::less(fRadiusY, fZero))
1587 {
1588 fRadiusY = fZero;
1589 }
1590 else if(fTools::more(fRadiusY, fOne))
1591 {
1592 fRadiusY = fOne;
1593 }
1594
1595 if(fZero == fRadiusX || fZero == fRadiusY)
1596 {
1597 B2DPolygon aRetval;
1598
1599 // at least in one direction no radius, use rectangle.
1600 // Do not use createPolygonFromRect() here since original
1601 // creator (historical reasons) still creates a start point at the
1602 // bottom center, so do the same here to get the same line patterns.
1603 // Due to this the order of points is different, too.
1604 const B2DPoint aBottomCenter(rRect.getCenter().getX(), rRect.getMaxY());
1605 aRetval.append(aBottomCenter);
1606
1607 aRetval.append( B2DPoint( rRect.getMinX(), rRect.getMaxY() ) );
1608 aRetval.append( B2DPoint( rRect.getMinX(), rRect.getMinY() ) );
1609 aRetval.append( B2DPoint( rRect.getMaxX(), rRect.getMinY() ) );
1610 aRetval.append( B2DPoint( rRect.getMaxX(), rRect.getMaxY() ) );
1611
1612 // close
1613 aRetval.setClosed( true );
1614
1615 return aRetval;
1616 }
1617 else if(fOne == fRadiusX && fOne == fRadiusY)
1618 {
1619 // in both directions full radius, use ellipse
1620 const B2DPoint aCenter(rRect.getCenter());
1621 const double fRectRadiusX(rRect.getWidth() / 2.0);
1622 const double fRectRadiusY(rRect.getHeight() / 2.0);
1623
1624 return createPolygonFromEllipse( aCenter, fRectRadiusX, fRectRadiusY );
1625 }
1626 else
1627 {
1628 B2DPolygon aRetval;
1629 const double fBowX((rRect.getWidth() / 2.0) * fRadiusX);
1630 const double fBowY((rRect.getHeight() / 2.0) * fRadiusY);
1631 const double fKappa((M_SQRT2 - 1.0) * 4.0 / 3.0);
1632
1633 // create start point at bottom center
1634 if(fOne != fRadiusX)
1635 {
1636 const B2DPoint aBottomCenter(rRect.getCenter().getX(), rRect.getMaxY());
1637 aRetval.append(aBottomCenter);
1638 }
1639
1640 // create first bow
1641 {
1642 const B2DPoint aBottomRight(rRect.getMaxX(), rRect.getMaxY());
1643 const B2DPoint aStart(aBottomRight + B2DPoint(-fBowX, 0.0));
1644 const B2DPoint aStop(aBottomRight + B2DPoint(0.0, -fBowY));
1645 aRetval.append(aStart);
1646 aRetval.appendBezierSegment(interpolate(aStart, aBottomRight, fKappa), interpolate(aStop, aBottomRight, fKappa), aStop);
1647 }
1648
1649 // create second bow
1650 {
1651 const B2DPoint aTopRight(rRect.getMaxX(), rRect.getMinY());
1652 const B2DPoint aStart(aTopRight + B2DPoint(0.0, fBowY));
1653 const B2DPoint aStop(aTopRight + B2DPoint(-fBowX, 0.0));
1654 aRetval.append(aStart);
1655 aRetval.appendBezierSegment(interpolate(aStart, aTopRight, fKappa), interpolate(aStop, aTopRight, fKappa), aStop);
1656 }
1657
1658 // create third bow
1659 {
1660 const B2DPoint aTopLeft(rRect.getMinX(), rRect.getMinY());
1661 const B2DPoint aStart(aTopLeft + B2DPoint(fBowX, 0.0));
1662 const B2DPoint aStop(aTopLeft + B2DPoint(0.0, fBowY));
1663 aRetval.append(aStart);
1664 aRetval.appendBezierSegment(interpolate(aStart, aTopLeft, fKappa), interpolate(aStop, aTopLeft, fKappa), aStop);
1665 }
1666
1667 // create forth bow
1668 {
1669 const B2DPoint aBottomLeft(rRect.getMinX(), rRect.getMaxY());
1670 const B2DPoint aStart(aBottomLeft + B2DPoint(0.0, -fBowY));
1671 const B2DPoint aStop(aBottomLeft + B2DPoint(fBowX, 0.0));
1672 aRetval.append(aStart);
1673 aRetval.appendBezierSegment(interpolate(aStart, aBottomLeft, fKappa), interpolate(aStop, aBottomLeft, fKappa), aStop);
1674 }
1675
1676 // close
1677 aRetval.setClosed( true );
1678
1679 // remove double created points if there are extreme radii envolved
1680 if(fOne == fRadiusX || fOne == fRadiusY)
1681 {
1682 aRetval.removeDoublePoints();
1683 }
1684
1685 return aRetval;
1686 }
1687 }
1688
1689 B2DPolygon createPolygonFromRect( const B2DRectangle& rRect )
1690 {
1691 B2DPolygon aRetval;
1692
1693 aRetval.append( B2DPoint( rRect.getMinX(), rRect.getMinY() ) );
1694 aRetval.append( B2DPoint( rRect.getMaxX(), rRect.getMinY() ) );
1695 aRetval.append( B2DPoint( rRect.getMaxX(), rRect.getMaxY() ) );
1696 aRetval.append( B2DPoint( rRect.getMinX(), rRect.getMaxY() ) );
1697
1698 // close
1699 aRetval.setClosed( true );
1700
1701 return aRetval;
1702 }
1703
1704 namespace
1705 {
1706 struct theUnitPolygon :
1707 public rtl::StaticWithInit<B2DPolygon, theUnitPolygon>
1708 {
1709 B2DPolygon operator () ()
1710 {
1711 B2DPolygon aRetval;
1712
1713 aRetval.append( B2DPoint( 0.0, 0.0 ) );
1714 aRetval.append( B2DPoint( 1.0, 0.0 ) );
1715 aRetval.append( B2DPoint( 1.0, 1.0 ) );
1716 aRetval.append( B2DPoint( 0.0, 1.0 ) );
1717
1718 // close
1719 aRetval.setClosed( true );
1720
1721 return aRetval;
1722 }
1723 };
1724 }
1725
1726 B2DPolygon createUnitPolygon()
1727 {
1728 return theUnitPolygon::get();
1729 }
1730
1731 B2DPolygon createPolygonFromCircle( const B2DPoint& rCenter, double fRadius )
1732 {
1733 return createPolygonFromEllipse( rCenter, fRadius, fRadius );
1734 }
1735
1736 B2DPolygon impCreateUnitCircle(sal_uInt32 nStartQuadrant)
1737 {
1738 B2DPolygon aUnitCircle;
1739 const double fKappa((M_SQRT2 - 1.0) * 4.0 / 3.0);
1740 const double fScaledKappa(fKappa * (1.0 / STEPSPERQUARTER));
1741 const B2DHomMatrix aRotateMatrix(createRotateB2DHomMatrix(F_PI2 / STEPSPERQUARTER));
1742
1743 B2DPoint aPoint(1.0, 0.0);
1744 B2DPoint aForward(1.0, fScaledKappa);
1745 B2DPoint aBackward(1.0, -fScaledKappa);
1746
1747 if(0 != nStartQuadrant)
1748 {
1749 const B2DHomMatrix aQuadrantMatrix(createRotateB2DHomMatrix(F_PI2 * (nStartQuadrant % 4)));
1750 aPoint *= aQuadrantMatrix;
1751 aBackward *= aQuadrantMatrix;
1752 aForward *= aQuadrantMatrix;
1753 }
1754
1755 aUnitCircle.append(aPoint);
1756
1757 for(sal_uInt32 a(0); a < STEPSPERQUARTER * 4; a++)
1758 {
1759 aPoint *= aRotateMatrix;
1760 aBackward *= aRotateMatrix;
1761 aUnitCircle.appendBezierSegment(aForward, aBackward, aPoint);
1762 aForward *= aRotateMatrix;
1763 }
1764
1765 aUnitCircle.setClosed(true);
1766 aUnitCircle.removeDoublePoints();
1767
1768 return aUnitCircle;
1769 }
1770
1771 namespace
1772 {
1773 struct theUnitHalfCircle :
1774 public rtl::StaticWithInit<B2DPolygon, theUnitHalfCircle>
1775 {
1776 B2DPolygon operator()()
1777 {
1778 B2DPolygon aUnitHalfCircle;
1779 const double fKappa((M_SQRT2 - 1.0) * 4.0 / 3.0);
1780 const double fScaledKappa(fKappa * (1.0 / STEPSPERQUARTER));
1781 const B2DHomMatrix aRotateMatrix(createRotateB2DHomMatrix(F_PI2 / STEPSPERQUARTER));
1782 B2DPoint aPoint(1.0, 0.0);
1783 B2DPoint aForward(1.0, fScaledKappa);
1784 B2DPoint aBackward(1.0, -fScaledKappa);
1785
1786 aUnitHalfCircle.append(aPoint);
1787
1788 for(sal_uInt32 a(0); a < STEPSPERQUARTER * 2; a++)
1789 {
1790 aPoint *= aRotateMatrix;
1791 aBackward *= aRotateMatrix;
1792 aUnitHalfCircle.appendBezierSegment(aForward, aBackward, aPoint);
1793 aForward *= aRotateMatrix;
1794 }
1795 return aUnitHalfCircle;
1796 }
1797 };
1798 }
1799
1800 B2DPolygon createHalfUnitCircle()
1801 {
1802 return theUnitHalfCircle::get();
1803 }
1804
1805 namespace
1806 {
1807 struct theUnitCircleStartQuadrantOne :
1808 public rtl::StaticWithInit<B2DPolygon, theUnitCircleStartQuadrantOne>
1809 {
1810 B2DPolygon operator()() { return impCreateUnitCircle(1); }
1811 };
1812
1813 struct theUnitCircleStartQuadrantTwo :
1814 public rtl::StaticWithInit<B2DPolygon, theUnitCircleStartQuadrantTwo>
1815 {
1816 B2DPolygon operator()() { return impCreateUnitCircle(2); }
1817 };
1818
1819 struct theUnitCircleStartQuadrantThree :
1820 public rtl::StaticWithInit<B2DPolygon, theUnitCircleStartQuadrantThree>
1821 {
1822 B2DPolygon operator()() { return impCreateUnitCircle(3); }
1823 };
1824
1825 struct theUnitCircleStartQuadrantZero :
1826 public rtl::StaticWithInit<B2DPolygon, theUnitCircleStartQuadrantZero>
1827 {
1828 B2DPolygon operator()() { return impCreateUnitCircle(0); }
1829 };
1830 }
1831
1832 B2DPolygon createPolygonFromUnitCircle(sal_uInt32 nStartQuadrant)
1833 {
1834 switch(nStartQuadrant % 4)
1835 {
1836 case 1 :
1837 return theUnitCircleStartQuadrantOne::get();
1838
1839 case 2 :
1840 return theUnitCircleStartQuadrantTwo::get();
1841
1842 case 3 :
1843 return theUnitCircleStartQuadrantThree::get();
1844
1845 default : // case 0 :
1846 return theUnitCircleStartQuadrantZero::get();
1847 }
1848 }
1849
1850 B2DPolygon createPolygonFromEllipse( const B2DPoint& rCenter, double fRadiusX, double fRadiusY )
1851 {
1852 B2DPolygon aRetval(createPolygonFromUnitCircle());
1853 const B2DHomMatrix aMatrix(createScaleTranslateB2DHomMatrix(fRadiusX, fRadiusY, rCenter.getX(), rCenter.getY()));
1854
1855 aRetval.transform(aMatrix);
1856
1857 return aRetval;
1858 }
1859
1860 B2DPolygon createPolygonFromUnitEllipseSegment( double fStart, double fEnd )
1861 {
1862 B2DPolygon aRetval;
1863
1864 // truncate fStart, fEnd to a range of [0.0 .. F_2PI[ where F_2PI
1865 // falls back to 0.0 to ensure a unique definition
1866 if(fTools::less(fStart, 0.0))
1867 {
1868 fStart = 0.0;
1869 }
1870
1871 if(fTools::moreOrEqual(fStart, F_2PI))
1872 {
1873 fStart = 0.0;
1874 }
1875
1876 if(fTools::less(fEnd, 0.0))
1877 {
1878 fEnd = 0.0;
1879 }
1880
1881 if(fTools::moreOrEqual(fEnd, F_2PI))
1882 {
1883 fEnd = 0.0;
1884 }
1885
1886 if(fTools::equal(fStart, fEnd))
1887 {
1888 // same start and end angle, add single point
1889 aRetval.append(B2DPoint(cos(fStart), sin(fStart)));
1890 }
1891 else
1892 {
1893 const sal_uInt32 nSegments(STEPSPERQUARTER * 4);
1894 const double fAnglePerSegment(F_PI2 / STEPSPERQUARTER);
1895 const sal_uInt32 nStartSegment(sal_uInt32(fStart / fAnglePerSegment) % nSegments);
1896 const sal_uInt32 nEndSegment(sal_uInt32(fEnd / fAnglePerSegment) % nSegments);
1897 const double fKappa((M_SQRT2 - 1.0) * 4.0 / 3.0);
1898 const double fScaledKappa(fKappa * (1.0 / STEPSPERQUARTER));
1899
1900 B2DPoint aSegStart(cos(fStart), sin(fStart));
1901 aRetval.append(aSegStart);
1902
1903 if(nStartSegment == nEndSegment && fTools::more(fEnd, fStart))
1904 {
1905 // start and end in one sector and in the right order, create in one segment
1906 const B2DPoint aSegEnd(cos(fEnd), sin(fEnd));
1907 const double fFactor(fScaledKappa * ((fEnd - fStart) / fAnglePerSegment));
1908
1909 aRetval.appendBezierSegment(
1910 aSegStart + (B2DPoint(-aSegStart.getY(), aSegStart.getX()) * fFactor),
1911 aSegEnd - (B2DPoint(-aSegEnd.getY(), aSegEnd.getX()) * fFactor),
1912 aSegEnd);
1913 }
1914 else
1915 {
1916 double fSegEndRad((nStartSegment + 1) * fAnglePerSegment);
1917 double fFactor(fScaledKappa * ((fSegEndRad - fStart) / fAnglePerSegment));
1918 B2DPoint aSegEnd(cos(fSegEndRad), sin(fSegEndRad));
1919
1920 aRetval.appendBezierSegment(
1921 aSegStart + (B2DPoint(-aSegStart.getY(), aSegStart.getX()) * fFactor),
1922 aSegEnd - (B2DPoint(-aSegEnd.getY(), aSegEnd.getX()) * fFactor),
1923 aSegEnd);
1924
1925 sal_uInt32 nSegment((nStartSegment + 1) % nSegments);
1926 aSegStart = aSegEnd;
1927
1928 while(nSegment != nEndSegment)
1929 {
1930 // No end in this sector, add full sector.
1931 fSegEndRad = (nSegment + 1) * fAnglePerSegment;
1932 aSegEnd = B2DPoint(cos(fSegEndRad), sin(fSegEndRad));
1933
1934 aRetval.appendBezierSegment(
1935 aSegStart + (B2DPoint(-aSegStart.getY(), aSegStart.getX()) * fScaledKappa),
1936 aSegEnd - (B2DPoint(-aSegEnd.getY(), aSegEnd.getX()) * fScaledKappa),
1937 aSegEnd);
1938
1939 nSegment = (nSegment + 1) % nSegments;
1940 aSegStart = aSegEnd;
1941 }
1942
1943 // End in this sector
1944 const double fSegStartRad(nSegment * fAnglePerSegment);
1945 fFactor = fScaledKappa * ((fEnd - fSegStartRad) / fAnglePerSegment);
1946 aSegEnd = B2DPoint(cos(fEnd), sin(fEnd));
1947
1948 aRetval.appendBezierSegment(
1949 aSegStart + (B2DPoint(-aSegStart.getY(), aSegStart.getX()) * fFactor),
1950 aSegEnd - (B2DPoint(-aSegEnd.getY(), aSegEnd.getX()) * fFactor),
1951 aSegEnd);
1952 }
1953 }
1954
1955 // remove double points between segments created by segmented creation
1956 aRetval.removeDoublePoints();
1957
1958 return aRetval;
1959 }
1960
1961 B2DPolygon createPolygonFromEllipseSegment( const B2DPoint& rCenter, double fRadiusX, double fRadiusY, double fStart, double fEnd )
1962 {
1963 B2DPolygon aRetval(createPolygonFromUnitEllipseSegment(fStart, fEnd));
1964 const B2DHomMatrix aMatrix(createScaleTranslateB2DHomMatrix(fRadiusX, fRadiusY, rCenter.getX(), rCenter.getY()));
1965
1966 aRetval.transform(aMatrix);
1967
1968 return aRetval;
1969 }
1970
1971 bool hasNeutralPoints(const B2DPolygon& rCandidate)
1972 {
1973 OSL_ENSURE(!rCandidate.areControlPointsUsed(), "hasNeutralPoints: ATM works not for curves (!)");
1974 const sal_uInt32 nPointCount(rCandidate.count());
1975
1976 if(nPointCount > 2L)
1977 {
1978 B2DPoint aPrevPoint(rCandidate.getB2DPoint(nPointCount - 1L));
1979 B2DPoint aCurrPoint(rCandidate.getB2DPoint(0L));
1980
1981 for(sal_uInt32 a(0L); a < nPointCount; a++)
1982 {
1983 const B2DPoint aNextPoint(rCandidate.getB2DPoint((a + 1) % nPointCount));
1984 const B2DVector aPrevVec(aPrevPoint - aCurrPoint);
1985 const B2DVector aNextVec(aNextPoint - aCurrPoint);
1986 const B2VectorOrientation aOrientation(getOrientation(aNextVec, aPrevVec));
1987
1988 if(ORIENTATION_NEUTRAL == aOrientation)
1989 {
1990 // current has neutral orientation
1991 return true;
1992 }
1993 else
1994 {
1995 // prepare next
1996 aPrevPoint = aCurrPoint;
1997 aCurrPoint = aNextPoint;
1998 }
1999 }
2000 }
2001
2002 return false;
2003 }
2004
2005 B2DPolygon removeNeutralPoints(const B2DPolygon& rCandidate)
2006 {
2007 if(hasNeutralPoints(rCandidate))
2008 {
2009 const sal_uInt32 nPointCount(rCandidate.count());
2010 B2DPolygon aRetval;
2011 B2DPoint aPrevPoint(rCandidate.getB2DPoint(nPointCount - 1L));
2012 B2DPoint aCurrPoint(rCandidate.getB2DPoint(0L));
2013
2014 for(sal_uInt32 a(0L); a < nPointCount; a++)
2015 {
2016 const B2DPoint aNextPoint(rCandidate.getB2DPoint((a + 1) % nPointCount));
2017 const B2DVector aPrevVec(aPrevPoint - aCurrPoint);
2018 const B2DVector aNextVec(aNextPoint - aCurrPoint);
2019 const B2VectorOrientation aOrientation(getOrientation(aNextVec, aPrevVec));
2020
2021 if(ORIENTATION_NEUTRAL == aOrientation)
2022 {
2023 // current has neutral orientation, leave it out and prepare next
2024 aCurrPoint = aNextPoint;
2025 }
2026 else
2027 {
2028 // add current point
2029 aRetval.append(aCurrPoint);
2030
2031 // prepare next
2032 aPrevPoint = aCurrPoint;
2033 aCurrPoint = aNextPoint;
2034 }
2035 }
2036
2037 while(aRetval.count() && ORIENTATION_NEUTRAL == getOrientationForIndex(aRetval, 0L))
2038 {
2039 aRetval.remove(0L);
2040 }
2041
2042 // copy closed state
2043 aRetval.setClosed(rCandidate.isClosed());
2044
2045 return aRetval;
2046 }
2047 else
2048 {
2049 return rCandidate;
2050 }
2051 }
2052
2053 bool isConvex(const B2DPolygon& rCandidate)
2054 {
2055 OSL_ENSURE(!rCandidate.areControlPointsUsed(), "isConvex: ATM works not for curves (!)");
2056 const sal_uInt32 nPointCount(rCandidate.count());
2057
2058 if(nPointCount > 2L)
2059 {
2060 const B2DPoint aPrevPoint(rCandidate.getB2DPoint(nPointCount - 1L));
2061 B2DPoint aCurrPoint(rCandidate.getB2DPoint(0L));
2062 B2DVector aCurrVec(aPrevPoint - aCurrPoint);
2063 B2VectorOrientation aOrientation(ORIENTATION_NEUTRAL);
2064
2065 for(sal_uInt32 a(0L); a < nPointCount; a++)
2066 {
2067 const B2DPoint aNextPoint(rCandidate.getB2DPoint((a + 1) % nPointCount));
2068 const B2DVector aNextVec(aNextPoint - aCurrPoint);
2069 const B2VectorOrientation aCurrentOrientation(getOrientation(aNextVec, aCurrVec));
2070
2071 if(ORIENTATION_NEUTRAL == aOrientation)
2072 {
2073 // set start value, maybe neutral again
2074 aOrientation = aCurrentOrientation;
2075 }
2076 else
2077 {
2078 if(ORIENTATION_NEUTRAL != aCurrentOrientation && aCurrentOrientation != aOrientation)
2079 {
2080 // different orientations found, that's it
2081 return false;
2082 }
2083 }
2084
2085 // prepare next
2086 aCurrPoint = aNextPoint;
2087 aCurrVec = -aNextVec;
2088 }
2089 }
2090
2091 return true;
2092 }
2093
2094 B2VectorOrientation getOrientationForIndex(const B2DPolygon& rCandidate, sal_uInt32 nIndex)
2095 {
2096 OSL_ENSURE(nIndex < rCandidate.count(), "getOrientationForIndex: index out of range (!)");
2097 const B2DPoint aPrev(rCandidate.getB2DPoint(getIndexOfPredecessor(nIndex, rCandidate)));
2098 const B2DPoint aCurr(rCandidate.getB2DPoint(nIndex));
2099 const B2DPoint aNext(rCandidate.getB2DPoint(getIndexOfSuccessor(nIndex, rCandidate)));
2100 const B2DVector aBack(aPrev - aCurr);
2101 const B2DVector aForw(aNext - aCurr);
2102
2103 return getOrientation(aForw, aBack);
2104 }
2105
2106 bool isPointOnLine(const B2DPoint& rStart, const B2DPoint& rEnd, const B2DPoint& rCandidate, bool bWithPoints)
2107 {
2108 if(rCandidate.equal(rStart) || rCandidate.equal(rEnd))
2109 {
2110 // candidate is in epsilon around start or end -> inside
2111 return bWithPoints;
2112 }
2113 else if(rStart.equal(rEnd))
2114 {
2115 // start and end are equal, but candidate is outside their epsilon -> outside
2116 return false;
2117 }
2118 else
2119 {
2120 const B2DVector aEdgeVector(rEnd - rStart);
2121 const B2DVector aTestVector(rCandidate - rStart);
2122
2123 if(areParallel(aEdgeVector, aTestVector))
2124 {
2125 const double fZero(0.0);
2126 const double fOne(1.0);
2127 const double fParamTestOnCurr(fabs(aEdgeVector.getX()) > fabs(aEdgeVector.getY())
2128 ? aTestVector.getX() / aEdgeVector.getX()
2129 : aTestVector.getY() / aEdgeVector.getY());
2130
2131 if(fTools::more(fParamTestOnCurr, fZero) && fTools::less(fParamTestOnCurr, fOne))
2132 {
2133 return true;
2134 }
2135 }
2136
2137 return false;
2138 }
2139 }
2140
2141 bool isPointOnPolygon(const B2DPolygon& rCandidate, const B2DPoint& rPoint, bool bWithPoints)
2142 {
2143 const B2DPolygon aCandidate(rCandidate.areControlPointsUsed() ? rCandidate.getDefaultAdaptiveSubdivision() : rCandidate);
2144 const sal_uInt32 nPointCount(aCandidate.count());
2145
2146 if(nPointCount > 1L)
2147 {
2148 const sal_uInt32 nLoopCount(aCandidate.isClosed() ? nPointCount : nPointCount - 1L);
2149 B2DPoint aCurrentPoint(aCandidate.getB2DPoint(0L));
2150
2151 for(sal_uInt32 a(0L); a < nLoopCount; a++)
2152 {
2153 const B2DPoint aNextPoint(aCandidate.getB2DPoint((a + 1L) % nPointCount));
2154
2155 if(isPointOnLine(aCurrentPoint, aNextPoint, rPoint, bWithPoints))
2156 {
2157 return true;
2158 }
2159
2160 aCurrentPoint = aNextPoint;
2161 }
2162 }
2163 else if(nPointCount && bWithPoints)
2164 {
2165 return rPoint.equal(aCandidate.getB2DPoint(0L));
2166 }
2167
2168 return false;
2169 }
2170
2171 bool isPointInTriangle(const B2DPoint& rA, const B2DPoint& rB, const B2DPoint& rC, const B2DPoint& rCandidate, bool bWithBorder)
2172 {
2173 if(arePointsOnSameSideOfLine(rA, rB, rC, rCandidate, bWithBorder))
2174 {
2175 if(arePointsOnSameSideOfLine(rB, rC, rA, rCandidate, bWithBorder))
2176 {
2177 if(arePointsOnSameSideOfLine(rC, rA, rB, rCandidate, bWithBorder))
2178 {
2179 return true;
2180 }
2181 }
2182 }
2183
2184 return false;
2185 }
2186
2187 bool arePointsOnSameSideOfLine(const B2DPoint& rStart, const B2DPoint& rEnd, const B2DPoint& rCandidateA, const B2DPoint& rCandidateB, bool bWithLine)
2188 {
2189 const B2DVector aLineVector(rEnd - rStart);
2190 const B2DVector aVectorToA(rEnd - rCandidateA);
2191 const double fCrossA(aLineVector.cross(aVectorToA));
2192
2193 if(fTools::equalZero(fCrossA))
2194 {
2195 // one point on the line
2196 return bWithLine;
2197 }
2198
2199 const B2DVector aVectorToB(rEnd - rCandidateB);
2200 const double fCrossB(aLineVector.cross(aVectorToB));
2201
2202 if(fTools::equalZero(fCrossB))
2203 {
2204 // one point on the line
2205 return bWithLine;
2206 }
2207
2208 // return true if they both have the same sign
2209 return ((fCrossA > 0.0) == (fCrossB > 0.0));
2210 }
2211
2212 void addTriangleFan(const B2DPolygon& rCandidate, B2DPolygon& rTarget)
2213 {
2214 const sal_uInt32 nCount(rCandidate.count());
2215
2216 if(nCount > 2L)
2217 {
2218 const B2DPoint aStart(rCandidate.getB2DPoint(0L));
2219 B2DPoint aLast(rCandidate.getB2DPoint(1L));
2220
2221 for(sal_uInt32 a(2L); a < nCount; a++)
2222 {
2223 const B2DPoint aCurrent(rCandidate.getB2DPoint(a));
2224 rTarget.append(aStart);
2225 rTarget.append(aLast);
2226 rTarget.append(aCurrent);
2227
2228 // prepare next
2229 aLast = aCurrent;
2230 }
2231 }
2232 }
2233
2234 namespace
2235 {
2236 /// return 0 for input of 0, -1 for negative and 1 for positive input
2237 inline int lcl_sgn( const double n )
2238 {
2239 return n == 0.0 ? 0 : 1 - 2*::rtl::math::isSignBitSet(n);
2240 }
2241 }
2242
2243 bool isRectangle( const B2DPolygon& rPoly )
2244 {
2245 // polygon must be closed to resemble a rect, and contain
2246 // at least four points.
2247 if( !rPoly.isClosed() ||
2248 rPoly.count() < 4 ||
2249 rPoly.areControlPointsUsed() )
2250 {
2251 return false;
2252 }
2253
2254 // number of 90 degree turns the polygon has taken
2255 int nNumTurns(0);
2256
2257 int nVerticalEdgeType=0;
2258 int nHorizontalEdgeType=0;
2259 bool bNullVertex(true);
2260 bool bCWPolygon(false); // when true, polygon is CW
2261 // oriented, when false, CCW
2262 bool bOrientationSet(false); // when false, polygon
2263 // orientation has not yet
2264 // been determined.
2265
2266 // scan all _edges_ (which involves coming back to point 0
2267 // for the last edge - thus the modulo operation below)
2268 const sal_Int32 nCount( rPoly.count() );
2269 for( sal_Int32 i=0; i<nCount; ++i )
2270 {
2271 const B2DPoint& rPoint0( rPoly.getB2DPoint(i % nCount) );
2272 const B2DPoint& rPoint1( rPoly.getB2DPoint((i+1) % nCount) );
2273
2274 // is 0 for zero direction vector, 1 for south edge and -1
2275 // for north edge (standard screen coordinate system)
2276 int nCurrVerticalEdgeType( lcl_sgn( rPoint1.getY() - rPoint0.getY() ) );
2277
2278 // is 0 for zero direction vector, 1 for east edge and -1
2279 // for west edge (standard screen coordinate system)
2280 int nCurrHorizontalEdgeType( lcl_sgn(rPoint1.getX() - rPoint0.getX()) );
2281
2282 if( nCurrVerticalEdgeType && nCurrHorizontalEdgeType )
2283 return false; // oblique edge - for sure no rect
2284
2285 const bool bCurrNullVertex( !nCurrVerticalEdgeType && !nCurrHorizontalEdgeType );
2286
2287 // current vertex is equal to previous - just skip,
2288 // until we have a real edge
2289 if( bCurrNullVertex )
2290 continue;
2291
2292 // if previous edge has two identical points, because
2293 // no previous edge direction was available, simply
2294 // take this first non-null edge as the start
2295 // direction. That's what will happen here, if
2296 // bNullVertex is false
2297 if( !bNullVertex )
2298 {
2299 // 2D cross product - is 1 for CW and -1 for CCW turns
2300 const int nCrossProduct( nHorizontalEdgeType*nCurrVerticalEdgeType -
2301 nVerticalEdgeType*nCurrHorizontalEdgeType );
2302
2303 if( !nCrossProduct )
2304 continue; // no change in orientation -
2305 // collinear edges - just go on
2306
2307 // if polygon orientation is not set, we'll
2308 // determine it now
2309 if( !bOrientationSet )
2310 {
2311 bCWPolygon = nCrossProduct == 1;
2312 bOrientationSet = true;
2313 }
2314 else
2315 {
2316 // if current turn orientation is not equal
2317 // initial orientation, this is not a
2318 // rectangle (as rectangles have consistent
2319 // orientation).
2320 if( (nCrossProduct == 1) != bCWPolygon )
2321 return false;
2322 }
2323
2324 ++nNumTurns;
2325
2326 // More than four 90 degree turns are an
2327 // indication that this must not be a rectangle.
2328 if( nNumTurns > 4 )
2329 return false;
2330 }
2331
2332 // store current state for the next turn
2333 nVerticalEdgeType = nCurrVerticalEdgeType;
2334 nHorizontalEdgeType = nCurrHorizontalEdgeType;
2335 bNullVertex = false; // won't reach this line,
2336 // if bCurrNullVertex is
2337 // true - see above
2338 }
2339
2340 return true;
2341 }
2342
2343 B3DPolygon createB3DPolygonFromB2DPolygon(const B2DPolygon& rCandidate, double fZCoordinate)
2344 {
2345 if(rCandidate.areControlPointsUsed())
2346 {
2347 // call myself recursively with subdivided input
2348 const B2DPolygon aCandidate(adaptiveSubdivideByAngle(rCandidate));
2349 return createB3DPolygonFromB2DPolygon(aCandidate, fZCoordinate);
2350 }
2351 else
2352 {
2353 B3DPolygon aRetval;
2354
2355 for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
2356 {
2357 B2DPoint aPoint(rCandidate.getB2DPoint(a));
2358 aRetval.append(B3DPoint(aPoint.getX(), aPoint.getY(), fZCoordinate));
2359 }
2360
2361 // copy closed state
2362 aRetval.setClosed(rCandidate.isClosed());
2363
2364 return aRetval;
2365 }
2366 }
2367
2368 B2DPolygon createB2DPolygonFromB3DPolygon(const B3DPolygon& rCandidate, const B3DHomMatrix& rMat)
2369 {
2370 B2DPolygon aRetval;
2371 const sal_uInt32 nCount(rCandidate.count());
2372 const bool bIsIdentity(rMat.isIdentity());
2373
2374 for(sal_uInt32 a(0L); a < nCount; a++)
2375 {
2376 B3DPoint aCandidate(rCandidate.getB3DPoint(a));
2377
2378 if(!bIsIdentity)
2379 {
2380 aCandidate *= rMat;
2381 }
2382
2383 aRetval.append(B2DPoint(aCandidate.getX(), aCandidate.getY()));
2384 }
2385
2386 // copy closed state
2387 aRetval.setClosed(rCandidate.isClosed());
2388
2389 return aRetval;
2390 }
2391
2392 double getSmallestDistancePointToEdge(const B2DPoint& rPointA, const B2DPoint& rPointB, const B2DPoint& rTestPoint, double& rCut)
2393 {
2394 if(rPointA.equal(rPointB))
2395 {
2396 rCut = 0.0;
2397 const B2DVector aVector(rTestPoint - rPointA);
2398 return aVector.getLength();
2399 }
2400 else
2401 {
2402 // get the relative cut value on line vector (Vector1) for cut with perpendicular through TestPoint
2403 const B2DVector aVector1(rPointB - rPointA);
2404 const B2DVector aVector2(rTestPoint - rPointA);
2405 const double fDividend((aVector2.getX() * aVector1.getX()) + (aVector2.getY() * aVector1.getY()));
2406 const double fDivisor((aVector1.getX() * aVector1.getX()) + (aVector1.getY() * aVector1.getY()));
2407 const double fCut(fDividend / fDivisor);
2408
2409 if(fCut < 0.0)
2410 {
2411 // not in line range, get distance to PointA
2412 rCut = 0.0;
2413 return aVector2.getLength();
2414 }
2415 else if(fCut > 1.0)
2416 {
2417 // not in line range, get distance to PointB
2418 rCut = 1.0;
2419 const B2DVector aVector(rTestPoint - rPointB);
2420 return aVector.getLength();
2421 }
2422 else
2423 {
2424 // in line range
2425 const B2DPoint aCutPoint(rPointA + fCut * aVector1);
2426 const B2DVector aVector(rTestPoint - aCutPoint);
2427 rCut = fCut;
2428 return aVector.getLength();
2429 }
2430 }
2431 }
2432
2433 double getSmallestDistancePointToPolygon(const B2DPolygon& rCandidate, const B2DPoint& rTestPoint, sal_uInt32& rEdgeIndex, double& rCut)
2434 {
2435 double fRetval(DBL_MAX);
2436 const sal_uInt32 nPointCount(rCandidate.count());
2437
2438 if(nPointCount > 1L)
2439 {
2440 const double fZero(0.0);
2441 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1L);
2442 B2DCubicBezier aBezier;
2443 aBezier.setStartPoint(rCandidate.getB2DPoint(0));
2444
2445 for(sal_uInt32 a(0L); a < nEdgeCount; a++)
2446 {
2447 const sal_uInt32 nNextIndex((a + 1) % nPointCount);
2448 aBezier.setEndPoint(rCandidate.getB2DPoint(nNextIndex));
2449 double fEdgeDist;
2450 double fNewCut(0.0);
2451 bool bEdgeIsCurve(false);
2452
2453 if(rCandidate.areControlPointsUsed())
2454 {
2455 aBezier.setControlPointA(rCandidate.getNextControlPoint(a));
2456 aBezier.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex));
2457 aBezier.testAndSolveTrivialBezier();
2458 bEdgeIsCurve = aBezier.isBezier();
2459 }
2460
2461 if(bEdgeIsCurve)
2462 {
2463 fEdgeDist = aBezier.getSmallestDistancePointToBezierSegment(rTestPoint, fNewCut);
2464 }
2465 else
2466 {
2467 fEdgeDist = getSmallestDistancePointToEdge(aBezier.getStartPoint(), aBezier.getEndPoint(), rTestPoint, fNewCut);
2468 }
2469
2470 if(DBL_MAX == fRetval || fEdgeDist < fRetval)
2471 {
2472 fRetval = fEdgeDist;
2473 rEdgeIndex = a;
2474 rCut = fNewCut;
2475
2476 if(fTools::equal(fRetval, fZero))
2477 {
2478 // already found zero distance, cannot get better. Ensure numerical zero value and end loop.
2479 fRetval = 0.0;
2480 break;
2481 }
2482 }
2483
2484 // prepare next step
2485 aBezier.setStartPoint(aBezier.getEndPoint());
2486 }
2487
2488 if(1.0 == rCut)
2489 {
2490 // correct rEdgeIndex when not last point
2491 if(rCandidate.isClosed())
2492 {
2493 rEdgeIndex = getIndexOfSuccessor(rEdgeIndex, rCandidate);
2494 rCut = 0.0;
2495 }
2496 else
2497 {
2498 if(rEdgeIndex != nEdgeCount - 1L)
2499 {
2500 rEdgeIndex++;
2501 rCut = 0.0;
2502 }
2503 }
2504 }
2505 }
2506
2507 return fRetval;
2508 }
2509
2510 B2DPoint distort(const B2DPoint& rCandidate, const B2DRange& rOriginal, const B2DPoint& rTopLeft, const B2DPoint& rTopRight, const B2DPoint& rBottomLeft, const B2DPoint& rBottomRight)
2511 {
2512 if(fTools::equalZero(rOriginal.getWidth()) || fTools::equalZero(rOriginal.getHeight()))
2513 {
2514 return rCandidate;
2515 }
2516 else
2517 {
2518 const double fRelativeX((rCandidate.getX() - rOriginal.getMinX()) / rOriginal.getWidth());
2519 const double fRelativeY((rCandidate.getY() - rOriginal.getMinY()) / rOriginal.getHeight());
2520 const double fOneMinusRelativeX(1.0 - fRelativeX);
2521 const double fOneMinusRelativeY(1.0 - fRelativeY);
2522 const double fNewX((fOneMinusRelativeY) * ((fOneMinusRelativeX) * rTopLeft.getX() + fRelativeX * rTopRight.getX()) +
2523 fRelativeY * ((fOneMinusRelativeX) * rBottomLeft.getX() + fRelativeX * rBottomRight.getX()));
2524 const double fNewY((fOneMinusRelativeX) * ((fOneMinusRelativeY) * rTopLeft.getY() + fRelativeY * rBottomLeft.getY()) +
2525 fRelativeX * ((fOneMinusRelativeY) * rTopRight.getY() + fRelativeY * rBottomRight.getY()));
2526
2527 return B2DPoint(fNewX, fNewY);
2528 }
2529 }
2530
2531 B2DPolygon distort(const B2DPolygon& rCandidate, const B2DRange& rOriginal, const B2DPoint& rTopLeft, const B2DPoint& rTopRight, const B2DPoint& rBottomLeft, const B2DPoint& rBottomRight)
2532 {
2533 const sal_uInt32 nPointCount(rCandidate.count());
2534
2535 if(nPointCount && 0.0 != rOriginal.getWidth() && 0.0 != rOriginal.getHeight())
2536 {
2537 B2DPolygon aRetval;
2538
2539 for(sal_uInt32 a(0L); a < nPointCount; a++)
2540 {
2541 aRetval.append(distort(rCandidate.getB2DPoint(a), rOriginal, rTopLeft, rTopRight, rBottomLeft, rBottomRight));
2542
2543 if(rCandidate.areControlPointsUsed())
2544 {
2545 if(!rCandidate.getPrevControlPoint(a).equalZero())
2546 {
2547 aRetval.setPrevControlPoint(a, distort(rCandidate.getPrevControlPoint(a), rOriginal, rTopLeft, rTopRight, rBottomLeft, rBottomRight));
2548 }
2549
2550 if(!rCandidate.getNextControlPoint(a).equalZero())
2551 {
2552 aRetval.setNextControlPoint(a, distort(rCandidate.getNextControlPoint(a), rOriginal, rTopLeft, rTopRight, rBottomLeft, rBottomRight));
2553 }
2554 }
2555 }
2556
2557 aRetval.setClosed(rCandidate.isClosed());
2558 return aRetval;
2559 }
2560 else
2561 {
2562 return rCandidate;
2563 }
2564 }
2565
2566 B2DPolygon expandToCurve(const B2DPolygon& rCandidate)
2567 {
2568 B2DPolygon aRetval(rCandidate);
2569
2570 for(sal_uInt32 a(0L); a < rCandidate.count(); a++)
2571 {
2572 expandToCurveInPoint(aRetval, a);
2573 }
2574
2575 return aRetval;
2576 }
2577
2578 bool expandToCurveInPoint(B2DPolygon& rCandidate, sal_uInt32 nIndex)
2579 {
2580 OSL_ENSURE(nIndex < rCandidate.count(), "expandToCurveInPoint: Access to polygon out of range (!)");
2581 bool bRetval(false);
2582 const sal_uInt32 nPointCount(rCandidate.count());
2583
2584 if(nPointCount)
2585 {
2586 // predecessor
2587 if(!rCandidate.isPrevControlPointUsed(nIndex))
2588 {
2589 if(!rCandidate.isClosed() && 0 == nIndex)
2590 {
2591 // do not create previous vector for start point of open polygon
2592 }
2593 else
2594 {
2595 const sal_uInt32 nPrevIndex((nIndex + (nPointCount - 1)) % nPointCount);
2596 rCandidate.setPrevControlPoint(nIndex, interpolate(rCandidate.getB2DPoint(nIndex), rCandidate.getB2DPoint(nPrevIndex), 1.0 / 3.0));
2597 bRetval = true;
2598 }
2599 }
2600
2601 // successor
2602 if(!rCandidate.isNextControlPointUsed(nIndex))
2603 {
2604 if(!rCandidate.isClosed() && nIndex + 1 == nPointCount)
2605 {
2606 // do not create next vector for end point of open polygon
2607 }
2608 else
2609 {
2610 const sal_uInt32 nNextIndex((nIndex + 1) % nPointCount);
2611 rCandidate.setNextControlPoint(nIndex, interpolate(rCandidate.getB2DPoint(nIndex), rCandidate.getB2DPoint(nNextIndex), 1.0 / 3.0));
2612 bRetval = true;
2613 }
2614 }
2615 }
2616
2617 return bRetval;
2618 }
2619
2620 bool setContinuityInPoint(B2DPolygon& rCandidate, sal_uInt32 nIndex, B2VectorContinuity eContinuity)
2621 {
2622 OSL_ENSURE(nIndex < rCandidate.count(), "setContinuityInPoint: Access to polygon out of range (!)");
2623 bool bRetval(false);
2624 const sal_uInt32 nPointCount(rCandidate.count());
2625
2626 if(nPointCount)
2627 {
2628 const B2DPoint aCurrentPoint(rCandidate.getB2DPoint(nIndex));
2629
2630 switch(eContinuity)
2631 {
2632 case CONTINUITY_NONE :
2633 {
2634 if(rCandidate.isPrevControlPointUsed(nIndex))
2635 {
2636 if(!rCandidate.isClosed() && 0 == nIndex)
2637 {
2638 // remove existing previous vector for start point of open polygon
2639 rCandidate.resetPrevControlPoint(nIndex);
2640 }
2641 else
2642 {
2643 const sal_uInt32 nPrevIndex((nIndex + (nPointCount - 1)) % nPointCount);
2644 rCandidate.setPrevControlPoint(nIndex, interpolate(aCurrentPoint, rCandidate.getB2DPoint(nPrevIndex), 1.0 / 3.0));
2645 }
2646
2647 bRetval = true;
2648 }
2649
2650 if(rCandidate.isNextControlPointUsed(nIndex))
2651 {
2652 if(!rCandidate.isClosed() && nIndex == nPointCount + 1)
2653 {
2654 // remove next vector for end point of open polygon
2655 rCandidate.resetNextControlPoint(nIndex);
2656 }
2657 else
2658 {
2659 const sal_uInt32 nNextIndex((nIndex + 1) % nPointCount);
2660 rCandidate.setNextControlPoint(nIndex, interpolate(aCurrentPoint, rCandidate.getB2DPoint(nNextIndex), 1.0 / 3.0));
2661 }
2662
2663 bRetval = true;
2664 }
2665
2666 break;
2667 }
2668 case CONTINUITY_C1 :
2669 {
2670 if(rCandidate.isPrevControlPointUsed(nIndex) && rCandidate.isNextControlPointUsed(nIndex))
2671 {
2672 // lengths both exist since both are used
2673 B2DVector aVectorPrev(rCandidate.getPrevControlPoint(nIndex) - aCurrentPoint);
2674 B2DVector aVectorNext(rCandidate.getNextControlPoint(nIndex) - aCurrentPoint);
2675 const double fLenPrev(aVectorPrev.getLength());
2676 const double fLenNext(aVectorNext.getLength());
2677 aVectorPrev.normalize();
2678 aVectorNext.normalize();
2679 const B2VectorOrientation aOrientation(getOrientation(aVectorPrev, aVectorNext));
2680
2681 if(ORIENTATION_NEUTRAL == aOrientation && aVectorPrev.scalar(aVectorNext) < 0.0)
2682 {
2683 // parallel and opposite direction; check length
2684 if(fTools::equal(fLenPrev, fLenNext))
2685 {
2686 // this would be even C2, but we want C1. Use the lengths of the corresponding edges.
2687 const sal_uInt32 nPrevIndex((nIndex + (nPointCount - 1)) % nPointCount);
2688 const sal_uInt32 nNextIndex((nIndex + 1) % nPointCount);
2689 const double fLenPrevEdge(B2DVector(rCandidate.getB2DPoint(nPrevIndex) - aCurrentPoint).getLength() * (1.0 / 3.0));
2690 const double fLenNextEdge(B2DVector(rCandidate.getB2DPoint(nNextIndex) - aCurrentPoint).getLength() * (1.0 / 3.0));
2691
2692 rCandidate.setControlPoints(nIndex,
2693 aCurrentPoint + (aVectorPrev * fLenPrevEdge),
2694 aCurrentPoint + (aVectorNext * fLenNextEdge));
2695 bRetval = true;
2696 }
2697 }
2698 else
2699 {
2700 // not parallel or same direction, set vectors and length
2701 const B2DVector aNormalizedPerpendicular(getNormalizedPerpendicular(aVectorPrev + aVectorNext));
2702
2703 if(ORIENTATION_POSITIVE == aOrientation)
2704 {
2705 rCandidate.setControlPoints(nIndex,
2706 aCurrentPoint - (aNormalizedPerpendicular * fLenPrev),
2707 aCurrentPoint + (aNormalizedPerpendicular * fLenNext));
2708 }
2709 else
2710 {
2711 rCandidate.setControlPoints(nIndex,
2712 aCurrentPoint + (aNormalizedPerpendicular * fLenPrev),
2713 aCurrentPoint - (aNormalizedPerpendicular * fLenNext));
2714 }
2715
2716 bRetval = true;
2717 }
2718 }
2719 break;
2720 }
2721 case CONTINUITY_C2 :
2722 {
2723 if(rCandidate.isPrevControlPointUsed(nIndex) && rCandidate.isNextControlPointUsed(nIndex))
2724 {
2725 // lengths both exist since both are used
2726 B2DVector aVectorPrev(rCandidate.getPrevControlPoint(nIndex) - aCurrentPoint);
2727 B2DVector aVectorNext(rCandidate.getNextControlPoint(nIndex) - aCurrentPoint);
2728 const double fCommonLength((aVectorPrev.getLength() + aVectorNext.getLength()) / 2.0);
2729 aVectorPrev.normalize();
2730 aVectorNext.normalize();
2731 const B2VectorOrientation aOrientation(getOrientation(aVectorPrev, aVectorNext));
2732
2733 if(ORIENTATION_NEUTRAL == aOrientation && aVectorPrev.scalar(aVectorNext) < 0.0)
2734 {
2735 // parallel and opposite direction; set length. Use one direction for better numerical correctness
2736 const B2DVector aScaledDirection(aVectorPrev * fCommonLength);
2737
2738 rCandidate.setControlPoints(nIndex,
2739 aCurrentPoint + aScaledDirection,
2740 aCurrentPoint - aScaledDirection);
2741 }
2742 else
2743 {
2744 // not parallel or same direction, set vectors and length
2745 const B2DVector aNormalizedPerpendicular(getNormalizedPerpendicular(aVectorPrev + aVectorNext));
2746 const B2DVector aPerpendicular(aNormalizedPerpendicular * fCommonLength);
2747
2748 if(ORIENTATION_POSITIVE == aOrientation)
2749 {
2750 rCandidate.setControlPoints(nIndex,
2751 aCurrentPoint - aPerpendicular,
2752 aCurrentPoint + aPerpendicular);
2753 }
2754 else
2755 {
2756 rCandidate.setControlPoints(nIndex,
2757 aCurrentPoint + aPerpendicular,
2758 aCurrentPoint - aPerpendicular);
2759 }
2760 }
2761
2762 bRetval = true;
2763 }
2764 break;
2765 }
2766 }
2767 }
2768
2769 return bRetval;
2770 }
2771
2772 B2DPolygon growInNormalDirection(const B2DPolygon& rCandidate, double fValue)
2773 {
2774 if(0.0 != fValue)
2775 {
2776 if(rCandidate.areControlPointsUsed())
2777 {
2778 // call myself recursively with subdivided input
2779 const B2DPolygon aCandidate(adaptiveSubdivideByAngle(rCandidate));
2780 return growInNormalDirection(aCandidate, fValue);
2781 }
2782 else
2783 {
2784 B2DPolygon aRetval;
2785 const sal_uInt32 nPointCount(rCandidate.count());
2786
2787 if(nPointCount)
2788 {
2789 B2DPoint aPrev(rCandidate.getB2DPoint(nPointCount - 1L));
2790 B2DPoint aCurrent(rCandidate.getB2DPoint(0L));
2791
2792 for(sal_uInt32 a(0L); a < nPointCount; a++)
2793 {
2794 const B2DPoint aNext(rCandidate.getB2DPoint(a + 1L == nPointCount ? 0L : a + 1L));
2795 const B2DVector aBack(aPrev - aCurrent);
2796 const B2DVector aForw(aNext - aCurrent);
2797 const B2DVector aPerpBack(getNormalizedPerpendicular(aBack));
2798 const B2DVector aPerpForw(getNormalizedPerpendicular(aForw));
2799 B2DVector aDirection(aPerpBack - aPerpForw);
2800 aDirection.normalize();
2801 aDirection *= fValue;
2802 aRetval.append(aCurrent + aDirection);
2803
2804 // prepare next step
2805 aPrev = aCurrent;
2806 aCurrent = aNext;
2807 }
2808 }
2809
2810 // copy closed state
2811 aRetval.setClosed(rCandidate.isClosed());
2812
2813 return aRetval;
2814 }
2815 }
2816 else
2817 {
2818 return rCandidate;
2819 }
2820 }
2821
2822 B2DPolygon reSegmentPolygon(const B2DPolygon& rCandidate, sal_uInt32 nSegments)
2823 {
2824 B2DPolygon aRetval;
2825 const sal_uInt32 nPointCount(rCandidate.count());
2826
2827 if(nPointCount && nSegments)
2828 {
2829 // get current segment count
2830 const sal_uInt32 nSegmentCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1L);
2831
2832 if(nSegmentCount == nSegments)
2833 {
2834 aRetval = rCandidate;
2835 }
2836 else
2837 {
2838 const double fLength(getLength(rCandidate));
2839 const sal_uInt32 nLoopCount(rCandidate.isClosed() ? nSegments : nSegments + 1L);
2840
2841 for(sal_uInt32 a(0L); a < nLoopCount; a++)
2842 {
2843 const double fRelativePos((double)a / (double)nSegments); // 0.0 .. 1.0
2844 const B2DPoint aNewPoint(getPositionRelative(rCandidate, fRelativePos, fLength));
2845 aRetval.append(aNewPoint);
2846 }
2847
2848 // copy closed flag
2849 aRetval.setClosed(rCandidate.isClosed());
2850 }
2851 }
2852
2853 return aRetval;
2854 }
2855
2856 B2DPolygon interpolate(const B2DPolygon& rOld1, const B2DPolygon& rOld2, double t)
2857 {
2858 OSL_ENSURE(rOld1.count() == rOld2.count(), "B2DPolygon interpolate: Different geometry (!)");
2859
2860 if(fTools::lessOrEqual(t, 0.0) || rOld1 == rOld2)
2861 {
2862 return rOld1;
2863 }
2864 else if(fTools::moreOrEqual(t, 1.0))
2865 {
2866 return rOld2;
2867 }
2868 else
2869 {
2870 B2DPolygon aRetval;
2871 const bool bInterpolateVectors(rOld1.areControlPointsUsed() || rOld2.areControlPointsUsed());
2872 aRetval.setClosed(rOld1.isClosed() && rOld2.isClosed());
2873
2874 for(sal_uInt32 a(0L); a < rOld1.count(); a++)
2875 {
2876 aRetval.append(interpolate(rOld1.getB2DPoint(a), rOld2.getB2DPoint(a), t));
2877
2878 if(bInterpolateVectors)
2879 {
2880 aRetval.setPrevControlPoint(a, interpolate(rOld1.getPrevControlPoint(a), rOld2.getPrevControlPoint(a), t));
2881 aRetval.setNextControlPoint(a, interpolate(rOld1.getNextControlPoint(a), rOld2.getNextControlPoint(a), t));
2882 }
2883 }
2884
2885 return aRetval;
2886 }
2887 }
2888
2889 // #i76891#
2890 B2DPolygon simplifyCurveSegments(const B2DPolygon& rCandidate)
2891 {
2892 const sal_uInt32 nPointCount(rCandidate.count());
2893
2894 if(nPointCount && rCandidate.areControlPointsUsed())
2895 {
2896 // prepare loop
2897 const sal_uInt32 nEdgeCount(rCandidate.isClosed() ? nPointCount : nPointCount - 1);
2898 B2DPolygon aRetval;
2899 B2DCubicBezier aBezier;
2900 aBezier.setStartPoint(rCandidate.getB2DPoint(0));
2901
2902 // try to avoid costly reallocations
2903 aRetval.reserve( nEdgeCount+1);
2904
2905 // add start point
2906 aRetval.append(aBezier.getStartPoint());
2907
2908 for(sal_uInt32 a(0L); a < nEdgeCount; a++)
2909 {
2910 // get values for edge
2911 const sal_uInt32 nNextIndex((a + 1) % nPointCount);
2912 aBezier.setEndPoint(rCandidate.getB2DPoint(nNextIndex));
2913 aBezier.setControlPointA(rCandidate.getNextControlPoint(a));
2914 aBezier.setControlPointB(rCandidate.getPrevControlPoint(nNextIndex));
2915 aBezier.testAndSolveTrivialBezier();
2916
2917 // still bezier?
2918 if(aBezier.isBezier())
2919 {
2920 // add edge with control vectors
2921 aRetval.appendBezierSegment(aBezier.getControlPointA(), aBezier.getControlPointB(), aBezier.getEndPoint());
2922 }
2923 else
2924 {
2925 // add edge
2926 aRetval.append(aBezier.getEndPoint());
2927 }
2928
2929 // next point
2930 aBezier.setStartPoint(aBezier.getEndPoint());
2931 }
2932
2933 if(rCandidate.isClosed())
2934 {
2935 // set closed flag, rescue control point and correct last double point
2936 closeWithGeometryChange(aRetval);
2937 }
2938
2939 return aRetval;
2940 }
2941 else
2942 {
2943 return rCandidate;
2944 }
2945 }
2946
2947 // makes the given indexed point the new polygon start point. To do that, the points in the
2948 // polygon will be rotated. This is only valid for closed polygons, for non-closed ones
2949 // an assertion will be triggered
2950 B2DPolygon makeStartPoint(const B2DPolygon& rCandidate, sal_uInt32 nIndexOfNewStatPoint)
2951 {
2952 const sal_uInt32 nPointCount(rCandidate.count());
2953
2954 if(nPointCount > 2 && nIndexOfNewStatPoint != 0 && nIndexOfNewStatPoint < nPointCount)
2955 {
2956 OSL_ENSURE(rCandidate.isClosed(), "makeStartPoint: only valid for closed polygons (!)");
2957 B2DPolygon aRetval;
2958
2959 for(sal_uInt32 a(0); a < nPointCount; a++)
2960 {
2961 const sal_uInt32 nSourceIndex((a + nIndexOfNewStatPoint) % nPointCount);
2962 aRetval.append(rCandidate.getB2DPoint(nSourceIndex));
2963
2964 if(rCandidate.areControlPointsUsed())
2965 {
2966 aRetval.setPrevControlPoint(a, rCandidate.getPrevControlPoint(nSourceIndex));
2967 aRetval.setNextControlPoint(a, rCandidate.getNextControlPoint(nSourceIndex));
2968 }
2969 }
2970
2971 return aRetval;
2972 }
2973
2974 return rCandidate;
2975 }
2976
2977 B2DPolygon createEdgesOfGivenLength(const B2DPolygon& rCandidate, double fLength, double fStart, double fEnd)
2978 {
2979 B2DPolygon aRetval;
2980
2981 if(fLength < 0.0)
2982 {
2983 fLength = 0.0;
2984 }
2985
2986 if(!fTools::equalZero(fLength))
2987 {
2988 if(fStart < 0.0)
2989 {
2990 fStart = 0.0;
2991 }
2992
2993 if(fEnd < 0.0)
2994 {
2995 fEnd = 0.0;
2996 }
2997
2998 if(fEnd < fStart)
2999 {
3000 fEnd = fStart;
3001 }
3002
3003 // iterate and consume pieces with fLength. First subdivide to reduce input to line segments
3004 const B2DPolygon aCandidate(rCandidate.areControlPointsUsed() ? rCandidate.getDefaultAdaptiveSubdivision() : rCandidate);
3005 const sal_uInt32 nPointCount(aCandidate.count());
3006
3007 if(nPointCount > 1)
3008 {
3009 const bool bEndActive(!fTools::equalZero(fEnd));
3010 const sal_uInt32 nEdgeCount(aCandidate.isClosed() ? nPointCount : nPointCount - 1);
3011 B2DPoint aCurrent(aCandidate.getB2DPoint(0));
3012 double fPositionInEdge(fStart);
3013 double fAbsolutePosition(fStart);
3014
3015 for(sal_uInt32 a(0); a < nEdgeCount; a++)
3016 {
3017 const sal_uInt32 nNextIndex((a + 1) % nPointCount);
3018 const B2DPoint aNext(aCandidate.getB2DPoint(nNextIndex));
3019 const B2DVector aEdge(aNext - aCurrent);
3020 double fEdgeLength(aEdge.getLength());
3021
3022 if(!fTools::equalZero(fEdgeLength))
3023 {
3024 while(fTools::less(fPositionInEdge, fEdgeLength))
3025 {
3026 // move position on edge forward as long as on edge
3027 const double fScalar(fPositionInEdge / fEdgeLength);
3028 aRetval.append(aCurrent + (aEdge * fScalar));
3029 fPositionInEdge += fLength;
3030
3031 if(bEndActive)
3032 {
3033 fAbsolutePosition += fLength;
3034
3035 if(fTools::more(fAbsolutePosition, fEnd))
3036 {
3037 break;
3038 }
3039 }
3040 }
3041
3042 // substract length of current edge
3043 fPositionInEdge -= fEdgeLength;
3044 }
3045
3046 if(bEndActive && fTools::more(fAbsolutePosition, fEnd))
3047 {
3048 break;
3049 }
3050
3051 // prepare next step
3052 aCurrent = aNext;
3053 }
3054
3055 // keep closed state
3056 aRetval.setClosed(aCandidate.isClosed());
3057 }
3058 else
3059 {
3060 // source polygon has only one point, return unchanged
3061 aRetval = aCandidate;
3062 }
3063 }
3064
3065 return aRetval;
3066 }
3067
3068 B2DPolygon createWaveline(const B2DPolygon& rCandidate, double fWaveWidth, double fWaveHeight)
3069 {
3070 B2DPolygon aRetval;
3071
3072 if(fWaveWidth < 0.0)
3073 {
3074 fWaveWidth = 0.0;
3075 }
3076
3077 if(fWaveHeight < 0.0)
3078 {
3079 fWaveHeight = 0.0;
3080 }
3081
3082 const bool bHasWidth(!fTools::equalZero(fWaveWidth));
3083
3084 if(bHasWidth)
3085 {
3086 const bool bHasHeight(!fTools::equalZero(fWaveHeight));
3087 if(bHasHeight)
3088 {
3089 // width and height, create waveline. First subdivide to reduce input to line segments
3090 // of WaveWidth. Last segment may be missing. If this turns out to be a problem, it
3091 // may be added here again using the original last point from rCandidate. It may
3092 // also be the case that rCandidate was closed. To simplify things it is handled here
3093 // as if it was opened.
3094 // Result from createEdgesOfGivenLength contains no curved segments, handle as straight
3095 // edges.
3096 const B2DPolygon aEqualLenghEdges(createEdgesOfGivenLength(rCandidate, fWaveWidth));
3097 const sal_uInt32 nPointCount(aEqualLenghEdges.count());
3098
3099 if(nPointCount > 1)
3100 {
3101 // iterate over straight edges, add start point
3102 B2DPoint aCurrent(aEqualLenghEdges.getB2DPoint(0));
3103 aRetval.append(aCurrent);
3104
3105 for(sal_uInt32 a(0); a < nPointCount - 1; a++)
3106 {
3107 const sal_uInt32 nNextIndex((a + 1) % nPointCount);
3108 const B2DPoint aNext(aEqualLenghEdges.getB2DPoint(nNextIndex));
3109 const B2DVector aEdge(aNext - aCurrent);
3110 const B2DVector aPerpendicular(getNormalizedPerpendicular(aEdge));
3111 const B2DVector aControlOffset((aEdge * 0.467308) - (aPerpendicular * fWaveHeight));
3112
3113 // add curve segment
3114 aRetval.appendBezierSegment(
3115 aCurrent + aControlOffset,
3116 aNext - aControlOffset,
3117 aNext);
3118
3119 // prepare next step
3120 aCurrent = aNext;
3121 }
3122 }
3123 }
3124 else
3125 {
3126 // width but no height -> return original polygon
3127 aRetval = rCandidate;
3128 }
3129 }
3130 else
3131 {
3132 // no width -> no waveline, stay empty and return
3133 }
3134
3135 return aRetval;
3136 }
3137
3138 // snap points of horizontal or vertical edges to discrete values
3139 B2DPolygon snapPointsOfHorizontalOrVerticalEdges(const B2DPolygon& rCandidate)
3140 {
3141 const sal_uInt32 nPointCount(rCandidate.count());
3142
3143 if(nPointCount > 1)
3144 {
3145 // Start by copying the source polygon to get a writeable copy. The closed state is
3146 // copied by aRetval's initialisation, too, so no need to copy it in this method
3147 B2DPolygon aRetval(rCandidate);
3148
3149 // prepare geometry data. Get rounded from original
3150 B2ITuple aPrevTuple(basegfx::fround(rCandidate.getB2DPoint(nPointCount - 1)));
3151 B2DPoint aCurrPoint(rCandidate.getB2DPoint(0));
3152 B2ITuple aCurrTuple(basegfx::fround(aCurrPoint));
3153
3154 // loop over all points. This will also snap the implicit closing edge
3155 // even when not closed, but that's no problem here
3156 for(sal_uInt32 a(0); a < nPointCount; a++)
3157 {
3158 // get next point. Get rounded from original
3159 const bool bLastRun(a + 1 == nPointCount);
3160 const sal_uInt32 nNextIndex(bLastRun ? 0 : a + 1);
3161 const B2DPoint aNextPoint(rCandidate.getB2DPoint(nNextIndex));
3162 const B2ITuple aNextTuple(basegfx::fround(aNextPoint));
3163
3164 // get the states
3165 const bool bPrevVertical(aPrevTuple.getX() == aCurrTuple.getX());
3166 const bool bNextVertical(aNextTuple.getX() == aCurrTuple.getX());
3167 const bool bPrevHorizontal(aPrevTuple.getY() == aCurrTuple.getY());
3168 const bool bNextHorizontal(aNextTuple.getY() == aCurrTuple.getY());
3169 const bool bSnapX(bPrevVertical || bNextVertical);
3170 const bool bSnapY(bPrevHorizontal || bNextHorizontal);
3171
3172 if(bSnapX || bSnapY)
3173 {
3174 const B2DPoint aSnappedPoint(
3175 bSnapX ? aCurrTuple.getX() : aCurrPoint.getX(),
3176 bSnapY ? aCurrTuple.getY() : aCurrPoint.getY());
3177
3178 aRetval.setB2DPoint(a, aSnappedPoint);
3179 }
3180
3181 // prepare next point
3182 if(!bLastRun)
3183 {
3184 aPrevTuple = aCurrTuple;
3185 aCurrPoint = aNextPoint;
3186 aCurrTuple = aNextTuple;
3187 }
3188 }
3189
3190 return aRetval;
3191 }
3192 else
3193 {
3194 return rCandidate;
3195 }
3196 }
3197
3198 } // end of namespace tools
3199 } // end of namespace basegfx
3200
3201 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
FREE OFFICE SUITE