Does the voronoi calculation handle shapes?

[eyal0]

For https://github.com/pcb2gcode/pcb2gcode, I need a voronoi calculation that can compute the voronoi regions of shapes, not just points. For example:

Currently this is done using libboost geometry. All the points of each polygon are added to the voronoi builder and then the voronoi diagram is built, similar to how GEOS would do it. libboost reports for each edge which point was the cause for the edge. It also reports the back-edge, which is the edge going the other direction and the point that caused it. By removing all edges that are separating points in the same shape, only the edges that separate voronoi shapes remain.

Can GEOS voronoi do this?

[dbaston]

GEOS does not provide the information in this way. The current best method in GEOS would be to use a point-and-polygon test to associate each point with a Voronoi cell, then dissolve the cells with coverage union. This may be inelegant but has been fast enough for real-time applications I've used it in.

Another alternative is https://github.com/libgeos/geos/pull/320

[eyal0]

So you check each polygon made by voronoi for which points it contains. And then you union all the polygons that belong to the same shape. Hmm, I guess that could work. If I get around to trying it, I'll compare performance and results with boost. I worry that all the point tests will take a long time.

I think that it will handle shapes inside shapes (like a circle inside a doughnut). We'll see how it goes.