# Find vertices of a Voronoi diagram of convex polygons

From a set of polygons guaranteed to be :

• Convex
• 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?

Precisions :

• 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 :

1. Draw each polygon in a unique color on an image
2. For every blank pixel, find closest polygon and fill the pixel with its color
3. 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.