1 // SPDX-FileCopyrightText: 2009 Petr Gajdos <pgajdos@suse.cz> and
2 // Maurizio Paolini <paolini@dmf.unicatt.it>
3
4 // SPDX-License-Identifier: GPL-2.0-or-later
5
6 #include "bezier_imp.h"
7
8 #include "bogus_imp.h"
9 #include "line_imp.h"
10 #include "point_imp.h"
11 #include "polygon_imp.h"
12
13 #include "../misc/common.h"
14 #include "../misc/coordinate.h"
15 #include "../misc/kigpainter.h"
16 #include "../misc/kigtransform.h"
17
18 #include "../kig/kig_document.h"
19 #include "../kig/kig_view.h"
20
21 #include <cmath>
22 //#include <gsl/gsl_poly.h>
23
24 /*
25 * Polynomial Bézier Curve
26 */
27
BezierImp(const std::vector<Coordinate> & points)28 BezierImp::BezierImp( const std::vector<Coordinate>& points )
29 {
30 uint npoints = points.size();
31 Coordinate centerofmassn = Coordinate( 0, 0 );
32
33 for ( uint i = 0; i < npoints; ++i )
34 {
35 centerofmassn += points[i];
36 }
37 mpoints = points;
38 mcenterofmass = centerofmassn/npoints;
39 mnpoints = npoints;
40 }
41
~BezierImp()42 BezierImp::~BezierImp()
43 {
44 }
45
attachPoint() const46 Coordinate BezierImp::attachPoint() const
47 {
48 return mcenterofmass;
49 }
50
transform(const Transformation & t) const51 ObjectImp* BezierImp::transform( const Transformation& t ) const
52 {
53 /*
54 * To perform affine transformation of Bezier curve is the same as transform
55 * control points and then draw Bezier curve with this control points.
56 */
57 if ( ! t.isAffine() ) /* Don't know how to do it in general so far. */
58 {
59 return new InvalidImp;
60 }
61 std::vector<Coordinate> np;
62 for ( uint i = 0; i < mpoints.size(); ++i )
63 {
64 Coordinate nc = t.apply( mpoints[i] );
65 if ( !nc.valid() )
66 return new InvalidImp;
67 np.push_back( nc );
68 }
69 return new BezierImp( np );
70 }
71
draw(KigPainter & p) const72 void BezierImp::draw( KigPainter& p ) const
73 {
74 p.drawCurve( this );
75 }
76
inRect(const Rect & r,int width,const KigWidget & w) const77 bool BezierImp::inRect( const Rect& r, int width, const KigWidget& w ) const
78 {
79 bool ret = false;
80 uint reduceddim = mpoints.size() - 1;
81 for ( uint i = 0; !ret && i < reduceddim; ++i )
82 {
83 SegmentImp s( mpoints[i], mpoints[i+1] );
84 ret = lineInRect( r, mpoints[i], mpoints[i+1], width, &s, w );
85 }
86 if ( !ret )
87 {
88 SegmentImp s( mpoints[reduceddim], mpoints[0] );
89 ret = lineInRect( r, mpoints[reduceddim], mpoints[0], width, &s, w );
90 }
91
92 return ret;
93 }
94
valid() const95 bool BezierImp::valid() const
96 {
97 if (mnpoints > 1)
98 return true;
99 else
100 return false;
101 }
102
numberOfProperties() const103 int BezierImp::numberOfProperties() const
104 {
105 return Parent::numberOfProperties() + 3;
106 }
107
propertiesInternalNames() const108 const QByteArrayList BezierImp::propertiesInternalNames() const
109 {
110 QByteArrayList l = Parent::propertiesInternalNames();
111 l += "bezier-number-of-control-points";
112 l += "bezier-control-polygon";
113 l += "cartesian-equation"; //on purpose, this has the same name as in LocusImp!
114 assert( l.size() == BezierImp::numberOfProperties() );
115 return l;
116 }
117
properties() const118 const QByteArrayList BezierImp::properties() const
119 {
120 QByteArrayList l = Parent::properties();
121 l += I18N_NOOP( "Number of control points" );
122 l += I18N_NOOP( "Control polygon" );
123 l += I18N_NOOP( "Cartesian Equation" );
124 assert( l.size() == BezierImp::numberOfProperties() );
125 return l;
126 }
127
impRequirementForProperty(int which) const128 const ObjectImpType* BezierImp::impRequirementForProperty( int which ) const
129 {
130 if ( which < Parent::numberOfProperties() )
131 return Parent::impRequirementForProperty( which );
132 else return BezierImp::stype();
133 }
134
iconForProperty(int which) const135 const char* BezierImp::iconForProperty( int which ) const
136 {
137 assert( which < BezierImp::numberOfProperties() );
138 if ( which < Parent::numberOfProperties() )
139 return Parent::iconForProperty( which );
140 else if ( which == Parent::numberOfProperties() )
141 return "en"; // number of sides
142 else if ( which == Parent::numberOfProperties() + 1 )
143 return "controlpolygon";
144 else if ( which == Parent::numberOfProperties() + 2 )
145 return "kig_text";
146 else assert( false );
147 return "";
148 }
149
property(int which,const KigDocument & w) const150 ObjectImp* BezierImp::property( int which, const KigDocument& w ) const
151 {
152 assert( which < BezierImp::numberOfProperties() );
153 if ( which < Parent::numberOfProperties() )
154 return Parent::property( which, w );
155 else if ( which == Parent::numberOfProperties() )
156 {
157 // number of points
158 return new IntImp( mnpoints );
159 }
160 else if ( which == Parent::numberOfProperties() + 1 )
161 {
162 // control polygon
163 return new OpenPolygonalImp( mpoints );
164 }
165 else if ( which == Parent::numberOfProperties() + 2 )
166 {
167 // cartesian equation
168 return new StringImp( cartesianEquationString( w ) );
169 }
170 else assert( false );
171 return new InvalidImp;
172 }
173
points() const174 const std::vector<Coordinate> BezierImp::points() const
175 {
176 return mpoints;
177 }
178
npoints() const179 uint BezierImp::npoints() const
180 {
181 return mnpoints;
182 }
183
copy() const184 BezierImp* BezierImp::copy() const
185 {
186 return new BezierImp( mpoints );
187 }
188
visit(ObjectImpVisitor * vtor) const189 void BezierImp::visit( ObjectImpVisitor* vtor ) const
190 {
191 vtor->visit( this );
192 }
193
equals(const ObjectImp & rhs) const194 bool BezierImp::equals( const ObjectImp& rhs ) const
195 {
196 // that's actually sufficient condition for equality
197 // of Bks; there are many equal Bks with distinct
198 // control points
199 return rhs.inherits( BezierImp::stype() ) &&
200 static_cast<const BezierImp&>( rhs ).points() == mpoints;
201 }
202
stype()203 const ObjectImpType* BezierImp::stype()
204 {
205 static const ObjectImpType B(
206 Parent::stype(), "bezier",
207 I18N_NOOP( "Bézier Curve" ),
208 I18N_NOOP( "Select this Bézier Curve" ),
209 I18N_NOOP( "Select Bézier Curve %1" ),
210 I18N_NOOP( "Remove a Bézier Curve" ),
211 I18N_NOOP( "Add a Bézier Curve" ),
212 I18N_NOOP( "Move a Bézier Curve" ),
213 I18N_NOOP( "Attach to this Bézier Curve" ),
214 I18N_NOOP( "Show a Bézier Curve" ),
215 I18N_NOOP( "Hide a Bézier Curve" )
216 );
217
218 return &B;
219 }
220
stype2()221 const ObjectImpType* BezierImp::stype2()
222 {
223 static const ObjectImpType B3(
224 BezierImp::stype(), "bezier_quadratic",
225 I18N_NOOP( "Bézier Quadratic" ),
226 I18N_NOOP( "Select this Bézier Quadratic" ),
227 I18N_NOOP( "Select Bézier Quadratic %1" ),
228 I18N_NOOP( "Remove a Bézier Quadratic" ),
229 I18N_NOOP( "Add a Bézier Quadratic" ),
230 I18N_NOOP( "Move a Bézier Quadratic" ),
231 I18N_NOOP( "Attach to this Bézier Quadratic" ),
232 I18N_NOOP( "Show a Bézier Quadratic" ),
233 I18N_NOOP( "Hide a Bézier Quadratic" )
234 );
235
236 return &B3;
237 }
238
stype3()239 const ObjectImpType* BezierImp::stype3()
240 {
241 static const ObjectImpType B4(
242 BezierImp::stype(), "bezier_cubic",
243 I18N_NOOP( "Bézier Cubic" ),
244 I18N_NOOP( "Select this Bézier Cubic" ),
245 I18N_NOOP( "Select Bézier Cubic %1" ),
246 I18N_NOOP( "Remove a Bézier Cubic" ),
247 I18N_NOOP( "Add a Bézier Cubic" ),
248 I18N_NOOP( "Move a Bézier Cubic" ),
249 I18N_NOOP( "Attach to this Bézier Cubic" ),
250 I18N_NOOP( "Show a Bézier Cubic" ),
251 I18N_NOOP( "Hide a Bézier Cubic" )
252 );
253
254 return &B4;
255 }
256
type() const257 const ObjectImpType* BezierImp::type() const
258 {
259 uint n = mpoints.size();
260
261 if ( n == 3 ) return BezierImp::stype2();
262 if ( n == 4 ) return BezierImp::stype3();
263 return BezierImp::stype();
264 }
265
isPropertyDefinedOnOrThroughThisImp(int which) const266 bool BezierImp::isPropertyDefinedOnOrThroughThisImp( int which ) const
267 {
268 assert( which < BezierImp::numberOfProperties() );
269 if ( which < Parent::numberOfProperties() )
270 return Parent::isPropertyDefinedOnOrThroughThisImp( which );
271 return false;
272 }
273
surroundingRect() const274 Rect BezierImp::surroundingRect() const
275 {
276 Rect r( 0., 0., 0., 0. );
277 for ( uint i = 0; i < mpoints.size(); ++i )
278 {
279 r.setContains( mpoints[i] );
280 }
281 return r;
282 }
283
contains(const Coordinate & o,int width,const KigWidget & w) const284 bool BezierImp::contains( const Coordinate& o, int width, const KigWidget& w ) const
285 {
286 return internalContainsPoint( o, w.screenInfo().normalMiss( width ), w.document() );
287 }
288
containsPoint(const Coordinate & p,const KigDocument & doc) const289 bool BezierImp::containsPoint( const Coordinate& p, const KigDocument& doc ) const
290 {
291 return internalContainsPoint( p, test_threshold, doc );
292 }
293
internalContainsPoint(const Coordinate & p,double threshold,const KigDocument & doc) const294 bool BezierImp::internalContainsPoint( const Coordinate& p, double threshold, const KigDocument& doc ) const
295 {
296 double param = getParam( p, doc );
297 double dist = getDist( param, p, doc );
298 return fabs( dist ) <= threshold;
299 }
300
deCasteljau(unsigned int m,unsigned int k,double p) const301 Coordinate BezierImp::deCasteljau( unsigned int m, unsigned int k, double p ) const
302 {
303 if (m == 0) return mpoints[k];
304 assert( k + 1 <= mnpoints );
305 return (1 - p)*deCasteljau( m - 1, k, p ) + p*deCasteljau( m - 1, k + 1, p );
306 }
307
getPoint(double p,const KigDocument & doc) const308 const Coordinate BezierImp::getPoint( double p, const KigDocument& doc ) const
309 {
310 /*
311 * Algorithm de Casteljau
312 */
313 doc.mcachedparam = p;
314 return deCasteljau( mpoints.size() - 1, 0, p );
315 }
316
317 /*
318 * Rational Bézier Curve
319 */
320
RationalBezierImp(const std::vector<Coordinate> & points,const std::vector<double> & weights)321 RationalBezierImp::RationalBezierImp( const std::vector<Coordinate>& points, const std::vector<double>& weights )
322 {
323 uint npoints = points.size();
324 Coordinate centerofmassn = Coordinate( 0, 0 );
325 double totalweight = 0;
326
327 assert(points.size() == weights.size());
328
329 for ( uint i = 0; i < npoints; ++i )
330 {
331 centerofmassn += points[i];
332 totalweight += weights[i];
333 }
334 mpoints = points;
335 mweights = weights;
336 mcenterofmass = centerofmassn/totalweight;
337 mnpoints = npoints;
338 }
339
~RationalBezierImp()340 RationalBezierImp::~RationalBezierImp()
341 {
342 }
343
attachPoint() const344 Coordinate RationalBezierImp::attachPoint() const
345 {
346 return mcenterofmass;
347 }
348
transform(const Transformation & t) const349 ObjectImp* RationalBezierImp::transform( const Transformation& t ) const
350 {
351 /*
352 * To perform affine transformation of Bezier curve is the same as transform
353 * control points and then draw Bezier curve with this control points.
354 */
355 if ( ! t.isAffine() ) /* Don't know how to do it in general so far. */
356 {
357 return new InvalidImp;
358 }
359 std::vector<Coordinate> np;
360 for ( uint i = 0; i < mpoints.size(); ++i )
361 {
362 Coordinate nc = t.apply( mpoints[i] );
363 if ( !nc.valid() )
364 return new InvalidImp;
365 np.push_back( nc );
366 }
367 return new RationalBezierImp( np, mweights );
368 }
369
draw(KigPainter & p) const370 void RationalBezierImp::draw( KigPainter& p ) const
371 {
372 p.drawCurve( this );
373 }
374
inRect(const Rect & r,int width,const KigWidget & w) const375 bool RationalBezierImp::inRect( const Rect& r, int width, const KigWidget& w ) const
376 {
377 bool ret = false;
378 uint reduceddim = mpoints.size() - 1;
379 for ( uint i = 0; !ret && i < reduceddim; ++i )
380 {
381 SegmentImp s( mpoints[i], mpoints[i+1] );
382 ret = lineInRect( r, mpoints[i], mpoints[i+1], width, &s, w );
383 }
384 if ( !ret )
385 {
386 SegmentImp s( mpoints[reduceddim], mpoints[0] );
387 ret = lineInRect( r, mpoints[reduceddim], mpoints[0], width, &s, w );
388 }
389
390 return ret;
391 }
392
valid() const393 bool RationalBezierImp::valid() const
394 {
395 if (mnpoints > 1 && mnpoints == mweights.size())
396 return true;
397 else
398 return false;
399 }
400
numberOfProperties() const401 int RationalBezierImp::numberOfProperties() const
402 {
403 return Parent::numberOfProperties() + 3;
404 }
405
propertiesInternalNames() const406 const QByteArrayList RationalBezierImp::propertiesInternalNames() const
407 {
408 QByteArrayList l = Parent::propertiesInternalNames();
409 l += "bezier-number-of-control-points";
410 l += "bezier-control-polygon";
411 l += "cartesian-equation"; //on purpose, this has the same name as in LocusImp!
412 assert( l.size() == RationalBezierImp::numberOfProperties() );
413 return l;
414 }
415
properties() const416 const QByteArrayList RationalBezierImp::properties() const
417 {
418 QByteArrayList l = Parent::properties();
419 l += I18N_NOOP( "Number of control points" );
420 l += I18N_NOOP( "Control polygon" );
421 l += I18N_NOOP( "Cartesian Equation" );
422 assert( l.size() == RationalBezierImp::numberOfProperties() );
423 return l;
424 }
425
impRequirementForProperty(int which) const426 const ObjectImpType* RationalBezierImp::impRequirementForProperty( int which ) const
427 {
428 if ( which < Parent::numberOfProperties() )
429 return Parent::impRequirementForProperty( which );
430 else return RationalBezierImp::stype();
431 }
432
iconForProperty(int which) const433 const char* RationalBezierImp::iconForProperty( int which ) const
434 {
435 assert( which < RationalBezierImp::numberOfProperties() );
436 if ( which < Parent::numberOfProperties() )
437 return Parent::iconForProperty( which );
438 else if ( which == Parent::numberOfProperties() )
439 return "en"; // number of sides
440 else if ( which == Parent::numberOfProperties() + 1 )
441 return "controlpolygon";
442 else if ( which == Parent::numberOfProperties() + 2 )
443 return "kig_text";
444 else assert( false );
445 return "";
446 }
447
property(int which,const KigDocument & w) const448 ObjectImp* RationalBezierImp::property( int which, const KigDocument& w ) const
449 {
450 assert( which < RationalBezierImp::numberOfProperties() );
451 if ( which < Parent::numberOfProperties() )
452 return Parent::property( which, w );
453 else if ( which == Parent::numberOfProperties() )
454 {
455 // number of points
456 return new IntImp( mnpoints );
457 }
458 else if ( which == Parent::numberOfProperties() + 1 )
459 {
460 // control polygon
461 return new OpenPolygonalImp( mpoints );
462 }
463 else if ( which == Parent::numberOfProperties() + 2 )
464 {
465 // cartesian equation
466 return new StringImp( cartesianEquationString( w ) );
467 }
468 else assert( false );
469 return new InvalidImp;
470 }
471
points() const472 const std::vector<Coordinate> RationalBezierImp::points() const
473 {
474 return mpoints;
475 }
476
npoints() const477 uint RationalBezierImp::npoints() const
478 {
479 return mnpoints;
480 }
481
copy() const482 RationalBezierImp* RationalBezierImp::copy() const
483 {
484 return new RationalBezierImp( mpoints, mweights );
485 }
486
visit(ObjectImpVisitor * vtor) const487 void RationalBezierImp::visit( ObjectImpVisitor* vtor ) const
488 {
489 vtor->visit( this );
490 }
491
equals(const ObjectImp & rhs) const492 bool RationalBezierImp::equals( const ObjectImp& rhs ) const
493 {
494 // that's actually sufficient condition for equality of
495 // RBks; there are many RBks which don't have the same
496 // control points
497 return rhs.inherits( BezierImp::stype() ) &&
498 static_cast<const BezierImp&>( rhs ).points() == mpoints;
499 }
500
stype()501 const ObjectImpType* RationalBezierImp::stype()
502 {
503 static const ObjectImpType R(
504 Parent::stype(), "rational_bezier",
505 I18N_NOOP( "Rational Bézier Curve" ),
506 I18N_NOOP( "Select this Rational Bézier Curve" ),
507 I18N_NOOP( "Select Rational Bézier Curve %1" ),
508 I18N_NOOP( "Remove a Rational Bézier Curve" ),
509 I18N_NOOP( "Add a Rational Bézier Curve" ),
510 I18N_NOOP( "Move a Rational Bézier Curve" ),
511 I18N_NOOP( "Attach to this Rational Bézier Curve" ),
512 I18N_NOOP( "Show a Rational Bézier Curve" ),
513 I18N_NOOP( "Hide a Rational Bézier Curve" )
514 );
515
516 return &R;
517 }
518
stype2()519 const ObjectImpType* RationalBezierImp::stype2()
520 {
521 static const ObjectImpType R3(
522 BezierImp::stype(), "rational_bezier_quadratic",
523 I18N_NOOP( "Rational Bézier Quadratic" ),
524 I18N_NOOP( "Select this Rational Bézier Quadratic" ),
525 I18N_NOOP( "Select Rational Bézier Quadratic %1" ),
526 I18N_NOOP( "Remove a Rational Bézier Quadratic" ),
527 I18N_NOOP( "Add a Rational Bézier Quadratic" ),
528 I18N_NOOP( "Move a Rational Bézier Quadratic" ),
529 I18N_NOOP( "Attach to this Rational Bézier Quadratic" ),
530 I18N_NOOP( "Show a Rational Bézier Quadratic" ),
531 I18N_NOOP( "Hide a Rational Bézier Quadratic" )
532 );
533
534 return &R3;
535 }
536
stype3()537 const ObjectImpType* RationalBezierImp::stype3()
538 {
539 static const ObjectImpType R4(
540 BezierImp::stype(), "rational_bezier_cubic",
541 I18N_NOOP( "Rational Bézier Cubic" ),
542 I18N_NOOP( "Select this Rational Bézier Cubic" ),
543 I18N_NOOP( "Select Rational Bézier Cubic %1" ),
544 I18N_NOOP( "Remove a Rational Bézier Cubic" ),
545 I18N_NOOP( "Add a Rational Bézier Cubic" ),
546 I18N_NOOP( "Move a Rational Bézier Cubic" ),
547 I18N_NOOP( "Attach to this Rational Bézier Cubic" ),
548 I18N_NOOP( "Show a Rational Bézier Cubic" ),
549 I18N_NOOP( "Hide a Rational Bézier Cubic" )
550 );
551
552 return &R4;
553 }
554
type() const555 const ObjectImpType* RationalBezierImp::type() const
556 {
557 uint n = mpoints.size();
558
559 if ( n == 3 ) return RationalBezierImp::stype2();
560 if ( n == 4 ) return RationalBezierImp::stype3();
561 return RationalBezierImp::stype();
562 }
563
isPropertyDefinedOnOrThroughThisImp(int which) const564 bool RationalBezierImp::isPropertyDefinedOnOrThroughThisImp( int which ) const
565 {
566 assert( which < RationalBezierImp::numberOfProperties() );
567 if ( which < Parent::numberOfProperties() )
568 return Parent::isPropertyDefinedOnOrThroughThisImp( which );
569 return false;
570 }
571
surroundingRect() const572 Rect RationalBezierImp::surroundingRect() const
573 {
574 Rect r( 0., 0., 0., 0. );
575 for ( uint i = 0; i < mpoints.size(); ++i )
576 {
577 r.setContains( mpoints[i] );
578 }
579 return r;
580 }
581
contains(const Coordinate & o,int width,const KigWidget & w) const582 bool RationalBezierImp::contains( const Coordinate& o, int width, const KigWidget& w ) const
583 {
584 return internalContainsPoint( o, w.screenInfo().normalMiss( width ), w.document() );
585 }
586
containsPoint(const Coordinate & p,const KigDocument & doc) const587 bool RationalBezierImp::containsPoint( const Coordinate& p, const KigDocument& doc ) const
588 {
589 return internalContainsPoint( p, test_threshold, doc );
590 }
591
internalContainsPoint(const Coordinate & p,double threshold,const KigDocument & doc) const592 bool RationalBezierImp::internalContainsPoint( const Coordinate& p, double threshold, const KigDocument& doc ) const
593 {
594 double param = getParam( p, doc );
595 double dist = getDist( param, p, doc );
596 return fabs( dist ) <= threshold;
597 }
598
deCasteljauPoints(unsigned int m,unsigned int k,double p) const599 Coordinate RationalBezierImp::deCasteljauPoints( unsigned int m, unsigned int k, double p ) const
600 {
601 if (m == 0) return mpoints[k]*mweights[k];
602 assert( k + 1 <= mnpoints );
603 return (1 - p)*deCasteljauPoints( m - 1, k, p ) + p*deCasteljauPoints( m - 1, k + 1, p );
604 }
605
deCasteljauWeights(unsigned int m,unsigned int k,double p) const606 double RationalBezierImp::deCasteljauWeights( unsigned int m, unsigned int k, double p ) const
607 {
608 if (m == 0) return mweights[k];
609 assert( k + 1 <= mnpoints );
610 return (1 - p)*deCasteljauWeights( m - 1, k, p ) + p*deCasteljauWeights( m - 1, k + 1, p );
611 }
612
getPoint(double p,const KigDocument & doc) const613 const Coordinate RationalBezierImp::getPoint( double p, const KigDocument& doc ) const
614 {
615 /*
616 * Algorithm de Casteljau
617 */
618 doc.mcachedparam = p;
619 return deCasteljauPoints( mpoints.size() - 1, 0, p ) / deCasteljauWeights( mweights.size() - 1, 0, p );
620 }
621
622