15,395,360 members
Articles / Programming Languages / C#
Article
Posted 10 Aug 2005

417.7K views
51 bookmarked

# Fortune's Voronoi algorithm implemented in C#

Rate me:
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).

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

 A vector line is reversed ... plunkman31-Jul-08 9:51 plunkman 31-Jul-08 9:51
 Re: A vector line is reversed ... plunkman31-Jul-08 10:54 plunkman 31-Jul-08 10:54
 ... what a mess! [modified] Salvatore Previti9-Jun-08 6:29 Salvatore Previti 9-Jun-08 6:29
 problem Member 454520718-Apr-08 0:09 Member 4545207 18-Apr-08 0:09
 help please Member 454520717-Apr-08 12:32 Member 4545207 17-Apr-08 12:32
 Re: help please Member 454520717-Apr-08 13:01 Member 4545207 17-Apr-08 13:01
 sample yansike31-Mar-08 16:42 yansike 31-Mar-08 16:42
 error: wrong voronoi diagrams Morton14-Mar-08 2:42 Morton 14-Mar-08 2:42
 First of all many thanks for providing this implementation of Fortune's algorithm in c#. The code seems to be working fine on randomly created point sets. However I have tested the code on several point sets of real-world (geographical) data and many times incorrect Voronoi diagrams are the result. I don't know where the error lies but I can send you screenshots+data if you want, to show you the problem.
 Re: error: wrong voronoi diagrams BenDi14-Mar-08 3:53 BenDi 14-Mar-08 3:53
 Re: error: wrong voronoi diagrams Morton18-Mar-08 0:36 Morton 18-Mar-08 0:36
 Doubt CPMO8-Feb-07 6:58 CPMO 8-Feb-07 6:58
 Re: Doubt BenDi8-Feb-07 9:39 BenDi 8-Feb-07 9:39
 Need help! lizc13-Aug-06 10:32 lizc 13-Aug-06 10:32
 What EULA this code has? Andrea N.11-Aug-06 10:38 Andrea N. 11-Aug-06 10:38
 Re: What EULA this code has? BenDi11-Aug-06 11:06 BenDi 11-Aug-06 11:06
 Re: What EULA this code has? Andrea N.11-Aug-06 11:31 Andrea N. 11-Aug-06 11:31
 New Version [modified] BenDi18-May-06 8:11 BenDi 18-May-06 8:11
 Re: New Version AndreAtIvu18-May-06 23:16 AndreAtIvu 18-May-06 23:16
 Re: New Version Dimasina24-May-06 17:08 Dimasina 24-May-06 17:08
 Re: New Version [modified] BenDi26-May-06 6:37 BenDi 26-May-06 6:37
 Re: New Version Dimasina31-May-06 17:39 Dimasina 31-May-06 17:39
 Re: New Version ddb30-Mar-08 9:31 ddb 30-Mar-08 9:31
 Re: New Version BenDi1-Apr-08 11:11 BenDi 1-Apr-08 11:11
 Re: New Version ddb3-Apr-08 7:04 ddb 3-Apr-08 7:04
 Re: New Version ddb3-Apr-08 10:56 ddb 3-Apr-08 10:56
 Last Visit: 31-Dec-99 18:00     Last Update: 14-Aug-22 18:58 Refresh ᐊ Prev123456 Next ᐅ