15,311,716 members
Articles / Programming Languages / C#
Article
Posted 10 Aug 2005

413.6K views
3.2K downloads
51 bookmarked

# Fortune's Voronoi algorithm implemented in C#

Rate me:
2.91/5 (30 votes)
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).

## License

This article, along with any associated source code and files, is licensed under The Mozilla Public License 1.1 (MPL 1.1)

## 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
 Re: Fortune's Voronoi algorithm implemented in C# BenDi13-Mar-06 21:29 BenDi 13-Mar-06 21:29
 Voronoi Cell's attributes Truong Pham Dang Khoa10-Mar-06 23:36 Truong Pham Dang Khoa 10-Mar-06 23:36
 Re: Voronoi Cell's attributes BenDi12-Mar-06 11:12 BenDi 12-Mar-06 11:12
 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
 I'm not sure how to draw a semi-unbounded edge. My first try was to find the midpoints of the two original vertices and draw an "infinite" line from VVertexA through this midpoint. Unfortunately, sometimes the edge should be drawn away from this midpoint rather than through it. So it would seem that in addition to knowing the two originating vertices and the node in the voronoi diagram I also need to know whether to draw the unbounded line *towards* the midpoint of the originating vertices or *away* from the midpoint. Is there some way of telling this that I'm just missing or is it really something that needs to be added? Thanks! Darrell Plank -- modified at 15:26 Tuesday 13th December, 2005
 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
 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: 26-May-22 0:53 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.