Re: [boost] [voronoi]medial axis

Subject: Re: [boost] [voronoi]medial axis
From: Louis Lavery (zen218432_at_[hidden])
Date: 2013-09-19 04:30:16

Hello Andrii,

On 16/09/13 21:32, Andrii Sydorchuk wrote:
> Hi Louis,
>
> Thanks for the explanation. Good to know that wire cutting is yet another
> application area for Voronoi diagrams.
> It's also not completely clear to me how tool paths retrieved from MAT are
> used for wire cutting machines.
> Will be great to read relevant article or any other reference.
>

Sorry, but I can't help you very much with articles, other than suggest 
google. I haven't come across any papers or articles that I've felt 
necessary to keep[1]. One name to include in your google is Martin Held, 
he's done some stuff on variable width offsetting (as apposed to fixed 
step/parallel offsetting).

In general (wire and milling) we use parallel offsetting to clear areas. 
I think in terms of a circle, not a mill or wire tool, and wrote a 
parallel offsetting program yonks ago. As you can probably guess, it's 
based on an algorithm that offsets a single closed curve and extracts 
the requisite offset curves from the offset. The offset curve can be 
quite complex in itself and we need to separate out the parts we want. I 
use winding numbers in my algorithm as once you've got them you've 
solved the problem in a general way, IYSWIM.

Anyway, that aside, if you look at the set of nested offsets of a given 
shape you can see the edges/legs (which are conics in general) of the 
shape's Medial Axis (MA). It's easier to see when the offsets are fairly 
close together. The edges/legs appear where the sharp corners of the 
offsets line up. For instance the MA of a square is 4 lines/legs, one 
from each corner, that meet at the centre. So you can, given the MAT of 
a square, invert the whole process and join up the points equidistant 
along each leg. You can do that for each distance you want to offset the 
square by in order to generate the set of nested offsets. Thus the MAT, 
in a way, represents all possible offsets of the square, or shape.

Having said that, I'm not that sure using the MAT in this manner is a 
good idea, it's certainly not the best use of it, in my opinion. As I 
said in an earlier post, I don't use or think in terms of the MAT 
directly. I think more in terms of the MAT's legs and the set of salient 
discs/circles (not sure if 'salient' is the best term to use, but it's 
the best I've been able to come up with :-)). Anyway, the salient discs 
have centres corresponding to the vertices of the MAT, and radius such 
that they graze the shape at n points, where n is the vertex's degree. 
My own idea is to use the set of salient discs to chop the shape up into 
a set of sausages, and to generate tool paths inside each sausage before 
joining them back together to create the final tool path for the shape.

This is all just ideas at the moment (although quite a bit of research 
has been carried out on the backs of beer mats) but I'm quite confident 
it's a good way to bridge the gap between the rather abstract structure 
of the MAT and the practical problem of area clearance. One warning 
though, I think in terms of Medial Axis Discs, so am working in 
namespace MAD :-)

Hope that gives you some idea of what I'm up to. I haven't a web site at 
the moment, that's something I need to do, and will let you know via 
this list if/when I get one going.

If any thing's not clear, or you want more detail, let me know.

Louis.

[1] I used keep it all, but decided that that's worse than keeping none. 
I now only keep what anything it inspires me. Even then I often throw it 
away later after revising it all.