Zhenyu Pan, a Masters student from York University, has reimplemented my C++ Voronoi generation algorithm (itself an adaptation of Steven Fortune’s sweep-line algorithm written in C) in Java. A Voronoi diagram is a graph where each edge is equidistant from the two points in the graph closest to it. 
Background:
Quite a few years ago (2003) I completed a research masters in mobile robotics, concentrating on robotic navigation and map building. As part of that research, and for about a year after it, I wrote many (many, many,many 🙂 ) thousands of lines of code to perform map building using sonars in numerous different ways, as well as performing a lot of different analysis techniques on them, one of which used Voronoi diagrams for spatial analysis. If you’re interested, you can download my Masters Thesis here.
So as to not see my work fade away and die, I first of all wrote an application called Map Viewer that provides lots of the useful features for researchers in mobile robotics and map building. Secondly, I started an open source project on Sourceforge called Map Manager, which is a standalone library that people can integrate into their own research. This included the Voronoi code I wrote, all in C++.
Back to the present:
Well, while I’ve been getting a steady number of emails over the years of people using my code (not exactly a flood, 3 or 4 per month), this is the first time that anyone has contributed back. Zhenyu Pan completely reimplemented my Voronoi C++ class in Java, and incorporated it into a Java Applet. Needless to say, I am very impressed.
The algorithm was originally written by a researcher called Steven Fortune in C, and while very performant and intelligent, it followed in the grand tradition of all C programs in being completely incomprehensible. I spent many a painful night converting into a marginally more understandable C++ class (also cleaning up the code, fixing memory leaks etc). That Zhenyu has been able to convert it from C++ to Java is very impressive (C to C++ is not so tricky, since C++ is a superset of C), as the code made very liberal use of non-Java constructs such as double pointers. His code, like mine and Stevens, runs extremely quickly, and seems to be very accurate and reliable.
I’ll be adding his code to the Map Manager open source project soon. For now, I’ve put his applet on the web at http://mapviewer.skynet.ie/java , and he will soon be putting it up on his university’s website at http://www.cse.yorku.ca/~aaw .
A big thanks to Zhenyu for attempting such a challenging project, and for contributing back to the project.
SOS 
Hi,
Just wondering what the status of the Java Voronoi code is? I didn’t see it in the MapManager project CVS repository yet, and the linked university pages only seem to contain applets and pseudocode, no sources.
Good question – I’ll send an email to the author too see how he’s getting on. Until he gets back to me, the code is available at http://mapviewer.skynet.ie/java/voronoi_java.zip
Ok, thanks.
Thanks very much for making this stuff available. The power-point and lecture notes on your website were the best presentation of the Fortune Sweep algorithm I’ve come across.
Hi Christopher,
You’re very welcome, glad it helped.
Shane
Wow, interesting…
Congrats, and thanks for making it available, impressive stuff.
I have few questions:
– In the algorithm you get just the sides (lines) that makes the Voronoi’s diagram, or you can get polygons (areas) too?
– In case that it only gets the sides (lines), it would be hard to implement a way to get polygons (areas)?
*Sorry, but im not good at english… xD
You’re very welcome. It doesn’t calculate the polygons, however it does calculate the set of edges. You can retrieve them using getNextVertexPair(). Make sure to set ‘genVectorInfo’ to true when calling the generateVoronoi() function.
This will give you a list of edges. You could then write some logic that matched up all edges that form a polygon, using some kind of 2d map.
Thanks
Shane
You’re very welcome. It doesn’t calculate the polygons, however it does calculate the set of edges. You can retrieve them using getNextVertexPair(). Make sure to set ‘genVectorInfo’ to true when calling the generateVoronoi() function.
This will give you a list of edges. You could then write some logic that matched up all edges that form a polygon, using some kind of 2d map.
Thanks
Shane
Hi Shane.
I tried to write a wrapper for your Voronoi code in order to save myself the huge effort of wading through Fortune’s C code myself. Thanks for putting your work online, by the way 🙂
I had to chop out the logger files since your preprocessor magic wouldn’t compile under my system (WinXP, DevCPP 4.9.9.2 with MinGW), but I redirected some of that to std::cout to check intermediate results.
Now however to the critical point:
I entered some test cases and in none of them any output was generated. I checked if the critical functions in your code were entered, and everything seems alright, but after the generateVoronoi function is done, there are no edges and no vertex pairs.
I made the pushGraphEdge() function output a notifier whenever it is called to check if it only is an interface problem with my wrapper, but apparently indeed no edges are written. My main test case consisted of 4 points arranged basically like a Mercedes Benz star well inside the bounding box. Your infinite while loop counted up to 7 events, which is exactly what I’d expected from comparing with interactive voronoi tools found on the web.
My wrapper is basically this:
float minDist = 0.0;
cout << “entering Shane O’Sullivan’s routine” << endl << endl;
VoronoiDiagramGenerator vgen;
bool success = vgen.generateVoronoi(xVal, yVal, pl.getNumberPoints(), float(minX), float(maxX), float(minY), float(maxY), minDist, true);
cout << “SOS voronoi algorithm: ” << (success? “success” : “failure”) << endl;
float x1, y1, x2, y2;
//read all edges
vgen.resetIterator();
while(vgen.getNext(x1, y1, x2, y2) ){
//returnValue.addEdge(x1, y1, x2, y2);
cout << “found edge: ” << x1 << “,” << y1 << ” – ” << x2 << “,” << y2 << endl;
}
//read all vertex pairs
vgen.resetVertexPairIterator();
while(vgen.getNextVertexPair(x1, y1, x2, y2) ){
cout << “found vertex pair: ” << x1 << “,” << y1 << ” – ” << x2 << “,” << y2 << endl;
}
Any glaring interface errors? Any idea what I did wrong?
Thank you! You are very kind for sharing your hard work.
I plan to derive the logic that produces polygon data from the edge data. I would also like to do this by pairing the edges with the corresponding points they bisect so that adjacent cells(polygons) can share signals through this “boundary”.
Hi Shane,
Thanks very much for sharing your C++ code. I am using your program to generate Voronoi cells to represent magnetic grains on a medium to model hi-density magnetic recording. I’m compiling my program and testing it with Valgrind to catch memory leaks. I’m picking some memory leaks that I think may be tied to your VoronoiDiagramGenerator.cpp. Sample output from Valgrind:
==30080==
==30080== 8 bytes in 1 blocks are definitely lost in loss record 1 of 14
==30080== at 0x40253C5: operator new(unsigned int) (vg_replace_malloc.c:214)
==30080== by 0x804D0BD: VoronoiDiagramGenerator::VoronoiDiagramGenerator() (VoronoiDiagramGenerator.cpp:37)
==30080== by 0x804BD9D: calcVoronoiVertices(media*) (createMedia_VoronoiGrains.cpp:605)
==30080== by 0x804BD00: calcVList(media*) (createMedia_VoronoiGrains.cpp:582)
==30080== by 0x8049810: main (main.c:120)
==30080==
I think the memory leak may be quite small, Valgrind is reporting only 988 bytes lost at the end. I’m not sure how much of it is from my code, and how much of it is VoronoiDiagramGenerator.cpp.
Unfortunately I am new to C++ and it’s memory allocation methods, otherwise I would send you a code-fix. As it is, I can only say that Valgrind is reporting some lost memory.
BTW, I read back in posts and saw Seigneur’s question about calculating polygons and areas.
That is just what I am doing now. I’m using another free library called ANN (approximate nearest neighbors) to efficiently find the nearest neighbor of each Voronoi Vertex (vv), where the search is over the set of voronoi nodes. Most vv’s should have 3 nearest neighbors that are equally near. I push each vv onto a list of vertices associated with each of the 3 nearest nodes. Each voronoi node, will have a list of vertices which make up its polygon, that I’ve been calling the vList.
You have to sort those vertices such that they are in order of increasing (or decreasing) angle subtended at the node (or at any point inside the cell). Following the vertices around in this order will generate the polygon. Areas of the polygon can be calculated as a summation of areas of triangles formed by 2 vertices and the node, iterating over each pair of vertices comprising the edges of the polygon.
shit – I just saw that I posted my email adress as name – can you *please* delete the comment to prevent it from being harvested?
Thanks
Felix: Deleted you previous post as requested. It was:
I tried out the code and it works amazingly fast, but the memory leak issue is killing me.
Any idea where it could be?
Has Anybody provided a fix?
Would be GREAT!
Felix, are you referring to the C++ or Java code?
Thanks a lot.
I am referring to the C++ code. I am using it for a video-installation that generates voronoi diagrams in real-time.
Unfortunately, the process gets bigger at a rate that is almost as amazing as the speed of the calculation…
Did you ever see this problem yourself?
Thanks,
Felix
Are you using the code from http://sourceforge.net/projects/mapmanager/ ?
Yes, that is the code that I used. I downloaded the whole package from sourceforge and used only the VoronoiDiagramGenerator.h & .cpp files. My only modification was to comment out all the logging related stuff (“LOG”).
There is also another (modified or older?) version on the net linked to here
http://forum.openframeworks.cc/index.php?&topic=4367.0
that has the same problem.
Meanwhile, I found a third modified version of your code in the fastjet project
http://www.lpthe.jussieu.fr/~salam/repository/software/fastjet/doxygen-2.3-beta0/Voronoi_8cc-source.html
This one does not suffer from the memory leak issue, but does not work correctly at the higher y boundary.
The author Gregory Soyez who made some quite substatial modifactions also claims that he made addition changes to the memory management, maybe he knows how to fix the issue.
Your support is quite extraordinary – I appreciate that!
Shane,
A huge thankyou to you and Zhenyu for making this code available. I’ve been using it to generate maps of UK postcode sectors.
I’ve taken Zhenyu’s Java version, refactored it somewhat and converted it to a Maven-based project. I’ve created a tiny Sourceforge project in case it’s useful to anyone else. It’s at https://sourceforge.net/projects/simplevoronoi/
For now, it’s mostly just a dump of the code in its current state. Needs Unit test and basic documentation – to be added soon hopefully. I figured I might as well make the code publicly available in a neat format. If you have any comments or thoughts, leave a reply or drop me an email.
Download link: http://sourceforge.net/projects/simplevoronoi/files/simplevoronoi-trunk-20110706.tar.gz/download
I’ve included the licence info that’s been added over the years (Stephen Fortune, Shane O’Sullivan, , Zhenyu Pan).
Thanks again for the code.
James Humphreys
Hi!
first, I thank you for you work. I want to do the same as Keith Youngblood. I use the Java implementation. I there a way to get all the lines that correspond to a point. I also want to build polygons. There is no getVertexPair() in the Java implementation.
Maybe you can get me some help. Inside voronoi_bd() where the sweep is done i plan to get the two Sites that correspond to a Edge and further process this information. As far as I understand, a edge is only created in the vector event?
Many Thanks,
Richard
Hello sir,
i am implementing voronoi diagram in NS2. So kindly i need a sample code for voronoi construction in TCL or in C++. Pls help me to complete my project. Am expecting a possible answer from u.
Check out the voronoi code at http://sourceforge.net/projects/mapmanager/
How is it that we’ve never discussed voronoi before? My grad school research involved voronoi tesselations on quasi-2D foam…
Dylan, I have no idea – I suppose it’s relatively rare that it would come up in conversation 🙂
Thanks for finally talking about >Fortune’s Sweep-Line Voronoi algorithm implemented in Java!
« SOS <Liked it!
pls send ns2 coding for region splitting in voronoi diadram as soon as possible
can u send ns2 coding for voronoi diagram?
I’m sorry, I don’t know what that is. I wrote this code 10 years ago and no longer work on it. Feel free to take it and build on it, but I won’t be making any changes in the future