How can I find all connected edges of a voronoi vertex

[rsaccon]

Is there a way provided by the API on how I can find for each voronoi vertex the neighbouring vertices (so I can draw all connected edges for a specific vertex)

I know how to get all vertices but that alone does not help much.

I could iterate over all cells, for each cell iterator over all neighbouring cells and somehow track the vertices which belong to cell and neighbour cell and with a huge hash map somehow identify all neighbouring vertices for each vertex. But that seems not to be very efficient, there must be a smarter way !

[andreesteve]

If all you are trying to do is draw the entire voronoi cells, or even a subset of cells, this example may be of help on how to map it to 3d vertex buffers and triangle indexing.

However, I believe what you really want to do is to pick a specific common edge between two neighbor voronoi cells. Is that right?

If that is the case, I don't think we have the optimal solution for this yet in the library API. I can imagine we should extend the neighbor iterator to include also the common edge for ergonomics.

The optimal solution (I think) would be to have a mapping between the delaunay edge and the voronoi edge (they are dual after all). The delaunay edges can be easily found through EdgesAroundSiteIterator (looks this in internal) which is used to build the NeighborSiteIterator.

The workaround I can think of, until we get the edge mapping, is to get the two neighbor cells and search for the common edge. This is similar to what I tried to do here.

Let me know if this helps or if I misunderstood your question.

[rsaccon]

Thanks a lot for your answer. I am actually not looking for a common edge between two neighbor voronoi cells (but I probably still need to find it). I am looking for all edges joined at one specific voronoi vertex. Let me try to explain:

Imagine you want to create a physical representation of the voronoi diagram. Each voronoi vertex will represent what I will call a hub, each edge I will call a strut. Struts would be something like a tube from any material and to manufacture them I will need the length. For each hub, we already know its position, but to actually manufacture them we need to know the direction of each strut going out of that hub. Hope I am more clear now.

So this is how I think I could work around to get the edges around a voronoi vertex:

1. In a outer loop I iterate over all voronoi cells.
2. For each cell I iterate over neighbour sites. Now for every two sequential cells and the cell from 1. there is a common voronoi vertex we need to find (think this is trivial, just comparing vertices) and for each two of these three cells there is a common edge we need to find. I will try with the EdgesAroundSiteIterator (which I need to make public first). If I can get this working, than I guess my problem is solved. If you have a better idea on how to approach, please let me know.

[andreesteve]

I think I understood. I've been using voronoice mostly with 3d rendering, so it lacks other usage examples. I added a SVG generation example, which I think may help with what you need.

It will generate something like below, by explicitly listing each voronoi edge directly: start -> end, which gives the edge direction. If I understood right, this is what you are looking for. Please let me know if I got it right.

To get each voronoi edge, it iterates over each cell and then iterates over each sequential pair of cell vertices. Note the vertices are ordered counter-clockwise.

Because each edge is shared between 2 cells (unless the edge is in the hull), if you do this, you will print or list each edge twice, each time in the opposite direction. If for your application you cannot print/list it twice, you could keep a hashtable of the edges using the vertices as key and deduplicate that way.

Let me know if this helps.

[rsaccon]

Yes, you got it right and this helps a lot, thank you very much. I was not sure whether vertices obtained by iter_vertices() were ordered sequential (could not find it explicitly mentioned), but here you say it is, so this makes things easier. And yes, I need deduplication, that is easy to implement, thanks again.

[andreesteve]

Cool - I pushed some doc changes to explicitly document the ordering. Thanks.

[rsaccon]

One little problem left for my use case: is there a way to get from the cell vertex iterator the index that vertex has in the the main vertices list ? Reason I am asking: I want just store one Vec<Point> list, and for the edges I want just store its indexes.

[andreesteve]

Yes, you can use iter_triangles. It iterates over the indices of the delaunay triangles associated with the voronoi cell, which are the same as the indices of the voronoi cell's vertices (since the voronoi cell vertices are the circumcenters of the associated delaunay triangles).

Something like the pseudocode below:

let cell = voronoi.cell(my_cell_index);
let vertices: Vec<Point> = cell.iter_triangles().map(|t| voronoi.vertices()[t]).collect();

Also, if all you need is the list of indices to the vertices for a cell, you can just get it like this:

let vertex_indices: Vec<usize> = voronoi.cells()[my_cell_index];
let first_vertex: &Point = voronoi.vertices()[vertex_indices[0]];

[rsaccon]

Ah, yeah. Now all makes sense. Thanks a lot.