From a set of polygons guaranteed to be :
- Full (no holes)
- Non-intersecting (polygons may share edges/points, but not penetrate each other)
How do I find the vertices of the Voronoi diagram where each polygon is a seed?
- Any answer for a Voronoi diagram of lines is also welcomed (I can merge the cells for lines belonging to the same polygon)
- I can work with an approximation of the vertices (within reasonable precision). This is for a simulated pathfinding / navigation system, so exact precision is appreciated but not mandatory.
- My math foundations are rusty, so please do mention anything obvious I should know / look into as an alternative.
I already have a working brute-force discretized approach :
- Draw each polygon in a unique color on an image
- For every blank pixel, find closest polygon and fill the pixel with its color
- List all pixels with adjacent to at least 2 different colors
While it works well enough (given a big enough image resolution) the performance is obviously horrible and it adds quite a few corner cases to handle. So I'd prefer to do without brute-forcing if possible.