Voronoi Diagrams

Some time ago I was looking for an algorithms that can generate a ‘map like’ like pictures –  e.g. tessellation of a plane into set of more or less random polygons.    I found Voronoi diagrams –   which give very nice pictures and have many useful properties.
Most common case of Voronoi diagram is known in  an Euclidean plane,   where we have a set of points (call seeds) then Voronoi  diagram splits the plane into areas – called Voronoi cells – around each seed,   where inside each area any point is closer to that seed then to any other.   Areas are then convex polygons (for Euclidean metric). This definition is best illustrated on the picture below – the Voronoi diagram for 100 random points in range 0-100 – Voronoi cells are marked by red lines, blue points are seeds:

voro-100

To play with Voronoi diagrams  we can use python – recent version of scipy  already contains function for calculating Voronoi diagram (see later).   But we can use duality of Voronoi diagram to Delaunay triangulation. Both scipy and matplotlib   contain   functions for Delaunay triangulation. From a given triangulation we can get Voronoi diagram, if we connect centers  of  circumcircles  of each triangle through edges of adjacent triangles.  Also there is a pure python implementation of Fortune algorithm available on web here.

Below is the code for calculation Voronoi diagram using Delaunay triangulation function in matplotlib and using numpy for numerical calculations:

I was inspired by code mentioned on first line comment,  I refactor  it to leverage numpy matrix computations and also added feature to limit diagram to a bounding box.

Pictures below illustrateshow Voronoi diagram is created from triangulation –   we have  a set of seed points (blue),   then Delaunay triangulation is calculated (yellow lines), for each triangle we calculate circumcircle  –   center of circle is green cross and circle itself is grey.   Finally we connect circle centers (red lines)  and for border triangles we create line from the circumcircle center in direction perpendicular to the outer triangle edge and line extends to infinity ( to bounding box boundary in our case).

As already said  there is also function scipy.spatial.Voronoi, which returns directly vertices and edges of Voronoi diagram. Generally this function is faster then our example above (app. 2 – 3 times) – below is code that also calculates missing edges (leading to infinity)  and  limits picture to a bounding box ( similar to previous example):

 

Voronoi diagrams have many different application , some of them in geography – for instance below is a map of Czech Republic, overlayed with Voronoi diagram, where seeds are breweries in that country.

breweries

One thought on “Voronoi Diagrams”

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">