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

another problem with my clothoids

I wrote:

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. ( . . more . . )

Sunday, 2018 February 25, 09:57 — curve-fitting

clothoid weekend update

For context, see past posts in the curve-fitting category that I just created. To recap:

The curves I’ve been drawing are the paths made by a point moving at constant speed at an angle which is a piecewise quadratic function of path length. Curvature, the first derivative of angle, is continuous.

Such a path that hits a given sequence of dots is fully determined if it loops, but otherwise it has two degrees of freedom. For any angle and curvature at the starting dot, there is a quadratic coefficient that lets the path reach the next node, and likewise for the next.

My current code starts with an estimate for the length of each segment (between two dots) and the angle at its midpoint, and uses these basis functions to fit those angles: a constant, a linear function, and a family of “solitons”: piecewise quadratics, zero outside a sequence of four dots, discontinuous in the second derivative at each of those dots. For n segments, there are n-2 solitons, so the constant and linear functions are needed to consume the last two degrees of freedom.

Eventually I noticed a flaw in this scheme: the curvature of the resulting path is the same at both ends, namely the slope of the linear component, because the solitons contribute nothing to it. That’s appropriate for ā€˜Cā€™, but wrong for plenty of other strokes; in ā€˜Sā€™ the end curvatures ought to have opposite sign.

The next thing I’ll try is a least-squares quadratic fit to the whole sequence, then fit the residues with solitons as before. That should be an improvement but it’s not ideal; curvature is a local feature. Perhaps I’ll think of something better later.

Wednesday, 2018 February 14, 23:20 — curve-fitting

un-meander


Here, each curve hits alternate dots: first exactly (above), then with offsets pushing it toward the other curve. Below is the result of eight iterations.

With enough iterations, the top of ‘s’ eventually gets a more symmetrical arch, as the change in curvature is spread more evenly.

But many runs get stuck in the fitting phase, and I don’t yet know why. Attacking one likely flaw didn’t help.

Sunday, 2018 February 11, 11:14 — curve-fitting

meander

(Previously: 2014, 2011, 2010; also, less closely related, 2015)

I tried to smoothen a stroke by shifting each dot toward the Euler spiral (aka clothoid, aka Cornu spiral) determined by its four nearest neighbors. That didn’t work so well: small wiggles were removed, but big ones were magnified.

( . . more . . )

Sunday, 2015 December 20, 14:23 — curve-fitting

Scribbles: The Ensmoothening, Part II

One thing I noticed in that last series of charts is that more than one degree of discontinuity doesn’t help: the best-looking curves are mostly on the diagonal, where only the last nonzero derivative is discontinuous. Here, therefore, are those curves all together.

In column zero, the tangent angle is piecewise constant; in column one, it is a piecewise linear function of path length, resulting in six circular arcs; in column two it is piecewise quadratic, resulting in six clothoid arcs with continuous curvature; and so on.

Of course the arcs are approximated by cubics; to improve the match, I put a knot wherever any derivative crosses zero, as well as at the discontinuities. (See the knots.)

Sunday, 2015 December 6, 17:06 — curve-fitting

ensmoothening scribbles

Presented for your consideration: the somewhat disappointing results of an experiment in using piecewise polynomial spirals, of varying degrees of continuity, to fit the Takana — disappointing in that few if any of the curves are as pretty as I hoped.

I treat here only those that can be drawn with a single stroke. (The others can be built by combining subsets of these strokes.) In each chart, the degree of continuity increases downward, and the degree of the polynomials increases to the right.

A polynomial spiral is a curve whose tangent angle is a polynomial function of arc length; it has the form integral(exp(i*f(t))). (I implement it as a Taylor series.) In principle, f could be any real-valued function. If f is constant, you get a straight line; if f is linear (leftmost column in these small charts), you get a circle; if f is quadratic, you get an Euler spiral or Cornu spiral or clothoid, which is much used in railroads and highways to avoid sudden changes in lateral acceleration.

Here f is a least-squares fit to the step function which is the direction of the squared stroke. The top row of the chart shows continuity of degree zero: the component arcs meet, but that’s all; f is discontinuous. Degree one: the tangent angle is a continuous function of arc length. Degree two: the first derivative of tangent angle with respect to arc length, i.e. the curvature, is continuous. Degree n: the (n-1)th derivative of tangent angle, i.e. the (n-2)th derivative of curvature, is continuous.

Click each chart to extend it.

Later: I have come to a couple of conclusions. In most of these charts, the best entry to my eye is where f is piecewise quadratic with one continuous derivative. More than one degree of polynomial above the continuous degree adds little fidelity and detracts from beauty.

( . . more . . )

Saturday, 2014 May 10, 16:30 — curve-fitting, neep-neep

naming is hard

I often have trouble giving meaningful concise names to variables in the programs I write, perhaps because, until I reach for the keyboard, my thinking is largely nonverbal. I suspect that it would be less of a problem for someone more exposed to the accumulated lore of programmer culture; though perhaps not in this case:

I’m thinking of breaking up this process into multiple rounds, to obtain increasing degrees of geometric continuity. The initial nodes would coincide with the input dots but have no defined theta (tangent angle) or kappa (curvature); the first round of replacements determines theta for G¹ continuity, the next round determines kappa (the first derivative of theta) for G² continuity — and subsequent rounds may seek higher degrees of continuity by matching further derivatives.

This means that the node object, instead of exactly two fields called theta and kappa, should have a list of theta and its known derivatives (one more than the current replacement-round needs), and I’m at a loss for a good name for this list.

Next Page »