15,307,206 members
Articles / Programming Languages / C#
Article
Posted 10 Aug 2005

413.4K views
51 bookmarked

# Fortune's Voronoi algorithm implemented in C#

Rate me:
21 Apr 2013MPL2 min read
A C# implementation of the Fortune algorithm to compute 2D Voronoi graphs.

NOTE: Code has moved to Google Code!

## 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).

## About the Author

 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.

## Comments and Discussions

 FirstPrev Next
 Wrong Diagram - What's the problem ? ramirob1-Feb-06 12:19 ramirob 1-Feb-06 12:19
 Re: Wrong Diagram - What's the problem ? BenDi1-Feb-06 22:09 BenDi 1-Feb-06 22:09
 Re: Wrong Diagram - What's the problem ? TomekS19-Mar-06 8:02 TomekS 19-Mar-06 8:02
 Re: Wrong Diagram - What's the problem ? BenDi20-Mar-06 10:16 BenDi 20-Mar-06 10:16
 Semi-unbounded edges darrellp13-Dec-05 9:24 darrellp 13-Dec-05 9:24
 Re: Semi-unbounded edges BenDi13-Dec-05 15:19 BenDi 13-Dec-05 15:19
 Re: Semi-unbounded edges darrellp13-Dec-05 18:40 darrellp 13-Dec-05 18:40
 Re: Semi-unbounded edges Dimasina4-May-06 5:26 Dimasina 4-May-06 5:26
 Hi BenDi, I guess there is a mistake in the code. I tried vector (1, 1),(2, 3),(5, 1) and got a result only 2 edges! I am shure, it should be 3 edges. I suppose the problem is Y coordinate of first point is equal of Y coordinate of therd point. When I changed (5,1)->(5,1.1) I got a correct result – 3 edges. Dim. -- modified at 11:28 Thursday 4th May, 2006
 Re: Semi-unbounded edges adamjcoon7-Dec-09 8:30 adamjcoon 7-Dec-09 8:30
 Source file link defective fwsouthern10-Aug-05 17:50 fwsouthern 10-Aug-05 17:50
 Re: Source file link defective BenDi10-Aug-05 19:28 BenDi 10-Aug-05 19:28
 Re: Source file link defective AndreAtIvu18-May-06 7:22 AndreAtIvu 18-May-06 7:22
 Last Visit: 31-Dec-99 18:00     Last Update: 22-May-22 16:59 Refresh ᐊ Prev123456

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.