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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.