Sunday 21 November 2010

A fast Java implementation Fortune's Voronoi algorithm

This is a very brief post, just to release some Java Voronoi code that may be useful to others.

The code is based on Steven Fortune's original C code, which was then converted to C++, then a Java applet and now cleaned up slightly to run as a Maven-based project.

There is no graphical display code in this. The input is simply a set of X/Y coordinates for each site. The output is a list of GraphEdges, which contain a start/end X/Y coordinate pair. Display is left to the coder.

The code is available on the Simple Voronoi project, hosted on Sourceforge.
The whole project is based on the Java code posted in the comments here: http://shaneosullivan.wordpress.com/2007/04/05/fortunes-sweep-line-voronoi-algorithm-implemented-in-java/
The code it is based on is at http://mapviewer.skynet.ie/java/voronoi_java.zip


To use it, build it and add the following dependencies to your project:

 <dependency>  
       <groupId>be.humphreys</groupId>  
       <artifactId>simplevoronoi</artifactId>  
       <version>0.2-SNAPSHOT</version>  
 </dependency>  

The code you use will look something like this:


 Voronoi v = new Voronoi(0.00001f);  
     List<GraphEdge> allEdges = v.generateVoronoi(latValues, lngValues, minLat, maxLat, minLng, maxLng);  


I will write a longer, more detailed and much more useful post when time allows!

2 comments:

  1. Thank, I appreciate your help, the code look really great and will put the license into my game.
    -lls

    ReplyDelete
  2. Wonderful!

    I was wondering : What exact license is it released under?
    I wanted a quick and dirty implementation of Voronoi diagrams for a really minor aspect of a commercial -yet personnal- project.

    I went for the "findClosestPoint" algorithm, which is so slow that I understand why I don't see any descripton of it anywhere!

    ReplyDelete