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!

Convert easting northing to latitude longitude

The solution to this depends on how many places you'd like to convert. To be clear though, I'm talking about converting British Ordnance survey easting northing coordinates (EPSG:27700) into WGS84 latitude longitude coordinates (EPSG:4326). This blog entry can easily be adapted to do the inverse - or other coordinates systems.

Converting just a few?
Use a website. Like this one: http://www.nearby.org.uk/conversions.cgi

Converting a big batch?
Say you have a text file (CSV maybe) with 1.7 million entries (for example, all the postcodes in the UK from the Ordnance Survey Code Point data, which is now free and downloadable here).
You want to convert them all but don't fancy doing them one by one because you have a life.

To do this, I've used Python and Mapnik. You'll need some (very) basic programming skills to do this example. I'm in Linux (Ubuntu to be precise), so you might have to adapt this slightly if you're using something else.

You'll need Python and Mapnik installed. In Ubuntu, I installed the following packages:

• mapnik-utils
• python
• python-dev
• python-mapnik
• libmapnik-0.6
• libmapnik-dev

You might not need all of them, but I have them installed. Then, download a little example I put together here. Don't worry, even if you don't know Python. It's really simple.

Decompress it into a folder, then in a command line type:

python en_to_latlng.py input.txt

The input.txt file is just an example to get you started. Notice it just dumps the output to the console. To save it to a file:

python en_to_latlng.py input.txt > output.txt

The "greater than" symbol just pushes all the output into output.txt using output redirection.

Doing it in Java?
Yes, I like Java too. I used GeoTools to do this conversion in Java. If you use Maven, it's fantastically easy to add the dependencies. You'll need to add 3 things to your pom.xml:

1. Property which defines which version you're using
2. The dependencies themselves
3. The repository (from which to download the geotools JARs and POMs)

<properties>
        <geotools.version>2.7.0.1</geotools.version>
 </properties>
...


<dependency>
            <groupId>org.geotools</groupId>
            <artifactId>gt-main</artifactId>
            <version>${geotools.version}</version>
        </dependency>
        <dependency>
            <groupId>org.geotools</groupId>
            <artifactId>gt-epsg-hsql</artifactId>
            <version>${geotools.version}</version>
        </dependency>
        <dependency>
            <!-- include WarpAffine to prevent ClassLoader error -->
            <groupId>org.geotools</groupId>
            <artifactId>gt-xml</artifactId>
            <version>${geotools.version}</version>
        </dependency>
...


<repositories>
        <repository>
            <id>maven2-repository.dev.java.net</id>
            <name>Java.net repository</name>
            <url>http://download.java.net/maven/2</url>
        </repository>
        <repository>
            <id>osgeo</id>
            <name>Open Source Geospatial Foundation Repository</name>
            <url>http://download.osgeo.org/webdav/geotools/</url>
        </repository>
</repositories>








As for the code itself, it's pretty straightforward:




CRSAuthorityFactory crsFac =
                    ReferencingFactoryFinder.getCRSAuthorityFactory("EPSG", null);


            CoordinateReferenceSystem wgs84crs = crsFac.createCoordinateReferenceSystem("4326");
            CoordinateReferenceSystem osgbCrs = crsFac.createCoordinateReferenceSystem("27700");


            CoordinateOperation op = new DefaultCoordinateOperationFactory().createOperation(osgbCrs, wgs84crs);


            DirectPosition eastNorth = new GeneralDirectPosition(easting, northing);
            DirectPosition latLng = op.getMathTransform().transform(eastNorth, eastNorth);


            System.out.println("lat: " + latLng.getOrdinate(0));
            

System.out.println("lng: " + latLng.getOrdinate(1));

Doing it in Javascript?

The key here is Proj4, an Open Source library originally written in C but it's been ported to plenty of other languages, including Javascript. Basically, it allows easy conversions between coordinate systems and projections. What you're looking for is Proj4JS, Pro4J's Javascript brother. See the website for details - I'll add an example here if I get time.