11,432,427 members (62,275 online)

# Fortune's Voronoi algorithm implemented in C#

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

 Re: 3 data points case rhill-ca26-Jun-09 7:45 rhill-ca 26-Jun-09 7:45
 Thiessen Polygons SOAD_19-Jun-09 15:46 SOAD_ 19-Jun-09 15:46
 Another wrong vertex Sunil Terkar11-May-09 3:04 Sunil Terkar 11-May-09 3:04
 Re: Another wrong vertex BenDi11-May-09 11:03 BenDi 11-May-09 11:03
 Re: Another wrong vertex Sunil Terkar12-May-09 1:37 Sunil Terkar 12-May-09 1:37
 Re: Another wrong vertex Sunil Terkar12-May-09 6:09 Sunil Terkar 12-May-09 6:09
 Re: Another wrong vertex rhill-ca26-Jun-09 7:34 rhill-ca 26-Jun-09 7:34
 Short of one edge and one vertex Sunil Terkar6-May-09 0:11 Sunil Terkar 6-May-09 0:11
 Re: Short of one edge and one vertex rhill-ca26-Jun-09 7:31 rhill-ca 26-Jun-09 7:31
 medial axis led16-Apr-09 10:38 led 16-Apr-09 10:38
 Thanks! Reconstructivism30-Mar-09 3:48 Reconstructivism 30-Mar-09 3:48
 Rays Wayne Romer22-Mar-09 21:55 Wayne Romer 22-Mar-09 21:55
 Re: Rays Reconstructivism30-Mar-09 3:56 Reconstructivism 30-Mar-09 3:56
 Re: Rays BenDi30-Mar-09 9:57 BenDi 30-Mar-09 9:57
 Hi! For (partly) infinite edges I provided two properties do make drawing easier: FixedPoint and DirectionVector. FixedPoint is either the (one) Vertex that exists or the middle between the two data points. DirectionVector is orthogonal to the connecting line between the data points (this is a property of all voronoi edges). The secret to getting the direction of an infinite edge is in the voronoi algorithm itself - it provides edges with 'left' and 'right' data points. This gives a direct way to calculating the direction from the vertex. It goes in the direction where LeftData is left and RightData is right. Simple Cheers, Ben
 Re: Rays Pavel Vladov29-Apr-09 1:54 Pavel Vladov 29-Apr-09 1:54
 Re: Rays BenDi29-Apr-09 10:49 BenDi 29-Apr-09 10:49
 Re: Rays Pavel Vladov30-Apr-09 0:39 Pavel Vladov 30-Apr-09 0:39
 Re: Rays BenDi30-Apr-09 9:04 BenDi 30-Apr-09 9:04
 Re: Rays Pavel Vladov30-Apr-09 23:36 Pavel Vladov 30-Apr-09 23:36
 Re: Rays Slagh14-May-09 23:10 Slagh 14-May-09 23:10
 Re: Rays BenDi16-May-09 3:15 BenDi 16-May-09 3:15
 Re: Rays Slagh21-May-09 20:54 Slagh 21-May-09 20:54
 Re: Rays PehGuevara27-Feb-13 5:15 PehGuevara 27-Feb-13 5:15
 Re: Rays BenDi27-Feb-13 22:53 BenDi 27-Feb-13 22:53
 Re: Rays PehGuevara27-Feb-13 23:32 PehGuevara 27-Feb-13 23:32
 Re: Rays BenDi2-Mar-13 9:28 BenDi 2-Mar-13 9:28
 Re: Rays PehGuevara6-Mar-13 0:59 PehGuevara 6-Mar-13 0:59
 Re: Rays BenDi6-Mar-13 1:16 BenDi 6-Mar-13 1:16
 Re: Rays PehGuevara7-Mar-13 7:44 PehGuevara 7-Mar-13 7:44
 Re: Rays Ray Hidayat7-Jun-11 19:06 Ray Hidayat 7-Jun-11 19:06
 Re: Rays ckaut30-Jan-10 5:20 ckaut 30-Jan-10 5:20
 How to use Fortune.ComputeVoronoiGraph function Sunil Terkar3-Mar-09 5:20 Sunil Terkar 3-Mar-09 5:20
 Re: How to use Fortune.ComputeVoronoiGraph function Wayne Romer22-Mar-09 21:56 Wayne Romer 22-Mar-09 21:56
 use with sharpmap agelospanagiotakis15-Feb-09 0:51 agelospanagiotakis 15-Feb-09 0:51
 Re: use with sharpmap BenDi30-Mar-09 9:58 BenDi 30-Mar-09 9:58
 problem mabrouki2331-Dec-08 6:03 mabrouki23 31-Dec-08 6:03
 Visualization. Maxim_Barsuk17-Nov-08 23:05 Maxim_Barsuk 17-Nov-08 23:05
 Data points to Polygons Zanele Mkhize3-Sep-08 4:25 Zanele Mkhize 3-Sep-08 4:25
 Re: Data points to Polygons BenDi3-Sep-08 5:46 BenDi 3-Sep-08 5:46
 A vector line is reversed ... plunkman31-Jul-08 10:51 plunkman 31-Jul-08 10:51
 Re: A vector line is reversed ... plunkman31-Jul-08 11:54 plunkman 31-Jul-08 11:54
 ... what a mess! [modified] NeoGeek9-Jun-08 7:29 NeoGeek 9-Jun-08 7:29
 problem Member 454520718-Apr-08 1:09 Member 4545207 18-Apr-08 1:09
 help please Member 454520717-Apr-08 13:32 Member 4545207 17-Apr-08 13:32
 Re: help please Member 454520717-Apr-08 14:01 Member 4545207 17-Apr-08 14:01
 sample yansike31-Mar-08 17:42 yansike 31-Mar-08 17:42
 error: wrong voronoi diagrams Morton14-Mar-08 3:42 Morton 14-Mar-08 3:42
 Re: error: wrong voronoi diagrams BenDi14-Mar-08 4:53 BenDi 14-Mar-08 4:53
 Re: error: wrong voronoi diagrams Morton18-Mar-08 1:36 Morton 18-Mar-08 1:36
 Doubt CPMO8-Feb-07 7:58 CPMO 8-Feb-07 7:58
 Last Visit: 31-Dec-99 19:00     Last Update: 4-May-15 18:03 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.