relax

This curve-fitting thingy is one of several projects on which I’ve made progress in rare fits over several years. It ran into two big snags. I haven’t found how to determine which gridpoints are within the pen-width of a blending arc; two methods that ought to work don’t. (What would help: tutoring in drawing pictures in a MacOS display, so that I might have a better idea where they go wrong. And a pony.)

The other snag is this: For each pair of arcs, there is an infinite family of blending arcs; how to choose the osculation points to minimize rapid changes in curvature, while meeting the gridpoint constraints?

I had long thought that the Right Way would be to start with a tight-fitting path and incrementally relax it, if only I could see how to do that. A recent sleepless night produced the germ of an answer.

A node’s principal fields are its coordinates in the plane, a tangent angle theta and a curvature kappa. Start with a node for each original dot, matching its coordinates exactly; its theta and kappa are taken from the circle that touches the dot and its two neighbors. Randomly choose a node and consider the blend-arc between its two neighbor nodes; if it fits the constraints and improves the smoothness function, replace the middle node with the arc’s nearest point to the original dot. Repeat.

If one circle fits the whole stroke (sequence of dots), then the above procedure will – I guess – usually converge to a circle, but is not obviously driven toward the best circle. So instead of fitting the input dots exactly, the nodes shall be compromises among those on the partial-fit circles that best fit the dots. Some segments of those circles are uncompromised at this stage (unless the stroke is a loop); though subject to replacement, their influence should persist and the final stroke should not deviate far from them, particularly at its endpoints.

This scheme can surely be improved. When the above procedure can no longer help, nodes should be inserted where theta is a multiple of π/4 (i.e. E/NE/N/NW/W/SW/S/SE) and other nodes – except endpoints! – removed. These extremal nodes can then be improved by shifting according to some other rule – which I may yet think up.