13,740,369 members
alternative version

#### Stats

344.3K views
50 bookmarked
Posted 10 Aug 2005
Licenced MPL

# Fortune's Voronoi algorithm implemented in C#

, 21 Apr 2013
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.

## You may also be interested in...

 First PrevNext
 Update license Vermillion Wizard15-Jul-18 5:30 Vermillion Wizard 15-Jul-18 5:30
 an error with fortune's sweepline 19-Dec-17 21:04 19-Dec-17 21:04
 The link has been invalid，would you send it to my e-mail Member 1194025111-Jul-16 6:28 Member 11940251 11-Jul-16 6:28
 Code exported to github for storing purposes, as google-code ceases to exist Bartosz Nowak10-Sep-15 9:41 Bartosz Nowak 10-Sep-15 9:41
 My vote of 5 Kristian Lindberg Vinther9-Jan-15 9:42 Kristian Lindberg Vinther 9-Jan-15 9:42
 Interesting 22-May-14 11:58 22-May-14 11:58
 Re: Interesting Kristian Lindberg Vinther5-Jan-15 4:32 Kristian Lindberg Vinther 5-Jan-15 4:32
 How to get a Polygon list asociated to seed Points marceloarguello70012-Jan-14 9:17 marceloarguello700 12-Jan-14 9:17
 Small example code would be very much appreciated pan05417-Dec-13 4:20 pan054 17-Dec-13 4:20
 divide and conquer . rizikandry23-Jul-13 3:02 rizikandry 23-Jul-13 3:02
 MESSAGE FROM THE OWNER: Help improve this project on Google Code! BenDi21-Apr-13 6:59 BenDi 21-Apr-13 6:59
 Rounding error when creating circles for new nodes Bwd Yeti19-Apr-13 0:50 Bwd Yeti 19-Apr-13 0:50
 Re: Rounding error when creating circles for new nodes BenDi21-Apr-13 6:56 BenDi 21-Apr-13 6:56
 Don't know where to start 18-Apr-13 16:58 18-Apr-13 16:58
 My vote of 4 PehGuevara7-Mar-13 21:40 PehGuevara 7-Mar-13 21:40
 Almost no comments in the code. Some things could be implemented in a nicer way. But the code is working fine.
 Getting regions from graph Bixel6-Feb-13 14:14 Bixel 6-Feb-13 14:14
 Re: Getting regions from graph BenDi6-Feb-13 23:50 BenDi 6-Feb-13 23:50
 Re: Getting regions from graph Bixel7-Feb-13 12:06 Bixel 7-Feb-13 12:06
 Separating braches of a medial axis sampled from inner voronoi points of a polygon 17-Jul-12 16:19 17-Jul-12 16:19
 Finding distance for VoronoiGraph vertizes representing Medial Axis of closed boundary 14-Jul-12 5:02 14-Jul-12 5:02
 Re: Finding distance for VoronoiGraph vertizes representing Medial Axis of closed boundary BenDi15-Jul-12 0:27 BenDi 15-Jul-12 0:27
 Re: Finding distance for VoronoiGraph vertizes representing Medial Axis of closed boundary Kenneth Haugland17-Jul-12 9:31 Kenneth Haugland 17-Jul-12 9:31
 Re: Finding distance for VoronoiGraph vertizes representing Medial Axis of closed boundary 17-Jul-12 16:11 17-Jul-12 16:11
 Is there a way to construct polygons from all the edges ? And how ? seb.493-Jun-12 21:36 seb.49 3-Jun-12 21:36
 Last Visit: 31-Dec-99 18:00     Last Update: 23-Oct-18 8:12 Refresh 123456 Next »