Fortune’s Sweep-Line Voronoi algorithm implemented in Java!
Posted by Shane O'Sullivan on April 5, 2007
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.
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.