Serendipitous optimization

An implementation choice in stippler turned out to give near-optimal output for the milling machine

In stippler, the initial point distribution is done with a simple error-propagation algorithm that traverses the input pixels according to the hilbert curve. Then the points are repeatedly displaced using the method discussed in Adrian Secord's paper, with most points moving only a short distance from where they began. It just so happens that, on the input images I tested, this order is within 10% or so of the path found by my gopt software's first pass, and within 10% of the final path when only the second (uncrossing) step is run.

I can see some reasons to think that the Hilbert Curve would be a very good tour for points distributed on a grid---each step is exactly 1 unit, except for an extra travel from the last point back to the first point. I don't see exactly why it would yield a good tour for a sparsely-populated, randomly-offset grid, but it looks like this turns out to be the case.

Practical consequence? Somewhere between 6000 and 10000 points, the time to run gopt would exceed the time to mill the output. But it looks like that doesn't matter.

Entry first conceived on 24 March 2005, 15:44 UTC, last modified on 15 January 2012, 3:46 UTC
Website Copyright © 2004-2017 Jeff Epler