Confused with Voronoi diagram algorithm (Fortune's sweepline)

algorithm computational-geometry voronoi
fireball003 picture fireball003 · Jun 11, 2009 · Viewed 9.6k times · Source

I am implementing Voronoi diagram to find out the nearest location in a map visually. Right now I want to do this using integer coordinates (x,y) only in a canvas.

Problem is- I am really confused about this algorithm. I read the Computational Geometry book, few more theory on Fortune's algorithm. And I am really confused now. It seems very complex to me when I am going for coding.

Please advice me very simple implementation of voronoi diagram (with given coordinates). Please advice me simple java or python or scheme code preferably without- hash, multi-threading, Delaunay Traingulation, fancy colors etc.

Isn't it possible to implement Voronoi diagram using Fortune's algorithm without multithreading or hash map?

Answer

bobobobo picture bobobobo · Jun 19, 2013

I opened a github repository with a port of Fortune's original paper. Fortune's implementation was very tough to follow mostly due to how he handled data structures.

This book appears a lot more modern

Fortune's original paper requires a few reads.

Ken Wong's paper describes the algorithm with arguably more clarity than Fortune in the original paper

Ken Wong's presentation has great slides (10, 11) on how to process a site and a vertex

There is an interactive JavaScript demo (Archived version) you can watch to help you visualize the algorithm.

A pdf describes the algorithm as well.

Steven Fortune's original implementation is on his homepage.

This Stony Brook site lists more implementations

Triangle is "A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator."

There is an entire book called "Spatial Tesselations Concepts and Applications of Voronoi Diagrams" by Atsuyuki Okabe, Barry Boots et al on Voronoi diagrams

Related questions

Algorithm to compute a Voronoi diagram on a sphere?

I'm looking for a simple (if exists) algorithm to find the Voronoi diagram for a set of points on the surface of a sphere. Source code would be great. I'm a Delphi man (yes, I know...), but I eat C-code …

Read More
Voronoi Tessellation in Python

Node Assignment Problem The problem I want to solve is to tessellate the map given with the Blue Nodes(Source Nodes) as given input points, Once I am able to do this I would like to see how many Black …

Read More
An algorithm for inflating/deflating (offsetting, buffering) polygons

How would I "inflate" a polygon? That is, I want to do something similar to this: The requirement is that the new (inflated) polygon's edges/points are all at the same constant distance from the old (original) polygon's (on the …

Read More