Hello Andrii, Thanks for the reply, and the link to the new (?) documentation. On 01/09/13 09:41, Andrii Sydorchuk wrote:

Hi Louis, [snip] The procedure is the following: 1) Instead of iterating over Voronoi edges, iterate over all Voronoi vertices. 2) For each Voronoi vertex check all Voronoi edges incident to it (in general case there should be 3 edges). For each such edge find the input point or segment located within the cell, that the edge belongs to. Check if all input object share a common endpoint. If yes, then the Voronoi vertex is located on the boundary, otherwise no. You can find more details on how to iterate over incident objects and Voronoi diagram topology here: http://www.boost.org/doc/libs/1_54_0/libs/polygon/doc/voronoi_diagram.htm

Yes, that's better than my idea, as it avoids comparing voronoi co-ords with user input points, so I don't need an epsilon.

Let me know if you have more questions.

After I've identified and marked the boundary vertices I need to identify and mark which vertices are outside and which are inside the shape. The shape is closed, but can have holes e.g. an annulus. I don't know if the following procedure is correct. Assume vertices on boundaries have been marked 1 and all others are 0. (1) Find an unmarked vertex and mark it and all unmarked vertices that can be reached from it via primary edges with 2. (2) Keep repeating (1) but mark vertices with 3,4,..., until all vertices are marked. (3) That identifies the separate areas, but I don't know which areas are outside, which are holes and which are inside. (4) If outside vertices (not in a hole) are always connected to an infinite vertex then I can use that fact to identify the outside area (and can deduce the others from that). So my question is, is each outside vertex connected to an infinite vertex via primary edges? [1] Thanks for your help, Louis [1] I assume inside vertices, and those in a hole, are not connected to an infinite vertex (via primary edges).

Hello Andrii, Sorry for being away so long, got caught up in other things. Anyway, I've a small change in what I need to do. All I require is to identify boundary vertices and inside vertices (not in a hole). However, to do that I still need to identify the outside vertices, AFAICS. I still identify and visit the boundary vertices using the method we've already discussed (that's working just fine). Here's what I'm now doing (cut and paste from the actual .cpp file) // Assume boundary vertices are visited and labeled as boundary. // // (6) We want to find the inside vertices (not in a hole). // (6.1) // The only sure way to do that, as far as I know, is to // visit and label each outside vertex. To do that we start // a bfs from the finite vertex of each primary infinite // edge, if that finite vertex is not already visited. // // (6.2) // Once we've visited, and labelled, these outside vertices // we find an edge (which may be secondary) incident to both // a boundary and an outside vertex, and rot_next about the // boundary end of that edge until we hit an unvisited vertex, // which we can be sure will happen(?). We then bfs from that // unvisited vertex to label inside vertices. // // (6.3) // Once we've done the above the only unvisited vertices will // be those in holes (and we could repeat something similar to // the above to label those hole vertices and discover any // holes within the holes, if we so wished). // // (6.4) // Note: the bfs searches along primary edges, it ignores // secondary edges. I'm pretty sure that should work okay, if I can assume rot_next about the boundary end of the edge will get me to an inside vertex, see '(?)' in the above (6.2) paragraph. I'm not sure what you mean by the following... On 02/09/13 21:19, Andrii Sydorchuk wrote:

1) Identify the outside area first by iterating from infinite edge; 2) Iterate over boundary vertices reachable from the infinite vertex and fill the inside area. Note: you might need to iterate over a few boundary vertices, because there won't be any primary Voronoi edges coming from the obtuse angles. As long as you use DFS or BFS for traversal with keeping the track of visited Voronoi edges, iterating over the outside boundary vertices won't change the complexity of the algorithm.

...regards obtuse angles. If my revised algorithm above will work, then I don't need to know what you mean (and am happy if that's the case). Thanks for your help, Louis.

Hello Andrii, On 14/09/13 21:49, Andrii Sydorchuk wrote:

Hi Louis,

The algorithm you've described should work! It will be great if you can share application area.

================================================================ I work in CAD/CAM, more the maths end than engineering. I'm writing a, templated, 2D medial axis transform (MAT). The input is any closed shape with zero or more holes. The input segments are arcs of circles. The final output is not the MAT, but a form more useful to an engineer. At the moment it (actually, an earlier non-robust version) is used for generating tool paths for 2 axis wire cutting machines (EDM), and we'll replace that with this robust version. We're also hoping to use the MAT for 4 axis wire cutting. I started out some time ago (longer than I'm willing to admit!) to write it, but have had the usual problems concerning robustness, so am using boost voronoi to get round that for now. I vector and integerise the input arcs before passing them to your voronoi builder. Once I've got the voronoi diagram I use it to build the MAT, which is essentially a graph with vertices that are tangental circles and edges that reference the original input arc segments. The graph's vertices are a subset of the voronoi's. If anything's not clear, or if you want more details, please let me know. Thanks again for you help, and for the voronoi diagram, Louis.

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.