Playing around with the vd-code has highlighted some problems. Using double-precision floating point numbers for coordinates, strange things start to appear when the coordinates are around 1E-6 or so. It's not possible to accurately compute the sign of the in-circle predicate (a 4x4 determinant) and the diagram update should instead be based on topological reasoning.
Category: OpenVoronoi
Delaunay Triangulation
The dual of the Voronoi diagram is the Delaunay triangulation. Here I've modified my earlier VD code to also output the dual (shown in red). If this can be developed further to do constrained Delaunay triangulations (arbitrary pockets with islands) then it will be useful for cutter-location surfaces in opencamlib.
The regular grid is, in the words of the GTS website, "a much more difficult test than it looks".
Voronoi diagram algorithm
Update: now seems to work for at least 10k generators:
and a zoom-in of the same picture:
One way to compute 2D offsets for toolpath generation is via the voronoi diagram. This video shows the first (somehow) working implementation of my code, which is based on papers by Sugihara and Iri. Their 1992 paper is here: http://dx.doi.org/10.1109/5.163412, then a longer 50-page paper from 1994 here: http://dx.doi.org/10.1142/S0218195994000124, and then there's a more general description of the topology-based approach from 1999 here 10.1007/3-540-46632-0_36, and from 2000 here: http://dx.doi.org/10.1007/s004530010002
The algorithm works by incrementally constructing the diagram while adding the point-generators one by one. This initial configuration is used at the beginning:
The diagram will be correct if new generator points are placed inside the orange circle (this way we avoid edges that extend to infinity). Once about 500 randomly chosen points are added the diagram looks like this:
Because of floating-point errors it gets harder to construct the correct diagram when more and more points are added. My code now crashes at slightly more than 500 generators (due to an assert() that fails, not a segfault - yay!). It boils down to calculating the sign of a 4-by-4 determinant, which due to floating-point error goes wrong at some point. That's why the Sugihara-Iri algorithm is based on strictly preserving the correct topology of the diagram, and in fact they show in their papers that their algorithm doesn't crash when a random error is added to the determinant-calculations, and it even works (in some sense) when the determinant calculation is completely replaced by a random number generator. Their 1992 paper constructs the diagram for one million generators using 32-bit float
numbers, while my naive attempt using double here crashes after 535 points... some work to do still then!
CAM toolpaths tend to be based on CAD-geometry in the form of lines, circular arcs, or spline-curves and such. One way forward is to think of a curve as a lot of closely spaced points along the curve. There are also papers which describe how to extend the algorithm for line and arc generators. See the 1996 paper by Imai. There is FORTRAN code for this by Imai over here (I haven't looked at it or tried compiling it...). Held et al. describe voronoi diagram generation for points and lines in 2001: http://dx.doi.org/10.1016/S0925-7721(01)00003-7 and for points, lines, and arcs in 2009 http://dx.doi.org/10.1016/j.cad.2008.08.004. This pic from the Held&Huber 2009 paper shows point, line, and arc generators in bold-black, the associated voronoi-diagram as solid lines, and offsets as grey lines.
Held has more pictures here: http://www.cosy.sbg.ac.at/~held/projects/pocket_off/pocket.html
Note how within one voronoi-region the offset is determined by the associated generator (a line, point, or arc). It's very easy to figure out the offset within one region: points and arcs have circular offsets, while lines have line offsets. The complete offset path is a result of connecting the offset from one region with the next region.