13,257,276 members (49,474 online)
alternative version

#### Stats

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

 First PrevNext
 The link has been invalid，would you send it to my e-mail Member 1194025111-Jul-16 7:28 Member 11940251 11-Jul-16 7:28
 Code exported to github for storing purposes, as google-code ceases to exist Bartosz Nowak10-Sep-15 10:41 Bartosz Nowak 10-Sep-15 10:41
 My vote of 5 Kristian Lindberg Vinther9-Jan-15 10:42 Kristian Lindberg Vinther 9-Jan-15 10:42
 Interesting Member 1083802822-May-14 12:58 Member 10838028 22-May-14 12:58
 Re: Interesting Kristian Vinther5-Jan-15 5:32 Kristian Vinther 5-Jan-15 5:32
 How to get a Polygon list asociated to seed Points marceloarguello70012-Jan-14 10:17 marceloarguello700 12-Jan-14 10:17
 Small example code would be very much appreciated pan05417-Dec-13 5:20 pan054 17-Dec-13 5:20
 divide and conquer . rizikandry23-Jul-13 4:02 rizikandry 23-Jul-13 4:02
 MESSAGE FROM THE OWNER: Help improve this project on Google Code! BenDi21-Apr-13 7:59 BenDi 21-Apr-13 7:59
 Rounding error when creating circles for new nodes Bwd Yeti19-Apr-13 1:50 Bwd Yeti 19-Apr-13 1:50
 Re: Rounding error when creating circles for new nodes BenDi21-Apr-13 7:56 BenDi 21-Apr-13 7:56
 Don't know where to start Member 998975818-Apr-13 17:58 Member 9989758 18-Apr-13 17:58
 My vote of 4 PehGuevara7-Mar-13 22:40 PehGuevara 7-Mar-13 22:40
 Getting regions from graph Bixel6-Feb-13 15:14 Bixel 6-Feb-13 15:14
 Re: Getting regions from graph BenDi7-Feb-13 0:50 BenDi 7-Feb-13 0:50
 Re: Getting regions from graph Bixel7-Feb-13 13:06 Bixel 7-Feb-13 13:06
 Separating braches of a medial axis sampled from inner voronoi points of a polygon Member 917583217-Jul-12 17:19 Member 9175832 17-Jul-12 17:19
 Finding distance for VoronoiGraph vertizes representing Medial Axis of closed boundary Member 917583214-Jul-12 6:02 Member 9175832 14-Jul-12 6:02
 I am attempting to use this Voronoi algorithm for medial axis computation of a closed boundary of lines, curves, or splines. I have sampled each boundary edge type to create a point at some distance value for a line or arc length of a curve. I then pass these set of points, which represent a filtered closed polygon of the boundary, into the ComputeVoronoiGraph function. I am returned VoronoiGraph vertizes that represent the sampled medial axis. One of the other challenges is that I would like to fit lines, arcs, or splines to the vertizes. But that is a different story... By definition a medial axis is represented as the center points of all inscribed circles that fit within the boundary, which is what I currently have. Although what I would like to also find is the radius of each of the vertizes (inscribed circle center points) that are returned from the ComputeVoronoiGraph function. Any pointers on how to accomplish this? Can I get this information from the algorithm somehow? My intention is to compute the medial axis and filter it similar to the Scale Axis Theorem
 Re: Finding distance for VoronoiGraph vertizes representing Medial Axis of closed boundary BenDi15-Jul-12 1:27 BenDi 15-Jul-12 1:27
 Re: Finding distance for VoronoiGraph vertizes representing Medial Axis of closed boundary Kenneth Haugland17-Jul-12 10:31 Kenneth Haugland 17-Jul-12 10:31
 Re: Finding distance for VoronoiGraph vertizes representing Medial Axis of closed boundary Member 917583217-Jul-12 17:11 Member 9175832 17-Jul-12 17:11
 Is there a way to construct polygons from all the edges ? And how ? seb.493-Jun-12 22:36 seb.49 3-Jun-12 22:36
 Possible issue. When I draw 2 points I haven't 2 area seb.4931-May-12 0:59 seb.49 31-May-12 0:59
 Re: Possible issue. When I draw 2 points I haven't 2 area BenDi31-May-12 4:11 BenDi 31-May-12 4:11
 Re: Possible issue. When I draw 2 points I haven't 2 area seb.4931-May-12 5:44 seb.49 31-May-12 5:44
 Re: Possible issue. When I draw 2 points I haven't 2 area BenDi31-May-12 8:00 BenDi 31-May-12 8:00
 Re: Possible issue. When I draw 2 points I haven't 2 area seb.4931-May-12 10:53 seb.49 31-May-12 10:53
 This code is shitted Member 868370514-May-12 5:42 Member 8683705 14-May-12 5:42
 Re: This code is shitted maamaamaa29-Jun-13 6:42 maamaamaa 29-Jun-13 6:42
 Any way to handle boundaries and holes? James Maeding16-Dec-10 12:03 James Maeding 16-Dec-10 12:03
 Re: Any way to handle boundaries and holes? xinaesthetic30-Sep-11 8:38 xinaesthetic 30-Sep-11 8:38
 My vote of 5 maurice.calvert1-Sep-10 0:08 maurice.calvert 1-Sep-10 0:08
 Re: My vote of 5 Member 868370514-May-12 5:45 Member 8683705 14-May-12 5:45
 Re: My vote of 5 maurice.calvert14-May-12 6:32 maurice.calvert 14-May-12 6:32
 Re: My vote of 5 Member 868370514-May-12 22:38 Member 8683705 14-May-12 22:38
 Re: My vote of 5 maurice.calvert15-May-12 5:56 maurice.calvert 15-May-12 5:56
 Voronoi Cells C-Bl28-Jul-09 0:08 C-Bl 28-Jul-09 0:08
 Re: 3 data points case rhill-ca26-Jun-09 7:45 rhill-ca 26-Jun-09 7:45
 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
 Last Visit: 31-Dec-99 19:00     Last Update: 23-Nov-17 3:21 Refresh 123 Next »