Freesteel Blog » A bit more voronoi

A bit more voronoi

Wednesday, October 21st, 2015 at 9:09 am Written by:

I’ve been going hammer-and-tongs at this code for almost two weeks now. To prove it’s real, here it is. No one is ever going to lock this algorithm away again. This time it’s a public good.


Back in the 1990s I implemented M. Held’s algorithm twice as it was written up, first in his PhD thesis, and later in a CAD paper. He later developed a third implementation, which I didn’t implement.

This version is a totally different approach and has the potential for being fully robust no matter what.


The plan right now is to get only this particular input shape working properly — and I can spot a few bugs still there, damn! — so that I can make a toolpath to cut a stamp, which involves area clearing, chamfering and V-groove cutting. It’s got to push through.



That’s better.

Notwithstanding a lot of technical debt I should deal with while the code is fresh on my mind, this is ready to turn into some toolpaths. Unfortunately the big machine tool in the closet is unavailable due to meetings in the spare room, so I’ll be using the mini Proxxon tool to prove this algorithm.

And while I’m packaging this up into a fit state to be presented, I need to remind myself exactly why I’ve been suckered by the Not-Invented-Here force-field and avoided using the relevant CGAL package that’s freely available and fully optimized.

For the sake of reclaiming my time I have to find a way that this code exceeds it. But it won’t be in terms of speed and efficiency, that’s for sure.

Leave a comment

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <blockquote cite=""> <code> <em> <strong>