Re: [Inkscapedevel] Bezier mathematicians anyone ?
On 5/27/06, Justin Wikinator <touchmewithsynchronicpulses@...400...> wrote:
I'm guessing instead of plotting a huge amount of points I can just do a rougher plot and then increase the resolution in the area before the target to optimize.
I've been thinking about ways to improve accuracy since yesterday, and I have some better math for you. :)
Dividing the curve into line segments and finding their lengths will always give you an answer that is too low, since line segments will always take a shortcut around any curved portions. It would be more efficient to use the Calculus definition, since it takes curvature into account:
Integral( sqrt( dx/dt ^ 2 + dy/dt ^ 2 ), t )
If you have a point traveling along your spline, the dx/dt and dy/dt functions tell you the point's x and y velocity with respect to t. The formula for dx/dt is:
dx/dt = x0 * (3*(1t)^2) + x1 * (+3*(1t)^2  6*(1t)*t) + x2 * (3*t^2 + 6*(1t)*t) x3 * (+3*t^2)
Here, x0 and x3 are the endpoints, and x1 and x2 are the control points. The formula for dy/dt is the same. Combining these two functions using the Pythagorean theorem gives the absolute speed of a point traveling along the spline:
s(t) = sqrt( dx/dt ^ 2 + dy/dt ^ 2 )
In other words, the definition of arc length is just speed integrated by time, giving distance traveled. Since an integration just divides a function into infinitely small chunks and adds them up, it can be approximated with a sum:
double s = 0; //Result double dt = 0.01; //Step size for (double t = 0; t < 1; t += dt) { s += s(t) * dt; }
Using an infinitely small dt would give you exact integration, but computers can't do that. :) Using something called Simpson's rule, however, can improve the results dramatically with almost no extra work:
int n = 100; //Steps; must be even double t0 = 0; //Start value for t double t1 = 1; //End value for t double dt = (t1  t0) / n; //Step size double s = s(t0) + s(t1); //Result for (int i = 1; i < n; i += 2) { s += 4*s(t0 + i*dt) + 2*s(t0 + i*dt + dt); } s *= dt/3;
You can Google Simpson's rule for more info on the algorithm, but the accuracy improvements are substantial. Plus, this algorithm is actually faster than summing lengths of line segments.
William Swanson
William Swanson wrote:
Using an infinitely small dt would give you exact integration, but computers can't do that. :) Using something called Simpson's rule, however, can improve the results dramatically with almost no extra work:
IIRC "Add Nodes" uses an implementation of Simpson's rule. I also tried a few other methods, but Simpson's rule was for sure the fastest. I think njh would tell you that eliptic integrals will give a much better/faster approximation, but that math was way over my head.
Aaron Spike
participants (2)

Aaron Spike

William Swanson