search
Wednesday, 2018 February 28, 21:14 — curve-fitting

another problem with my clothoids

each curve hits alternate dots: first exactly, then with offsets pushing it toward the other curve.

I don’t think I’ve mentioned here how the offsets work.

Rather than considering the two coordinates of a point separately, I treat them as a complex number; this has huge notational conveniences.

The arc you see in my plots is a complex function of a real number. For the actual font, when I get around to making it, the outline will be the same function of a number whose imaginary part is ±½. (Curvature affects the thickness of the stroke, but by remarkably little: less than one part in twenty if the radius of curvature of the midline is 1.) So, to test whether or not a gridpoint is within the path, I find a complex number `t` such that `f(t)` is the desired point, and then compare `abs(t.imag)` to 0.5. (Secant method works well because the second derivative is not too big.)

The “offsets pushing it toward the other curve” are imaginary numbers: telling the path to miss each dot by a specified amount to one side or the other (halfway between the old `t.imag` and the new), rather than to hit any specified coordinates. I call the offset sway. What makes this approach compelling (to me) is the ease of applying it to miss white dots: if the path covers a gridpoint that it shouldn’t, I can add it to the sequence with a tag that says its sway must be more than half a unit, rather than specifying where the path must go to avoid it.

Now, for each iteration of the path, I estimate the length of each segment-arc (between two dots) and the angle at its midpoint, find the interpolating function for the angles, and then for each segment generate the Taylor series for the arc, find out how much `f(t[k+1]+i*sway[k+1])-f(t[k]+i*sway[k])` differs from `z[k+1]-z[k]`, and adjust the length and angle estimates accordingly for the next attempt.

But where sway is nonzero, the point where the segments meet on the midline – `f(t[k])` without sway – keeps changing as the angles change; and I suspect that may be why this fitting phase sometimes falls into an infinite loop, failing to converge to a solution.

If that is the cause, what can I do about it? Well, I could chuck the sway concept; I hate to do that, because it’s so darn convenient when it works.

It’s hard to say which is more frustrating: knowing it’s unlikely that anyone has ever tried something so weird, or (as in another project of mine) knowing that someone somewhere has probably done exactly what I need help with and I’m unlikely to find them.

• comment by Anton — Thursday, 2018 March 1, 12:56

On second thought, it shouldn’t matter whether adjacent segments meet on or off the real axis, so long as their meeting-point is well defined. More likely the flaw is in my correction formula, which is a dirty first approximation. The corrections to adjacent segments are not independent!

To avoid going into a loop of overshooting back and forth, each correction step is weighted by a random number between zero and one. (You’d think that randomness would cancel out some of whatever bias is in the approximation.) Maybe I ought to instead divide the correction by the iteration count.

• comment by Anton — Thursday, 2018 March 15, 09:21

I tried increasing “inertia” – the weight of the old estimate – by one whenever any of the errors is backward relative to the previous error, and resetting to 1 whenever none is backward. Didn’t help.

Also sometimes the arc-length grows unreasonably. I thought that might be because the Taylor series gets too long, but truncating it to 19 (terms beyond that are likely to be noise, because of the limit of floating point resolution) helped only a little.

• comment by Anton — Monday, 2018 June 11, 08:35

What needs scaling, I now think, is not Δt itself but the magnitude of Δt + i Δsway, where Δsway is constant. So I tried that, but kept getting a failure because Δsway is sometimes longer than the scaled hypoteneuse, making the new (Δt)² negative. Now what?!

Subscribe without commenting

RSS feed for comments on this post.