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

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

 First PrevNext
 Interesting Member 10838028 22-May-14 11:58
 voronoy bad link Giovanni Cuccureddu 21-Sep-13 21:22
 divide and conquer . rizikandry 23-Jul-13 3:02
 Hi all!   I am thrilled and humbled by all the feedback I got for this project. I'm happy some people found it useful.   It is hard to overlook that the code was never polished from all the questions and change request, but since I can't fulfill all of these, I have   MOVED THE PROJECT to Google Code: https://code.google.com/p/fortune-voronoi/[^]   Feel free to submit Fixes, Comments, Refactorings, UIs, whatever you feel like!   If someone would like to help with the reviews, let me know.   Cheers,   Ben
 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
 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
 Thiessen Polygons SOAD_ 19-Jun-09 14:46
 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:13 Refresh 123 Next »

General    News    Suggestion    Question    Bug    Answer    Joke    Rant    Admin

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

| Advertise | Privacy | Mobile
Web01 | 2.8.140821.2 | Last Updated 22 Apr 2013
Article Copyright 2005 by BenDi