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