13,259,847 members (50,107 online)
alternative version

Stats

298.2K views
50 bookmarked
Posted 10 Aug 2005

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

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

 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
 Re: Rays BenDi29-Apr-09 10:49 BenDi 29-Apr-09 10:49
 Ok, thanks. But what about the vertices. I made a simple polygon generator to test the algorithm and I saw that the location of the vertex for 3 points (i.e. a triangle) is sometimes out of the triangle. But it should be the center of the inscribed circle, shouldn't it ? VladovsoftSoftware products for fitness and health club management, storehouses, shops and barcode generation.
 Re: Rays BenDi30-Apr-09 9:04 BenDi 30-Apr-09 9:04
 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
 Re: Doubt BenDi8-Feb-07 10:39 BenDi 8-Feb-07 10:39
 Need help! lizc13-Aug-06 11:32 lizc 13-Aug-06 11:32
 What EULA this code has? Andrea N.11-Aug-06 11:38 Andrea N. 11-Aug-06 11:38
 Last Visit: 31-Dec-99 19:00     Last Update: 24-Nov-17 11:04 Refresh 123 Next »