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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.