A mathematical digression (revisited)

I received two working programs that attempted to solve my ellipse problem. Both were creditable attempts, but neither of them were quite accurate enough for my requirements. One had small (but visible) gaps between the first and last circle and the other didn’t work well for small or large n. However they made me think that a heuristic approach might be workable.

I made a couple of attempts to work out the quartic equations I would have to solve to find the solution analytically. But my brain started to bleed.

After much thinking about it I coded a heuristic approach myself in a day (till 3am!). It works from n=1 to n=100 for variable a/b without noticeable gaps or overlaps for n>7. There is some slight overlapping at n=7 and a/b=1.5. But I can fudge that by changing a/b to 1.6!

The approach is:

1. use Ramunajan’s formula to work back to a reasonable starting value for b (semi-minor axis)
2. lay out the n circles
3. work out the gap/overlap between the first and last circle
4. if gap/overlap error acceptable, stop, otherwise go to 2

There is also a bit of extra fudging for small n.

I used the secant method to interpolate the values for steps 1,2 and 4. As the functions were all smooth and well-behaved this converged on accurate answers very rapidly (typically 5 or 6 iterations per calculation).

Despite the fact that it is doing 2 levels of iterative calculation, it is surprisingly fast. Even going for high accuracy it takes <1ms for n=50 and <2ms for n=100 on my Windows box. About double that on my old Mac mini. And I can easily cache results in memory for more speed.

You can download and play with the test harness binaries here, if you are so inclined:

Windows binaries (Windows XP or Vista)

Mac binaries (MacOSX 10.3.9 or later)

Both Windows and Mac versions are created from a single set of C++ using the Qt cross-platform toolkit. Note that the timer resolution is 1ms, so times <1ms show as 0ms.

So the next version of my table planner software will have oval tables. As always, there was something I hadn’t though of. I had to do a bit of extra work to calculate the normal to the ellipse circumference (which isn’t the same as the line that joins the ellipse centre and the circumference – as I had initially assumed).

Without calculating normals.

With calculated normals

The commercial value of this feature probably isn’t worth the time I have spent on it. But it will make some of my customers very happy and it was an interesting problem. Part of the reason I set up as a microISV was to do things that I find interesting.

Many thanks to everyone that contributed code or suggestions to the original post.