Article

# Fortune's Voronoi algorithm implemented in C#

, 21 Apr 2013
 Rate this:
A C# implementation of the Fortune algorithm to compute 2D Voronoi graphs.

## Introduction

Given a set of two dimensional vectors (or data points), a Voronoi graph is a separation of those points into compartments where all points inside one compartment are closer to the contained data point than to any other data point. I won't give any demonstration here, but if you want to know more about Voronoi graphs, check out this.

The applications of Voronoi graphs are quite broad. Very useful for a lot of optimization problems (in most cases, the Delaunay Triangulation which can be easily derived from a Vononoi graph is used there), it ranges to computing topological maps from bitmaps.

[This is an article for freaks. After a rather painful experience writing the thing I hope it will benefit everyone who is looking for this algorithm in a civilized language (or simply does not want to use Fortune's original C implementation).]

In 1987, Steve Fortune described an algorithm to compute such a graph by using a sweep line in combination with a binary tree. A PowerPoint explanation of the algorithm (the one I used to implement it) can be found here. Note that I did not use the linked data structure to represent a graph - I think that is an unnecessary difficulty in the age of `ArrayList`s and `HashSet`s.

## The Implementation

Data points are represented by my own `Vector` class. It can do much more than needed here (but there was no reason to strip it before bringing it) but I won't explain it here. The most important fact is that although working with `double`s the Vector class automatically rounds values to 10 digits (or whatever is set in the `Vector.Precision` field). Yes, sadly, this is very important if you want to sort of compare `double`s.

A `VoronoiGraph` is a class that only contains a `HashSet` of vertices (as 2D vectors) and a `HashSet` of `VoronoiEdge`s - each with references to the left and right data point and (of course) the two vertices that bound the edge. If the edge is (partially or completely) unbounded, the vector `Fortune.VVUnknown` is used.

`BinaryPriorityQueue` is used for the sweep line event queue.

## Usage

The algorithm itself (`Fortune.ComputeVoronoiGraph(IEnumerable)`) takes any `IEnumerable` containing only two dimensional vectors. It will return a `VoronoiGraph`. The algorithm's complexity is O(n ld(n)) with a factor of about 10 microseconds on my machine (2GHz).

## Share

Software Developer (Senior)
Germany
I did my diploma in Dresden and Sydney where I dealt with algorithms, agents and other cool AI stuff. Now I moved to Frankfurt to work on my PhD dealing with software structures for artificial intelligence systems. If I can, I do things in C# and ASP.NET, but if I have to, my C++, Java and SQL are not that bad.
Long Live .NET.

 First PrevNext
 Interesting Member 10838028 22-May-14 11:58
 divide and conquer . rizikandry 23-Jul-13 3:02
 Rounding error when creating circles for new nodes Bwd Yeti 19-Apr-13 0:50
 Re: Rounding error when creating circles for new nodes BenDi 21-Apr-13 6:56
 Don't know where to start [modified] Member 9989758 18-Apr-13 16:58
 My vote of 4 PehGuevara 7-Mar-13 21:40
 Getting regions from graph Bixel 6-Feb-13 14:14
 Re: Getting regions from graph BenDi 6-Feb-13 23:50
 Re: Getting regions from graph Bixel 7-Feb-13 12:06
 Possible issue. When I draw 2 points I haven't 2 area seb.49 30-May-12 23:59
 Re: Possible issue. When I draw 2 points I haven't 2 area BenDi 31-May-12 3:11
 Re: Possible issue. When I draw 2 points I haven't 2 area seb.49 31-May-12 4:44
 Re: Possible issue. When I draw 2 points I haven't 2 area BenDi 31-May-12 7:00
 Re: Possible issue. When I draw 2 points I haven't 2 area seb.49 31-May-12 9:53
 This code is shitted Member 8683705 14-May-12 4:42
 The provided code is absolutely shitted. Why if I change epsilon value it will stop working correctly??????????? What epsilon value should be used??? Why 1e-10???? Why not 1e-20???? Did you try it for big numbers, for example: 220034495, 883612293??????   It's really piece of S H I T and I've wasted so huge amount of time on this crap...
 Re: This code is shitted maamaamaa 29-Jun-13 5:42
 Any way to handle boundaries and holes? James Maeding 16-Dec-10 11:03
 Re: Any way to handle boundaries and holes? xinaesthetic 30-Sep-11 7:38
 My vote of 5 maurice.calvert 31-Aug-10 23:08
 Re: My vote of 5 Member 8683705 14-May-12 4:45
 Re: My vote of 5 maurice.calvert 14-May-12 5:32
 Re: My vote of 5 Member 8683705 14-May-12 21:38
 Re: My vote of 5 maurice.calvert 15-May-12 4:56
 Voronoi Cells C-Bl 27-Jul-09 23:08
 3 data points case SOAD_ 21-Jun-09 6:08
 Re: 3 data points case rhill-ca 26-Jun-09 6:45
 Another wrong vertex Sunil Terkar 11-May-09 2:04
 Re: Another wrong vertex BenDi 11-May-09 10:03
 Re: Another wrong vertex Sunil Terkar 12-May-09 0:37
 Re: Another wrong vertex Sunil Terkar 12-May-09 5:09
 Re: Another wrong vertex rhill-ca 26-Jun-09 6:34
 Short of one edge and one vertex Sunil Terkar 5-May-09 23:11
 Re: Short of one edge and one vertex rhill-ca 26-Jun-09 6:31
 medial axis led 16-Apr-09 9:38
 Thanks! Reconstructivism 30-Mar-09 2:48
 Rays Wayne Romer 22-Mar-09 20:55
 Re: Rays Reconstructivism 30-Mar-09 2:56
 Re: Rays BenDi 30-Mar-09 8:57
 Last Visit: 31-Dec-99 18:00     Last Update: 21-Aug-14 18:52 Refresh 123 Next »