Click here to Skip to main content
13,049,684 members (64,514 online)
Click here to Skip to main content
Add your own
alternative version


50 bookmarked
Posted 10 Aug 2005

Fortune's Voronoi algorithm implemented in C#

, 21 Apr 2013
Rate this:
Please Sign up or sign in to vote.
A C# implementation of the Fortune algorithm to compute 2D Voronoi graphs.


NOTE: Code has moved to Google Code! 


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 ArrayLists and HashSets.

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

A VoronoiGraph is a class that only contains a HashSet of vertices (as 2D vectors) and a HashSet of VoronoiEdges - 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.


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


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

Comments and Discussions

QuestionThe link has been invalid,would you send it to my e-mail Pin
Member 1194025111-Jul-16 6:28
memberMember 1194025111-Jul-16 6:28 
QuestionCode exported to github for storing purposes, as google-code ceases to exist Pin
Bartosz Nowak10-Sep-15 9:41
memberBartosz Nowak10-Sep-15 9:41 
GeneralMy vote of 5 Pin
Kristian Lindberg Vinther9-Jan-15 9:42
professionalKristian Lindberg Vinther9-Jan-15 9:42 
QuestionInteresting Pin
Member 1083802822-May-14 11:58
memberMember 1083802822-May-14 11:58 
AnswerRe: Interesting Pin
Kristian Vinther5-Jan-15 4:32
memberKristian Vinther5-Jan-15 4:32 
QuestionHow to get a Polygon list asociated to seed Points Pin
marceloarguello70012-Jan-14 9:17
membermarceloarguello70012-Jan-14 9:17 
QuestionSmall example code would be very much appreciated Pin
pan05417-Dec-13 4:20
memberpan05417-Dec-13 4:20 
Questionvoronoy bad link Pin
Giovanni Cuccureddu21-Sep-13 21:22
memberGiovanni Cuccureddu21-Sep-13 21:22 
Questiondivide and conquer . Pin
rizikandry23-Jul-13 3:02
memberrizikandry23-Jul-13 3:02 
QuestionMESSAGE FROM THE OWNER: Help improve this project on Google Code! Pin
BenDi21-Apr-13 6:59
memberBenDi21-Apr-13 6:59 
QuestionRounding error when creating circles for new nodes Pin
Bwd Yeti19-Apr-13 0:50
memberBwd Yeti19-Apr-13 0:50 
AnswerRe: Rounding error when creating circles for new nodes Pin
BenDi21-Apr-13 6:56
memberBenDi21-Apr-13 6:56 
QuestionDon't know where to start Pin
Member 998975818-Apr-13 16:58
memberMember 998975818-Apr-13 16:58 
GeneralMy vote of 4 Pin
PehGuevara7-Mar-13 21:40
memberPehGuevara7-Mar-13 21:40 
QuestionGetting regions from graph Pin
Bixel6-Feb-13 14:14
memberBixel6-Feb-13 14:14 
AnswerRe: Getting regions from graph Pin
BenDi6-Feb-13 23:50
memberBenDi6-Feb-13 23:50 
GeneralRe: Getting regions from graph Pin
Bixel7-Feb-13 12:06
memberBixel7-Feb-13 12:06 
QuestionSeparating braches of a medial axis sampled from inner voronoi points of a polygon Pin
Member 917583217-Jul-12 16:19
memberMember 917583217-Jul-12 16:19 
QuestionFinding distance for VoronoiGraph vertizes representing Medial Axis of closed boundary Pin
Member 917583214-Jul-12 5:02
memberMember 917583214-Jul-12 5:02 
GeneralRe: Finding distance for VoronoiGraph vertizes representing Medial Axis of closed boundary Pin
BenDi15-Jul-12 0:27
memberBenDi15-Jul-12 0:27 
AnswerRe: Finding distance for VoronoiGraph vertizes representing Medial Axis of closed boundary Pin
Kenneth Haugland17-Jul-12 9:31
memberKenneth Haugland17-Jul-12 9:31 
GeneralRe: Finding distance for VoronoiGraph vertizes representing Medial Axis of closed boundary Pin
Member 917583217-Jul-12 16:11
memberMember 917583217-Jul-12 16:11 
Good comment on the link. I have seen this video and even briefly looked into utilizing the code. I believe the code for Mesecina has been released. Although I decided to look elsewhere for because the voronoi computation utilizes CGAL, which I wanted to avoid.

I did implement a method of finding the radii of each of the vertices by computing the polygon point that has the minimum distance and setting this magnitude as the radius value for each vertices. Although before hand I also have a quick method that filters the vertices and edges that lie outside of the polygon. I accomplish this using the method described in this CodeProject article, Is a Point inside a Polygon?[^]. First the point is checked to see if it lies in the polygon min and max x and y values. If so, the point is then checked using the algorithm from the article, which uses each polygon sample point for each voronoi vertex for the check. This does take some computation time.

I am sure that there is a more efficient way to accomplish filtering only vertices and edges that lie in the polygon. Although because of this increased computation time I have considered diving into the Voronoi algorithm to see if the radius value can be found during the sweep line algorithm. Or I was thinking for each medial axis voronoi vertex the radius can be extracted by finding the intersection of the infinite edge attached to the medial axis voronoi vertex. This may be the most efficient approach.
QuestionIs there a way to construct polygons from all the edges ? And how ? Pin
seb.493-Jun-12 21:36
memberseb.493-Jun-12 21:36 
QuestionPossible issue. When I draw 2 points I haven't 2 area Pin
seb.4930-May-12 23:59
memberseb.4930-May-12 23:59 
AnswerRe: Possible issue. When I draw 2 points I haven't 2 area Pin
BenDi31-May-12 3:11
memberBenDi31-May-12 3:11 
GeneralRe: Possible issue. When I draw 2 points I haven't 2 area Pin
seb.4931-May-12 4:44
memberseb.4931-May-12 4:44 
GeneralRe: Possible issue. When I draw 2 points I haven't 2 area Pin
BenDi31-May-12 7:00
memberBenDi31-May-12 7:00 
GeneralRe: Possible issue. When I draw 2 points I haven't 2 area Pin
seb.4931-May-12 9:53
memberseb.4931-May-12 9:53 
QuestionThis code is shitted Pin
Member 868370514-May-12 4:42
memberMember 868370514-May-12 4:42 
AnswerRe: This code is shitted Pin
maamaamaa29-Jun-13 5:42
membermaamaamaa29-Jun-13 5:42 
QuestionAny way to handle boundaries and holes? Pin
James Maeding16-Dec-10 11:03
memberJames Maeding16-Dec-10 11:03 
AnswerRe: Any way to handle boundaries and holes? Pin
xinaesthetic30-Sep-11 7:38
memberxinaesthetic30-Sep-11 7:38 
GeneralMy vote of 5 Pin
maurice.calvert31-Aug-10 23:08
membermaurice.calvert31-Aug-10 23:08 
GeneralRe: My vote of 5 Pin
Member 868370514-May-12 4:45
memberMember 868370514-May-12 4:45 
GeneralRe: My vote of 5 Pin
maurice.calvert14-May-12 5:32
membermaurice.calvert14-May-12 5:32 
GeneralRe: My vote of 5 Pin
Member 868370514-May-12 21:38
memberMember 868370514-May-12 21:38 
GeneralRe: My vote of 5 Pin
maurice.calvert15-May-12 4:56
membermaurice.calvert15-May-12 4:56 
Generalplease help soon Pin
daskan8-Aug-09 1:55
memberdaskan8-Aug-09 1:55 
QuestionVoronoi Cells Pin
C-Bl27-Jul-09 23:08
memberC-Bl27-Jul-09 23:08 
Answer3 data points case Pin
SOAD_21-Jun-09 6:08
memberSOAD_21-Jun-09 6:08 
GeneralRe: 3 data points case Pin
rhill-ca26-Jun-09 6:45
memberrhill-ca26-Jun-09 6:45 
GeneralThiessen Polygons Pin
SOAD_19-Jun-09 14:46
memberSOAD_19-Jun-09 14:46 
GeneralAnother wrong vertex Pin
Sunil Terkar11-May-09 2:04
memberSunil Terkar11-May-09 2:04 
GeneralRe: Another wrong vertex Pin
BenDi11-May-09 10:03
memberBenDi11-May-09 10:03 
GeneralRe: Another wrong vertex Pin
Sunil Terkar12-May-09 0:37
memberSunil Terkar12-May-09 0:37 
GeneralRe: Another wrong vertex Pin
Sunil Terkar12-May-09 5:09
memberSunil Terkar12-May-09 5:09 
GeneralRe: Another wrong vertex Pin
rhill-ca26-Jun-09 6:34
memberrhill-ca26-Jun-09 6:34 
GeneralShort of one edge and one vertex Pin
Sunil Terkar5-May-09 23:11
memberSunil Terkar5-May-09 23:11 
GeneralRe: Short of one edge and one vertex Pin
rhill-ca26-Jun-09 6:31
memberrhill-ca26-Jun-09 6:31 
Generalmedial axis Pin
led16-Apr-09 9:38
memberled16-Apr-09 9:38 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

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

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.170713.1 | Last Updated 22 Apr 2013
Article Copyright 2005 by BenDi
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid