## Etch-a-sketch curves

Thu 4 Aug 2011 by mskala Tags used: compsci, typographySuppose you want to draw a curve with an Etch-a-Sketch. The idea is that you can move the pointer up, down, left, or right, by a precisely controlled amount, but you aren't coordinated enough to turn both knobs at once in a precise way to create a diagonal or curved line. So you want to approximate your desired curve, with one made up of stair-steps; a piecewise linear curve made up of segments that each go in a direction chosen from a small finite set of directions (in this case, the four directions up, down, left, and right, but I'm interested in allowing any arbitrary small finite set of directions).

How can you do this so as to get the best possible approximation?

First we have to define what is the difference between a good and a bad approximation. There are a number of reasonable ways to do it; I'm going to be a bit vague and just say we'll parametrize both curves from zero to one in some appropriate way, and then take the integral of some sort of function of the distance between them as the parameter goes through its range. You can imagine that we have two ants, which both start at the starts of their respective curves at the same time, and both end up at the ends of their respective curves at some specific time in the future, and then we accumulate a "penalty" at all times in between based on how far apart they are at that moment, and we want to minimize the total penalty.

If the ants were smart enough to coordinate their movements (speeding up and slowing down) so as to minimize the total penalty, and if the penalty were equal to the longest distance we ever see between the ants (they are friendly ants and want to remain close to each other) then this would be the Fréchet distance. But calculating that is tricky because it requires planning out the ants' movements, and so we're probably going to use something a bit less intelligent and just do some sort of integral. The exact details aren't important; it is easy to think of and test a couple of definitions that will probably be good enough. There is one very important thing about fixing a parametrization and doing an integral: anywhere the desired and approximate curves intersect, we can cut them both in half. Then the optimal solution for the whole thing happens to consist of the optimal solutions for the two smaller problems, concatenated. (That's a big clue.)

If we are free to change direction whenever we want, then the solution is going to end up consisting of infinitely many infinitely small stair-steps that always stay right on top of the desired curve. But if we assume that we must also add on an extra penalty every time we change direction, then it becomes a much more interesting question: then it's necessary to balance "not too many direction changes" against "stay close to the curve" and it's not clear how to solve it efficiently. There seems to be a basically unlimited number of solutions possible. You have to choose a sequence of directions. Some of those sequences may make it impossible to get from the start to the end (for instance, up and then left, if the destination is to the right), but there may be any number that will work (up and then right; or up, right, up, right; or up, right, up, right, up...), and for each sequence of directions you also have to choose how long to make each step, from a real-number interval, and it's not clear how to optimize. If we just test all reasonable guesses we're heading for at least exponential time complexity.

I want to actually implement this, so I'm willing to make some further assumptions in the interest of being able to have an algorithm I can actually run. So let's first of all quantize the desired curve: it is now a sequence of closely spaced points, *n* of them. That's reasonable because I would probably end up doing it to compute the numerical integrals anyway. Let's also assume that the approximating curve intersects the desired curve not only at the start and end, but also at least once in between each change of direction. That seems at least sort of reasonable: it means the approximating curve is going to sort of zig-zag around the desired curve. (Though, to be clear, it could be tangent at some of these intersection points rather than actually *crossing*.) It seems like an optimal approximating curve would do this nearly all the time anyway, so requiring it should not be a problem.

Now we can think about this rationally in terms of smaller instances of the same problem. The basic problem is, how do you get from time 0 to time *t*, and end up in state (movement direction) number *i*, for minimum cost? Set *t* to the end of the curve, evaluate that for all *i*, and take the best answer, and you've answered the original problem. But if you have a way of solving it for smaller *t*, then you can call it recursively to get the answer for larger *t*. You just say, for each *t* smaller than the one you're currently looking at, and every *i*, recursively "What is the best way to get to that smaller *t* and that *i*, and then if I did that, could I get to the final *t* and *i* I'm looking at by extending the relevant directions forward and back until they intersect, and if I could, what would be the resulting overall cost?" Evaluate all those and find the best cost and you've got the best cost for the current subproblem.

Given *n* different values of *t* and *k* different values of *i*, it seems like we just invented an algorithm that is exponential with a branching factor on the order of *kn*, which is not good at all. The thing is, though, that there are only *O*(*kn*) of these subproblems. We could cache the answer to each one when we solve it, and then whenever we go to solve one, always check the cache first. This is just dynamic programming by memoization. (Doing it by memoization rather than just filling the table makes sense because there are some recursive calls we may be able to prune because of constraints between directions, obviating the need to actually compute those table entries.) The cache grows to *O*(*kn*) size, which is the number of subproblems; solving each subproblem costs *O*(*kn*) time, maybe multiplied by another *O*(*n*) for the cost of doing the integrals to evaluate the cost function; overall time is *O*(*k*^{2}*n*^{3}). That's within the range where we can reasonably execute it.

The actual motivation for this is an attempt to automatically generate black-letter type. The idea is that you have a curved letter form you'd like to write, but you're only allowed to move the pen at certain specific angles; and there may also be issues of stroke width, which can be incorporated into the cost function, so that at some points on the curve you might want the pen to be moving in a certain direction so that it will give you the stroke width you want. I haven't yet implemented it and I don't know how good the results will look, but I think it's worth trying.

4 comments

**Matt**- 2011-08-05 09:14

Your diagram reminded me of an early interest of mine - interpolation. This was very useful when we calculated charts using data at fixed intervals in the ephemeris, but it is still useful in many ways (inverse interpolation to find out when an aspect is exact, for instance). On the shelf next to where I am writing this stands the first publication I ever bought on the subject: Interpolation and Allied Tables Prepared by H. M. Nautical Almanac Office, London, 1956. I still use a homebrewed function based on four tabular points that was inspired by this booklet.

**Axel**- 2011-08-05 09:18

Part of what makes the line-width tricky is that although it *largely* comes from the mechanism you describe, holding the pen at a fixed angle and then the width of the line automatically changes depending on the angle of motion, I don't think it *all* comes from that in blackletter; I think scribes writing most blackletter styles would also change their pen angles in specific ways so that the line width changed according to more than just a simple function of the direction. In my algorithm I think I might actually end up with more than one vector in the same direction, corresponding to different widths of line, so that the system could choose the best of them.

**Matt**- 2011-08-06 10:29

kiwano- 2011-08-05 08:58