Debian Codegraph @

basegfx/source/curve/b2dcubicbezier.cxx

raw
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/curve/b2dcubicbezier.hxx>
21 #include <basegfx/range/b2drange.hxx>
22 #include <basegfx/vector/b2dvector.hxx>
23 #include <basegfx/polygon/b2dpolygon.hxx>
24 #include <basegfx/matrix/b2dhommatrix.hxx>
25 #include <basegfx/numeric/ftools.hxx>
26
27 #include <osl/diagnose.h>
28
29 #include <cassert>
30 #include <cmath>
31 #include <limits>
32
33 constexpr double FACTOR_FOR_UNSHARPEN = 1.6;
34 // #i37443#
35 #ifdef DBG_UTIL
36 const double fMultFactUnsharpen = FACTOR_FOR_UNSHARPEN;
37 #endif
38
39 namespace basegfx
40 {
41 namespace
42 {
43 void ImpSubDivAngle(
44 const B2DPoint& rfPA, // start point
45 const B2DPoint& rfEA, // edge on A
46 const B2DPoint& rfEB, // edge on B
47 const B2DPoint& rfPB, // end point
48 B2DPolygon& rTarget, // target polygon
49 double fAngleBound, // angle bound in [0.0 .. 2PI]
50 bool bAllowUnsharpen, // #i37443# allow the criteria to get unsharp in recursions
51 sal_uInt16 nMaxRecursionDepth) // endless loop protection
52 {
53 if(nMaxRecursionDepth)
54 {
55 // do angle test
56 B2DVector aLeft(rfEA - rfPA);
57 B2DVector aRight(rfEB - rfPB);
58
59 // #i72104#
60 if(aLeft.equalZero())
61 {
62 aLeft = rfEB - rfPA;
63 }
64
65 if(aRight.equalZero())
66 {
67 aRight = rfEA - rfPB;
68 }
69
70 const double fCurrentAngle(aLeft.angle(aRight));
71
72 if(fabs(fCurrentAngle) > (M_PI - fAngleBound))
73 {
74 // end recursion
75 nMaxRecursionDepth = 0;
76 }
77 else
78 {
79 if(bAllowUnsharpen)
80 {
81 // #i37443# unsharpen criteria
82 #ifdef DBG_UTIL
83 fAngleBound *= fMultFactUnsharpen;
84 #else
85 fAngleBound *= FACTOR_FOR_UNSHARPEN;
86 #endif
87 }
88 }
89 }
90
91 if(nMaxRecursionDepth)
92 {
93 // divide at 0.5
94 const B2DPoint aS1L(average(rfPA, rfEA));
95 const B2DPoint aS1C(average(rfEA, rfEB));
96 const B2DPoint aS1R(average(rfEB, rfPB));
97 const B2DPoint aS2L(average(aS1L, aS1C));
98 const B2DPoint aS2R(average(aS1C, aS1R));
99 const B2DPoint aS3C(average(aS2L, aS2R));
100
101 // left recursion
102 ImpSubDivAngle(rfPA, aS1L, aS2L, aS3C, rTarget, fAngleBound, bAllowUnsharpen, nMaxRecursionDepth - 1);
103
104 // right recursion
105 ImpSubDivAngle(aS3C, aS2R, aS1R, rfPB, rTarget, fAngleBound, bAllowUnsharpen, nMaxRecursionDepth - 1);
106 }
107 else
108 {
109 rTarget.append(rfPB);
110 }
111 }
112
113 void ImpSubDivAngleStart(
114 const B2DPoint& rfPA, // start point
115 const B2DPoint& rfEA, // edge on A
116 const B2DPoint& rfEB, // edge on B
117 const B2DPoint& rfPB, // end point
118 B2DPolygon& rTarget, // target polygon
119 const double& rfAngleBound) // angle bound in [0.0 .. 2PI]
120 {
121 sal_uInt16 nMaxRecursionDepth(8);
122 const B2DVector aLeft(rfEA - rfPA);
123 const B2DVector aRight(rfEB - rfPB);
124 bool bLeftEqualZero(aLeft.equalZero());
125 bool bRightEqualZero(aRight.equalZero());
126 bool bAllParallel(false);
127
128 if(bLeftEqualZero && bRightEqualZero)
129 {
130 nMaxRecursionDepth = 0;
131 }
132 else
133 {
134 const B2DVector aBase(rfPB - rfPA);
135 const bool bBaseEqualZero(aBase.equalZero()); // #i72104#
136
137 if(!bBaseEqualZero)
138 {
139 const bool bLeftParallel(bLeftEqualZero || areParallel(aLeft, aBase));
140 const bool bRightParallel(bRightEqualZero || areParallel(aRight, aBase));
141
142 if(bLeftParallel && bRightParallel)
143 {
144 bAllParallel = true;
145
146 if(!bLeftEqualZero)
147 {
148 double fFactor;
149
150 if(fabs(aBase.getX()) > fabs(aBase.getY()))
151 {
152 fFactor = aLeft.getX() / aBase.getX();
153 }
154 else
155 {
156 fFactor = aLeft.getY() / aBase.getY();
157 }
158
159 if(fFactor >= 0.0 && fFactor <= 1.0)
160 {
161 bLeftEqualZero = true;
162 }
163 }
164
165 if(!bRightEqualZero)
166 {
167 double fFactor;
168
169 if(fabs(aBase.getX()) > fabs(aBase.getY()))
170 {
171 fFactor = aRight.getX() / -aBase.getX();
172 }
173 else
174 {
175 fFactor = aRight.getY() / -aBase.getY();
176 }
177
178 if(fFactor >= 0.0 && fFactor <= 1.0)
179 {
180 bRightEqualZero = true;
181 }
182 }
183
184 if(bLeftEqualZero && bRightEqualZero)
185 {
186 nMaxRecursionDepth = 0;
187 }
188 }
189 }
190 }
191
192 if(nMaxRecursionDepth)
193 {
194 // divide at 0.5 ad test both edges for angle criteria
195 const B2DPoint aS1L(average(rfPA, rfEA));
196 const B2DPoint aS1C(average(rfEA, rfEB));
197 const B2DPoint aS1R(average(rfEB, rfPB));
198 const B2DPoint aS2L(average(aS1L, aS1C));
199 const B2DPoint aS2R(average(aS1C, aS1R));
200 const B2DPoint aS3C(average(aS2L, aS2R));
201
202 // test left
203 bool bAngleIsSmallerLeft(bAllParallel && bLeftEqualZero);
204 if(!bAngleIsSmallerLeft)
205 {
206 const B2DVector aLeftLeft(bLeftEqualZero ? aS2L - aS1L : aS1L - rfPA); // #i72104#
207 const B2DVector aRightLeft(aS2L - aS3C);
208 const double fCurrentAngleLeft(aLeftLeft.angle(aRightLeft));
209 bAngleIsSmallerLeft = (fabs(fCurrentAngleLeft) > (M_PI - rfAngleBound));
210 }
211
212 // test right
213 bool bAngleIsSmallerRight(bAllParallel && bRightEqualZero);
214 if(!bAngleIsSmallerRight)
215 {
216 const B2DVector aLeftRight(aS2R - aS3C);
217 const B2DVector aRightRight(bRightEqualZero ? aS2R - aS1R : aS1R - rfPB); // #i72104#
218 const double fCurrentAngleRight(aLeftRight.angle(aRightRight));
219 bAngleIsSmallerRight = (fabs(fCurrentAngleRight) > (M_PI - rfAngleBound));
220 }
221
222 if(bAngleIsSmallerLeft && bAngleIsSmallerRight)
223 {
224 // no recursion necessary at all
225 nMaxRecursionDepth = 0;
226 }
227 else
228 {
229 // left
230 if(bAngleIsSmallerLeft)
231 {
232 rTarget.append(aS3C);
233 }
234 else
235 {
236 ImpSubDivAngle(rfPA, aS1L, aS2L, aS3C, rTarget, rfAngleBound, true/*bAllowUnsharpen*/, nMaxRecursionDepth);
237 }
238
239 // right
240 if(bAngleIsSmallerRight)
241 {
242 rTarget.append(rfPB);
243 }
244 else
245 {
246 ImpSubDivAngle(aS3C, aS2R, aS1R, rfPB, rTarget, rfAngleBound, true/*bAllowUnsharpen*/, nMaxRecursionDepth);
247 }
248 }
249 }
250
251 if(!nMaxRecursionDepth)
252 {
253 rTarget.append(rfPB);
254 }
255 }
256
257 void ImpSubDivDistance(
258 const B2DPoint& rfPA, // start point
259 const B2DPoint& rfEA, // edge on A
260 const B2DPoint& rfEB, // edge on B
261 const B2DPoint& rfPB, // end point
262 B2DPolygon& rTarget, // target polygon
263 double fDistanceBound2, // quadratic distance criteria
264 double fLastDistanceError2, // the last quadratic distance error
265 sal_uInt16 nMaxRecursionDepth) // endless loop protection
266 {
267 if(nMaxRecursionDepth)
268 {
269 // decide if another recursion is needed. If not, set
270 // nMaxRecursionDepth to zero
271
272 // Perform bezier flatness test (lecture notes from R. Schaback,
273 // Mathematics of Computer-Aided Design, Uni Goettingen, 2000)
274
275 // ||P(t) - L(t)|| <= max ||b_j - b_0 - j/n(b_n - b_0)||
276 // 0<=j<=n
277
278 // What is calculated here is an upper bound to the distance from
279 // a line through b_0 and b_3 (rfPA and P4 in our notation) and the
280 // curve. We can drop 0 and n from the running indices, since the
281 // argument of max becomes zero for those cases.
282 const double fJ1x(rfEA.getX() - rfPA.getX() - 1.0/3.0*(rfPB.getX() - rfPA.getX()));
283 const double fJ1y(rfEA.getY() - rfPA.getY() - 1.0/3.0*(rfPB.getY() - rfPA.getY()));
284 const double fJ2x(rfEB.getX() - rfPA.getX() - 2.0/3.0*(rfPB.getX() - rfPA.getX()));
285 const double fJ2y(rfEB.getY() - rfPA.getY() - 2.0/3.0*(rfPB.getY() - rfPA.getY()));
286 const double fDistanceError2(std::max(fJ1x*fJ1x + fJ1y*fJ1y, fJ2x*fJ2x + fJ2y*fJ2y));
287
288 // stop if error measure does not improve anymore. This is a
289 // safety guard against floating point inaccuracies.
290 // stop if distance from line is guaranteed to be bounded by d
291 const bool bFurtherDivision(fLastDistanceError2 > fDistanceError2 && fDistanceError2 >= fDistanceBound2);
292
293 if(bFurtherDivision)
294 {
295 // remember last error value
296 fLastDistanceError2 = fDistanceError2;
297 }
298 else
299 {
300 // stop recursion
301 nMaxRecursionDepth = 0;
302 }
303 }
304
305 if(nMaxRecursionDepth)
306 {
307 // divide at 0.5
308 const B2DPoint aS1L(average(rfPA, rfEA));
309 const B2DPoint aS1C(average(rfEA, rfEB));
310 const B2DPoint aS1R(average(rfEB, rfPB));
311 const B2DPoint aS2L(average(aS1L, aS1C));
312 const B2DPoint aS2R(average(aS1C, aS1R));
313 const B2DPoint aS3C(average(aS2L, aS2R));
314
315 // left recursion
316 ImpSubDivDistance(rfPA, aS1L, aS2L, aS3C, rTarget, fDistanceBound2, fLastDistanceError2, nMaxRecursionDepth - 1);
317
318 // right recursion
319 ImpSubDivDistance(aS3C, aS2R, aS1R, rfPB, rTarget, fDistanceBound2, fLastDistanceError2, nMaxRecursionDepth - 1);
320 }
321 else
322 {
323 rTarget.append(rfPB);
324 }
325 }
326 } // end of anonymous namespace
327 } // end of namespace basegfx
328
329 namespace basegfx
330 {
331 B2DCubicBezier::B2DCubicBezier(const B2DCubicBezier&) = default;
332
333 B2DCubicBezier::B2DCubicBezier() = default;
334
335 B2DCubicBezier::B2DCubicBezier(const B2DPoint& rStart, const B2DPoint& rControlPointA, const B2DPoint& rControlPointB, const B2DPoint& rEnd)
336 : maStartPoint(rStart),
337 maEndPoint(rEnd),
338 maControlPointA(rControlPointA),
339 maControlPointB(rControlPointB)
340 {
341 }
342
343 // assignment operator
344 B2DCubicBezier& B2DCubicBezier::operator=(const B2DCubicBezier&) = default;
345
346 // compare operators
347 bool B2DCubicBezier::operator==(const B2DCubicBezier& rBezier) const
348 {
349 return (
350 maStartPoint == rBezier.maStartPoint
351 && maEndPoint == rBezier.maEndPoint
352 && maControlPointA == rBezier.maControlPointA
353 && maControlPointB == rBezier.maControlPointB
354 );
355 }
356
357 bool B2DCubicBezier::equal(const B2DCubicBezier& rBezier) const
358 {
359 return (
360 maStartPoint.equal(rBezier.maStartPoint)
361 && maEndPoint.equal(rBezier.maEndPoint)
362 && maControlPointA.equal(rBezier.maControlPointA)
363 && maControlPointB.equal(rBezier.maControlPointB)
364 );
365 }
366
367 // test if vectors are used
368 bool B2DCubicBezier::isBezier() const
369 {
370 return maControlPointA != maStartPoint || maControlPointB != maEndPoint;
371 }
372
373 void B2DCubicBezier::testAndSolveTrivialBezier()
374 {
375 if(maControlPointA == maStartPoint && maControlPointB == maEndPoint)
376 return;
377
378 const B2DVector aEdge(maEndPoint - maStartPoint);
379
380 // controls parallel to edge can be trivial. No edge -> not parallel -> control can
381 // still not be trivial (e.g. ballon loop)
382 if(aEdge.equalZero())
383 return;
384
385 // get control vectors
386 const B2DVector aVecA(maControlPointA - maStartPoint);
387 const B2DVector aVecB(maControlPointB - maEndPoint);
388
389 // check if trivial per se
390 bool bAIsTrivial(aVecA.equalZero());
391 bool bBIsTrivial(aVecB.equalZero());
392
393 // #i102241# prepare inverse edge length to normalize cross values;
394 // else the small compare value used in fTools::equalZero
395 // will be length dependent and this detection will work as less
396 // precise as longer the edge is. In principle, the length of the control
397 // vector would need to be used too, but to be trivial it is assumed to
398 // be of roughly equal length to the edge, so edge length can be used
399 // for both. Only needed when one of both is not trivial per se.
400 const double fInverseEdgeLength(bAIsTrivial && bBIsTrivial
401 ? 1.0
402 : 1.0 / aEdge.getLength());
403
404 // if A is not zero, check if it could be
405 if(!bAIsTrivial)
406 {
407 // #i102241# parallel to edge? Check aVecA, aEdge. Use cross() which does what
408 // we need here with the precision we need
409 const double fCross(aVecA.cross(aEdge) * fInverseEdgeLength);
410
411 if(fTools::equalZero(fCross))
412 {
413 // get scale to edge. Use bigger distance for numeric quality
414 const double fScale(fabs(aEdge.getX()) > fabs(aEdge.getY())
415 ? aVecA.getX() / aEdge.getX()
416 : aVecA.getY() / aEdge.getY());
417
418 // relative end point of vector in edge range?
419 if (fTools::betweenOrEqualEither(fScale, 0.0, 1.0))
420 {
421 bAIsTrivial = true;
422 }
423 }
424 }
425
426 // if B is not zero, check if it could be, but only if A is already trivial;
427 // else solve to trivial will not be possible for whole edge
428 if(bAIsTrivial && !bBIsTrivial)
429 {
430 // parallel to edge? Check aVecB, aEdge
431 const double fCross(aVecB.cross(aEdge) * fInverseEdgeLength);
432
433 if(fTools::equalZero(fCross))
434 {
435 // get scale to edge. Use bigger distance for numeric quality
436 const double fScale(fabs(aEdge.getX()) > fabs(aEdge.getY())
437 ? aVecB.getX() / aEdge.getX()
438 : aVecB.getY() / aEdge.getY());
439
440 // end point of vector in edge range? Caution: controlB is directed AGAINST edge
441 if (fTools::betweenOrEqualEither(fScale, -1.0, 0.0))
442 {
443 bBIsTrivial = true;
444 }
445 }
446 }
447
448 // if both are/can be reduced, do it.
449 // Not possible if only one is/can be reduced (!)
450 if(bAIsTrivial && bBIsTrivial)
451 {
452 maControlPointA = maStartPoint;
453 maControlPointB = maEndPoint;
454 }
455 }
456
457 namespace {
458 double impGetLength(const B2DCubicBezier& rEdge, double fDeviation, sal_uInt32 nRecursionWatch)
459 {
460 const double fEdgeLength(rEdge.getEdgeLength());
461 const double fControlPolygonLength(rEdge.getControlPolygonLength());
462 const double fCurrentDeviation(fTools::equalZero(fControlPolygonLength) ? 0.0 : 1.0 - (fEdgeLength / fControlPolygonLength));
463
464 if(!nRecursionWatch || fTools:: lessOrEqual(fCurrentDeviation, fDeviation))
465 {
466 return (fEdgeLength + fControlPolygonLength) * 0.5;
467 }
468 else
469 {
470 B2DCubicBezier aLeft, aRight;
471 const double fNewDeviation(fDeviation * 0.5);
472 const sal_uInt32 nNewRecursionWatch(nRecursionWatch - 1);
473
474 rEdge.split(0.5, &aLeft, &aRight);
475
476 return impGetLength(aLeft, fNewDeviation, nNewRecursionWatch)
477 + impGetLength(aRight, fNewDeviation, nNewRecursionWatch);
478 }
479 }
480 }
481
482 double B2DCubicBezier::getLength(double fDeviation) const
483 {
484 if(isBezier())
485 {
486 if(fDeviation < 0.00000001)
487 {
488 fDeviation = 0.00000001;
489 }
490
491 return impGetLength(*this, fDeviation, 6);
492 }
493 else
494 {
495 return B2DVector(getEndPoint() - getStartPoint()).getLength();
496 }
497 }
498
499 double B2DCubicBezier::getEdgeLength() const
500 {
501 const B2DVector aEdge(maEndPoint - maStartPoint);
502 return aEdge.getLength();
503 }
504
505 double B2DCubicBezier::getControlPolygonLength() const
506 {
507 const B2DVector aVectorA(maControlPointA - maStartPoint);
508 const B2DVector aVectorB(maEndPoint - maControlPointB);
509
510 if(!aVectorA.equalZero() || !aVectorB.equalZero())
511 {
512 const B2DVector aTop(maControlPointB - maControlPointA);
513 return (aVectorA.getLength() + aVectorB.getLength() + aTop.getLength());
514 }
515 else
516 {
517 return getEdgeLength();
518 }
519 }
520
521 void B2DCubicBezier::adaptiveSubdivideByAngle(B2DPolygon& rTarget, double fAngleBound) const
522 {
523 if(isBezier())
524 {
525 // use support method #i37443# and allow unsharpen the criteria
526 ImpSubDivAngleStart(maStartPoint, maControlPointA, maControlPointB, maEndPoint, rTarget,
527 deg2rad(fAngleBound));
528 }
529 else
530 {
531 rTarget.append(getEndPoint());
532 }
533 }
534
535 B2DVector B2DCubicBezier::getTangent(double t) const
536 {
537 if(t <= 0.0)
538 {
539 // tangent in start point
540 B2DVector aTangent(getControlPointA() - getStartPoint());
541
542 if(!aTangent.equalZero())
543 {
544 return aTangent;
545 }
546
547 // start point and control vector are the same, fallback
548 // to implicit start vector to control point B
549 aTangent = (getControlPointB() - getStartPoint()) * 0.3;
550
551 if(!aTangent.equalZero())
552 {
553 return aTangent;
554 }
555
556 // not a bezier at all, return edge vector
557 return (getEndPoint() - getStartPoint()) * 0.3;
558 }
559 else if(fTools::moreOrEqual(t, 1.0))
560 {
561 // tangent in end point
562 B2DVector aTangent(getEndPoint() - getControlPointB());
563
564 if(!aTangent.equalZero())
565 {
566 return aTangent;
567 }
568
569 // end point and control vector are the same, fallback
570 // to implicit start vector from control point A
571 aTangent = (getEndPoint() - getControlPointA()) * 0.3;
572
573 if(!aTangent.equalZero())
574 {
575 return aTangent;
576 }
577
578 // not a bezier at all, return edge vector
579 return (getEndPoint() - getStartPoint()) * 0.3;
580 }
581 else
582 {
583 // t is in ]0.0 .. 1.0[. Split and extract
584 B2DCubicBezier aRight;
585 split(t, nullptr, &aRight);
586
587 return aRight.getControlPointA() - aRight.getStartPoint();
588 }
589 }
590
591 // #i37443# adaptive subdivide by nCount subdivisions
592 void B2DCubicBezier::adaptiveSubdivideByCount(B2DPolygon& rTarget, sal_uInt32 nCount) const
593 {
594 const double fLenFact(1.0 / static_cast< double >(nCount + 1));
595
596 for(sal_uInt32 a(1); a <= nCount; a++)
597 {
598 const double fPos(static_cast< double >(a) * fLenFact);
599 rTarget.append(interpolatePoint(fPos));
600 }
601
602 rTarget.append(getEndPoint());
603 }
604
605 // adaptive subdivide by distance
606 void B2DCubicBezier::adaptiveSubdivideByDistance(B2DPolygon& rTarget, double fDistanceBound, int nRecurseLimit) const
607 {
608 if(isBezier())
609 {
610 ImpSubDivDistance(maStartPoint, maControlPointA, maControlPointB, maEndPoint, rTarget,
611 fDistanceBound * fDistanceBound, std::numeric_limits<double>::max(), nRecurseLimit);
612 }
613 else
614 {
615 rTarget.append(getEndPoint());
616 }
617 }
618
619 B2DPoint B2DCubicBezier::interpolatePoint(double t) const
620 {
621 OSL_ENSURE(t >= 0.0 && t <= 1.0, "B2DCubicBezier::interpolatePoint: Access out of range (!)");
622
623 if(isBezier())
624 {
625 const B2DPoint aS1L(interpolate(maStartPoint, maControlPointA, t));
626 const B2DPoint aS1C(interpolate(maControlPointA, maControlPointB, t));
627 const B2DPoint aS1R(interpolate(maControlPointB, maEndPoint, t));
628 const B2DPoint aS2L(interpolate(aS1L, aS1C, t));
629 const B2DPoint aS2R(interpolate(aS1C, aS1R, t));
630
631 return interpolate(aS2L, aS2R, t);
632 }
633 else
634 {
635 return interpolate(maStartPoint, maEndPoint, t);
636 }
637 }
638
639 double B2DCubicBezier::getSmallestDistancePointToBezierSegment(const B2DPoint& rTestPoint, double& rCut) const
640 {
641 const sal_uInt32 nInitialDivisions(3);
642 B2DPolygon aInitialPolygon;
643
644 // as start make a fix division, creates nInitialDivisions + 2 points
645 aInitialPolygon.append(getStartPoint());
646 adaptiveSubdivideByCount(aInitialPolygon, nInitialDivisions);
647
648 // now look for the closest point
649 const sal_uInt32 nPointCount(aInitialPolygon.count());
650 B2DVector aVector(rTestPoint - aInitialPolygon.getB2DPoint(0));
651 double pointDistance(std::hypot(aVector.getX(), aVector.getY()));
652 double newPointDistance;
653 sal_uInt32 nSmallestIndex(0);
654
655 for(sal_uInt32 a(1); a < nPointCount; a++)
656 {
657 aVector = B2DVector(rTestPoint - aInitialPolygon.getB2DPoint(a));
658 newPointDistance = std::hypot(aVector.getX(), aVector.getY());
659 if(newPointDistance < pointDistance)
660 {
661 pointDistance = newPointDistance;
662 nSmallestIndex = a;
663 }
664 }
665
666 // look right and left for even smaller distances
667 double fStepValue(1.0 / static_cast<double>((nPointCount - 1) * 2)); // half the edge step width
668 double fPosition(static_cast<double>(nSmallestIndex) / static_cast<double>(nPointCount - 1));
669
670 while(true)
671 {
672 // test left
673 double fPosLeft(fPosition - fStepValue);
674
675 if(fPosLeft < 0.0)
676 {
677 fPosLeft = 0.0;
678 aVector = B2DVector(rTestPoint - maStartPoint);
679 }
680 else
681 {
682 aVector = B2DVector(rTestPoint - interpolatePoint(fPosLeft));
683 }
684
685 newPointDistance = std::hypot(aVector.getX(), aVector.getY());
686
687 if(fTools::less(newPointDistance, pointDistance))
688 {
689 pointDistance = newPointDistance;
690 fPosition = fPosLeft;
691 }
692 else
693 {
694 // test right
695 double fPosRight(fPosition + fStepValue);
696
697 if(fPosRight > 1.0)
698 {
699 fPosRight = 1.0;
700 aVector = B2DVector(rTestPoint - maEndPoint);
701 }
702 else
703 {
704 aVector = B2DVector(rTestPoint - interpolatePoint(fPosRight));
705 }
706
707 newPointDistance = std::hypot(aVector.getX(), aVector.getY());
708
709 if(fTools::less(newPointDistance, pointDistance))
710 {
711 pointDistance = newPointDistance;
712 fPosition = fPosRight;
713 }
714 else
715 {
716 // not less left or right, done
717 break;
718 }
719 }
720
721 if(fPosition == 0.0 || fPosition == 1.0)
722 {
723 // if we are completely left or right, we are done
724 break;
725 }
726
727 // prepare next step value
728 fStepValue /= 2.0;
729 }
730
731 rCut = fPosition;
732 return pointDistance;
733 }
734
735 void B2DCubicBezier::split(double t, B2DCubicBezier* pBezierA, B2DCubicBezier* pBezierB) const
736 {
737 OSL_ENSURE(t >= 0.0 && t <= 1.0, "B2DCubicBezier::split: Access out of range (!)");
738
739 if(!pBezierA && !pBezierB)
740 {
741 return;
742 }
743
744 if(isBezier())
745 {
746 const B2DPoint aS1L(interpolate(maStartPoint, maControlPointA, t));
747 const B2DPoint aS1C(interpolate(maControlPointA, maControlPointB, t));
748 const B2DPoint aS1R(interpolate(maControlPointB, maEndPoint, t));
749 const B2DPoint aS2L(interpolate(aS1L, aS1C, t));
750 const B2DPoint aS2R(interpolate(aS1C, aS1R, t));
751 const B2DPoint aS3C(interpolate(aS2L, aS2R, t));
752
753 if(pBezierA)
754 {
755 pBezierA->setStartPoint(maStartPoint);
756 pBezierA->setEndPoint(aS3C);
757 pBezierA->setControlPointA(aS1L);
758 pBezierA->setControlPointB(aS2L);
759 }
760
761 if(pBezierB)
762 {
763 pBezierB->setStartPoint(aS3C);
764 pBezierB->setEndPoint(maEndPoint);
765 pBezierB->setControlPointA(aS2R);
766 pBezierB->setControlPointB(aS1R);
767 }
768 }
769 else
770 {
771 const B2DPoint aSplit(interpolate(maStartPoint, maEndPoint, t));
772
773 if(pBezierA)
774 {
775 pBezierA->setStartPoint(maStartPoint);
776 pBezierA->setEndPoint(aSplit);
777 pBezierA->setControlPointA(maStartPoint);
778 pBezierA->setControlPointB(aSplit);
779 }
780
781 if(pBezierB)
782 {
783 pBezierB->setStartPoint(aSplit);
784 pBezierB->setEndPoint(maEndPoint);
785 pBezierB->setControlPointA(aSplit);
786 pBezierB->setControlPointB(maEndPoint);
787 }
788 }
789 }
790
791 B2DCubicBezier B2DCubicBezier::snippet(double fStart, double fEnd) const
792 {
793 B2DCubicBezier aRetval;
794
795 fStart = std::clamp(fStart, 0.0, 1.0);
796 fEnd = std::clamp(fEnd, 0.0, 1.0);
797
798 if(fEnd <= fStart)
799 {
800 // empty or NULL, create single point at center
801 const double fSplit((fEnd + fStart) * 0.5);
802 const B2DPoint aPoint(interpolate(getStartPoint(), getEndPoint(), fSplit));
803 aRetval.setStartPoint(aPoint);
804 aRetval.setEndPoint(aPoint);
805 aRetval.setControlPointA(aPoint);
806 aRetval.setControlPointB(aPoint);
807 }
808 else
809 {
810 if(isBezier())
811 {
812 // copy bezier; cut off right, then cut off left. Do not forget to
813 // adapt cut value when both cuts happen
814 const bool bEndIsOne(fTools::equal(fEnd, 1.0));
815 const bool bStartIsZero(fTools::equalZero(fStart));
816 aRetval = *this;
817
818 if(!bEndIsOne)
819 {
820 aRetval.split(fEnd, &aRetval, nullptr);
821
822 if(!bStartIsZero)
823 {
824 assert(fEnd != 0 && "help coverity see it's not zero");
825 fStart /= fEnd;
826 }
827 }
828
829 if(!bStartIsZero)
830 {
831 aRetval.split(fStart, nullptr, &aRetval);
832 }
833 }
834 else
835 {
836 // no bezier, create simple edge
837 const B2DPoint aPointA(interpolate(getStartPoint(), getEndPoint(), fStart));
838 const B2DPoint aPointB(interpolate(getStartPoint(), getEndPoint(), fEnd));
839 aRetval.setStartPoint(aPointA);
840 aRetval.setEndPoint(aPointB);
841 aRetval.setControlPointA(aPointA);
842 aRetval.setControlPointB(aPointB);
843 }
844 }
845
846 return aRetval;
847 }
848
849 B2DRange B2DCubicBezier::getRange() const
850 {
851 B2DRange aRetval(maStartPoint, maEndPoint);
852
853 aRetval.expand(maControlPointA);
854 aRetval.expand(maControlPointB);
855
856 return aRetval;
857 }
858
859 bool B2DCubicBezier::getMinimumExtremumPosition(double& rfResult) const
860 {
861 std::vector< double > aAllResults;
862
863 aAllResults.reserve(4);
864 getAllExtremumPositions(aAllResults);
865
866 const sal_uInt32 nCount(aAllResults.size());
867
868 if(!nCount)
869 {
870 return false;
871 }
872 else if(nCount == 1)
873 {
874 rfResult = aAllResults[0];
875 return true;
876 }
877 else
878 {
879 rfResult = *(std::min_element(aAllResults.begin(), aAllResults.end()));
880 return true;
881 }
882 }
883
884 namespace
885 {
886 void impCheckExtremumResult(double fCandidate, std::vector< double >& rResult)
887 {
888 // check for range ]0.0 .. 1.0[ with excluding 1.0 and 0.0 clearly
889 // by using the equalZero test, NOT ::more or ::less which will use the
890 // ApproxEqual() which is too exact here
891 if(fCandidate > 0.0 && !fTools::equalZero(fCandidate))
892 {
893 if(fCandidate < 1.0 && !fTools::equalZero(fCandidate - 1.0))
894 {
895 rResult.push_back(fCandidate);
896 }
897 }
898 }
899 }
900
901 void B2DCubicBezier::getAllExtremumPositions(std::vector< double >& rResults) const
902 {
903 rResults.clear();
904
905 // calculate the x-extrema parameters by zeroing first x-derivative
906 // of the cubic bezier's parametric formula, which results in a
907 // quadratic equation: dBezier/dt = t*t*fAX - 2*t*fBX + fCX
908 const B2DPoint aControlDiff( maControlPointA - maControlPointB );
909 double fCX = maControlPointA.getX() - maStartPoint.getX();
910 const double fBX = fCX + aControlDiff.getX();
911 const double fAX = 3 * aControlDiff.getX() + (maEndPoint.getX() - maStartPoint.getX());
912
913 if(fTools::equalZero(fCX))
914 {
915 // detect fCX equal zero and truncate to real zero value in that case
916 fCX = 0.0;
917 }
918
919 if( !fTools::equalZero(fAX) )
920 {
921 // derivative is polynomial of order 2 => use binomial formula
922 const double fD = fBX*fBX - fAX*fCX;
923 if( fD >= 0.0 )
924 {
925 const double fS = sqrt(fD);
926 // calculate both roots (avoiding a numerically unstable subtraction)
927 const double fQ = fBX + ((fBX >= 0) ? +fS : -fS);
928 impCheckExtremumResult(fQ / fAX, rResults);
929 if( !fTools::equalZero(fS) ) // ignore root multiplicity
930 impCheckExtremumResult(fCX / fQ, rResults);
931 }
932 }
933 else if( !fTools::equalZero(fBX) )
934 {
935 // derivative is polynomial of order 1 => one extrema
936 impCheckExtremumResult(fCX / (2 * fBX), rResults);
937 }
938
939 // calculate the y-extrema parameters by zeroing first y-derivative
940 double fCY = maControlPointA.getY() - maStartPoint.getY();
941 const double fBY = fCY + aControlDiff.getY();
942 const double fAY = 3 * aControlDiff.getY() + (maEndPoint.getY() - maStartPoint.getY());
943
944 if(fTools::equalZero(fCY))
945 {
946 // detect fCY equal zero and truncate to real zero value in that case
947 fCY = 0.0;
948 }
949
950 if( !fTools::equalZero(fAY) )
951 {
952 // derivative is polynomial of order 2 => use binomial formula
953 const double fD = fBY*fBY - fAY*fCY;
954 if( fD >= 0.0 )
955 {
956 const double fS = sqrt(fD);
957 // calculate both roots (avoiding a numerically unstable subtraction)
958 const double fQ = fBY + ((fBY >= 0) ? +fS : -fS);
959 impCheckExtremumResult(fQ / fAY, rResults);
960 if( !fTools::equalZero(fS) ) // ignore root multiplicity
961 impCheckExtremumResult(fCY / fQ, rResults);
962 }
963 }
964 else if( !fTools::equalZero(fBY) )
965 {
966 // derivative is polynomial of order 1 => one extrema
967 impCheckExtremumResult(fCY / (2 * fBY), rResults);
968 }
969 }
970
971 void B2DCubicBezier::transform(const basegfx::B2DHomMatrix& rMatrix)
972 {
973 if(rMatrix.isIdentity())
974 return;
975
976 if(maControlPointA == maStartPoint)
977 {
978 maControlPointA = maStartPoint = rMatrix * maStartPoint;
979 }
980 else
981 {
982 maStartPoint *= rMatrix;
983 maControlPointA *= rMatrix;
984 }
985
986 if(maControlPointB == maEndPoint)
987 {
988 maControlPointB = maEndPoint = rMatrix * maEndPoint;
989 }
990 else
991 {
992 maEndPoint *= rMatrix;
993 maControlPointB *= rMatrix;
994 }
995 }
996
997 void B2DCubicBezier::fround()
998 {
999 if(maControlPointA == maStartPoint)
1000 {
1001 maControlPointA = maStartPoint = basegfx::B2DPoint(
1002 std::round(maStartPoint.getX()),
1003 std::round(maStartPoint.getY()));
1004 }
1005 else
1006 {
1007 maStartPoint = basegfx::B2DPoint(
1008 std::round(maStartPoint.getX()),
1009 std::round(maStartPoint.getY()));
1010 maControlPointA = basegfx::B2DPoint(
1011 std::round(maControlPointA.getX()),
1012 std::round(maControlPointA.getY()));
1013 }
1014
1015 if(maControlPointB == maEndPoint)
1016 {
1017 maControlPointB = maEndPoint = basegfx::B2DPoint(
1018 std::round(maEndPoint.getX()),
1019 std::round(maEndPoint.getY()));
1020 }
1021 else
1022 {
1023 maEndPoint = basegfx::B2DPoint(
1024 std::round(maEndPoint.getX()),
1025 std::round(maEndPoint.getY()));
1026 maControlPointB = basegfx::B2DPoint(
1027 std::round(maControlPointB.getX()),
1028 std::round(maControlPointB.getY()));
1029 }
1030 }
1031 } // end of namespace basegfx
1032
1033 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */