3 #include <unordered_map>
14 * Use dynamic programming / recursion
18 static unordered_map<int, int> dp;
19 static bool init = false;
28 int result = n*Factorial(n-1);
34 * Binomial coefficients
36 int BinomialCoeff(int n, int k)
38 return Factorial(n) / (Factorial(k) * Factorial(n-k));
42 * Bernstein Basis Polynomial
44 Real Bernstein(int k, int n, const Real & u)
46 return Real(BinomialCoeff(n, k)) * Power(u, k) * Power(Real(1.0) - u, n-k);
51 * Returns the parametric parameter at the turning point(s)
52 * In one coordinate direction
55 pair<Real, Real> BezierTurningPoints(const Real & p0, const Real & p1, const Real & p2, const Real & p3)
58 if (p1 == p2 && p2 == p3)
60 return pair<Real,Real>(0, 1);
62 Real a = (3*(p1-p2) + p3 - p0);
63 Real b = 2*(p2 - 2*p1 + p0);
68 return pair<Real, Real>(0,1);
72 return pair<Real, Real>(t, t);
74 //Debug("a, b, c are %f, %f, %f", Float(a), Float(b), Float(c));
77 //Debug("No real roots");
78 return pair<Real, Real>(0,1);
80 pair<Real, Real> tsols = SolveQuadratic(a, b, c);
81 if (tsols.first > 1) tsols.first = 1;
82 if (tsols.first < 0) tsols.first = 0;
83 if (tsols.second > 1) tsols.second = 1;
84 if (tsols.second < 0) tsols.second = 0;
88 inline bool CompRealByPtr(const Real * a, const Real * b)
94 * Get top most *point* on Bezier curve
96 pair<Real,Real> Bezier::GetTop() const
98 pair<Real, Real> tsols = BezierTurningPoints(y0,y1,y2,y3);
101 Evaluate(tx0, ty0, tsols.first);
102 Evaluate(tx1, ty1, tsols.second);
103 vector<const Real*> v(4);
108 sort(v.begin(), v.end(), CompRealByPtr);
109 pair<Real,Real> result;
110 result.second = *v[0];
115 else if (v[0] == &y3)
119 else if (v[0] == &ty0)
123 else if (v[0] == &ty1)
131 * Get bottom most *point* on Bezier curve
133 pair<Real,Real> Bezier::GetBottom() const
135 pair<Real, Real> tsols = BezierTurningPoints(y0,y1,y2,y3);
138 Evaluate(tx0, ty0, tsols.first);
139 Evaluate(tx1, ty1, tsols.second);
140 vector<const Real*> v(4);
145 sort(v.begin(), v.end(), CompRealByPtr);
146 pair<Real,Real> result;
147 result.second = *v[3];
152 else if (v[3] == &y3)
156 else if (v[3] == &ty0)
160 else if (v[3] == &ty1)
168 * Get left most *point* on Bezier curve
170 pair<Real,Real> Bezier::GetLeft() const
172 pair<Real, Real> tsols = BezierTurningPoints(x0,x1,x2,x3);
175 Evaluate(tx0, ty0, tsols.first);
176 Evaluate(tx1, ty1, tsols.second);
177 vector<const Real*> v(4);
182 sort(v.begin(), v.end(), CompRealByPtr);
183 pair<Real,Real> result;
184 result.first = *v[0];
189 else if (v[0] == &x3)
193 else if (v[0] == &tx0)
197 else if (v[0] == &tx1)
206 * Get left most *point* on Bezier curve
208 pair<Real,Real> Bezier::GetRight() const
210 pair<Real, Real> tsols = BezierTurningPoints(x0,x1,x2,x3);
213 Evaluate(tx0, ty0, tsols.first);
214 Evaluate(tx1, ty1, tsols.second);
215 vector<const Real*> v(4);
220 sort(v.begin(), v.end(), CompRealByPtr);
221 pair<Real,Real> result;
222 result.first = *v[3];
227 else if (v[3] == &x3)
231 else if (v[3] == &tx0)
235 else if (v[3] == &tx1)
243 * Get Bounds Rectangle of Bezier
245 Rect Bezier::SolveBounds() const
248 pair<Real, Real> tsols = BezierTurningPoints(x0, x1, x2, x3);
250 Real tp0; Real tp1; Real o;
251 Evaluate(tp0, o, tsols.first);
252 Evaluate(tp1, o, tsols.second);
254 //Debug("x: tp0 is %f tp1 is %f", Float(tp0), Float(tp1));
256 vector<const Real*> v(4);
262 // Not using a lambda to keep this compiling on cabellera
263 sort(v.begin(), v.end(), CompRealByPtr);
266 result.w = *(v[3]) - result.x;
268 // Do the same thing for y component (wow this is a mess)
269 tsols = BezierTurningPoints(y0, y1, y2, y3);
270 Evaluate(o, tp0, tsols.first);
271 Evaluate(o, tp1, tsols.second);
274 //Debug("y: tp0 is %f tp1 is %f", Float(tp0), Float(tp1));
280 sort(v.begin(), v.end(), CompRealByPtr);
283 result.h = *(v[3]) - result.y;
285 //Debug("Solved Bezier %s bounds as %s", Str().c_str(), result.Str().c_str());