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