Click here to Skip to main content
11,485,334 members (77,797 online)
Click here to Skip to main content

Fortune's Voronoi algorithm implemented in C#

, 21 Apr 2013 MPL 216.5K 2.6K 49
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! 

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

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

License

This article, along with any associated source code and files, is licensed under The Mozilla Public License 1.1 (MPL 1.1)

Share

About the Author

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

Comments and Discussions

 
GeneralThiessen Polygons Pin
SOAD_19-Jun-09 15:46
memberSOAD_19-Jun-09 15:46 
GeneralAnother wrong vertex Pin
Sunil Terkar11-May-09 3:04
memberSunil Terkar11-May-09 3:04 
GeneralRe: Another wrong vertex Pin
BenDi11-May-09 11:03
memberBenDi11-May-09 11:03 
GeneralRe: Another wrong vertex Pin
Sunil Terkar12-May-09 1:37
memberSunil Terkar12-May-09 1:37 
GeneralRe: Another wrong vertex Pin
Sunil Terkar12-May-09 6:09
memberSunil Terkar12-May-09 6:09 
GeneralRe: Another wrong vertex Pin
rhill-ca26-Jun-09 7:34
memberrhill-ca26-Jun-09 7:34 
GeneralShort of one edge and one vertex Pin
Sunil Terkar6-May-09 0:11
memberSunil Terkar6-May-09 0:11 
GeneralRe: Short of one edge and one vertex Pin
rhill-ca26-Jun-09 7:31
memberrhill-ca26-Jun-09 7:31 
Generalmedial axis Pin
led16-Apr-09 10:38
memberled16-Apr-09 10:38 
GeneralThanks! Pin
Reconstructivism30-Mar-09 3:48
memberReconstructivism30-Mar-09 3:48 
GeneralRays Pin
Wayne Romer22-Mar-09 21:55
memberWayne Romer22-Mar-09 21:55 
GeneralRe: Rays Pin
Reconstructivism30-Mar-09 3:56
memberReconstructivism30-Mar-09 3:56 
GeneralRe: Rays Pin
BenDi30-Mar-09 9:57
memberBenDi30-Mar-09 9:57 
GeneralRe: Rays Pin
Pavel Vladov29-Apr-09 1:54
memberPavel Vladov29-Apr-09 1:54 
Do you mean that the Voronoi edge ray must start at VVertexA and must have the direction of the line made by the points LeftData and RightData (i.e. from LeftData to RightData comes first). If yes, then your algorithm is wrong. Just test it on a rectangle and you will see the result. If I misunderstood you, please explain how to get the rays in more details.

Vladovsoft
Software products for fitness and health club management, storehouses, shops and barcode generation.

GeneralRe: Rays Pin
BenDi29-Apr-09 10:49
memberBenDi29-Apr-09 10:49 
GeneralRe: Rays Pin
Pavel Vladov30-Apr-09 0:39
memberPavel Vladov30-Apr-09 0:39 
GeneralRe: Rays Pin
BenDi30-Apr-09 9:04
memberBenDi30-Apr-09 9:04 
GeneralRe: Rays Pin
Pavel Vladov30-Apr-09 23:36
memberPavel Vladov30-Apr-09 23:36 
GeneralRe: Rays Pin
Slagh14-May-09 23:10
memberSlagh14-May-09 23:10 
GeneralRe: Rays Pin
BenDi16-May-09 3:15
memberBenDi16-May-09 3:15 
AnswerRe: Rays Pin
Slagh21-May-09 20:54
memberSlagh21-May-09 20:54 
BugRe: Rays Pin
PehGuevara27-Feb-13 5:15
memberPehGuevara27-Feb-13 5:15 
GeneralRe: Rays Pin
BenDi27-Feb-13 22:53
memberBenDi27-Feb-13 22:53 
GeneralRe: Rays Pin
PehGuevara27-Feb-13 23:32
memberPehGuevara27-Feb-13 23:32 
GeneralRe: Rays Pin
BenDi2-Mar-13 9:28
memberBenDi2-Mar-13 9:28 
GeneralRe: Rays Pin
PehGuevara6-Mar-13 0:59
memberPehGuevara6-Mar-13 0:59 
GeneralRe: Rays Pin
BenDi6-Mar-13 1:16
memberBenDi6-Mar-13 1:16 
AnswerRe: Rays Pin
PehGuevara7-Mar-13 7:44
memberPehGuevara7-Mar-13 7:44 
GeneralRe: Rays Pin
Ray Hidayat7-Jun-11 19:06
memberRay Hidayat7-Jun-11 19:06 
GeneralRe: Rays Pin
ckaut30-Jan-10 5:20
memberckaut30-Jan-10 5:20 
QuestionHow to use Fortune.ComputeVoronoiGraph function Pin
Sunil Terkar3-Mar-09 5:20
memberSunil Terkar3-Mar-09 5:20 
AnswerRe: How to use Fortune.ComputeVoronoiGraph function Pin
Wayne Romer22-Mar-09 21:56
memberWayne Romer22-Mar-09 21:56 
Generaluse with sharpmap Pin
agelospanagiotakis15-Feb-09 0:51
memberagelospanagiotakis15-Feb-09 0:51 
GeneralRe: use with sharpmap Pin
BenDi30-Mar-09 9:58
memberBenDi30-Mar-09 9:58 
Generalproblem Pin
mabrouki2331-Dec-08 6:03
membermabrouki2331-Dec-08 6:03 
GeneralVisualization. Pin
Maxim_Barsuk17-Nov-08 23:05
memberMaxim_Barsuk17-Nov-08 23:05 
GeneralData points to Polygons Pin
Zanele Mkhize3-Sep-08 4:25
memberZanele Mkhize3-Sep-08 4:25 
GeneralRe: Data points to Polygons Pin
BenDi3-Sep-08 5:46
memberBenDi3-Sep-08 5:46 
QuestionA vector line is reversed ... Pin
plunkman31-Jul-08 10:51
memberplunkman31-Jul-08 10:51 
AnswerRe: A vector line is reversed ... Pin
plunkman31-Jul-08 11:54
memberplunkman31-Jul-08 11:54 
General... what a mess! [modified] Pin
NeoGeek9-Jun-08 7:29
memberNeoGeek9-Jun-08 7:29 
Generalproblem Pin
Member 454520718-Apr-08 1:09
memberMember 454520718-Apr-08 1:09 
Generalhelp please Pin
Member 454520717-Apr-08 13:32
memberMember 454520717-Apr-08 13:32 
GeneralRe: help please Pin
Member 454520717-Apr-08 14:01
memberMember 454520717-Apr-08 14:01 
Generalsample Pin
yansike31-Mar-08 17:42
memberyansike31-Mar-08 17:42 
Generalerror: wrong voronoi diagrams Pin
Morton14-Mar-08 3:42
memberMorton14-Mar-08 3:42 
GeneralRe: error: wrong voronoi diagrams Pin
BenDi14-Mar-08 4:53
memberBenDi14-Mar-08 4:53 
GeneralRe: error: wrong voronoi diagrams Pin
Morton18-Mar-08 1:36
memberMorton18-Mar-08 1:36 
QuestionDoubt Pin
CPMO8-Feb-07 7:58
memberCPMO8-Feb-07 7:58 
AnswerRe: Doubt Pin
BenDi8-Feb-07 10:39
memberBenDi8-Feb-07 10:39 

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

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

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