0
$\begingroup$

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.

$\endgroup$

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.