Lin.ear th.inking

Let's do it again at FOSS4G-NA!

2012-01-27T20:06:00.000-08:00

FOSS4G 2011 in Denver last September was such a good time, we're going to do it all over again at FOSS4G North America 2012!

It will be interesting to see who and how many attend. Some conference budgets might have been blown last year - but note that this event is cleverly timed to fall into a new fiscal! And being in D.C. there should be lots of suits and spooks in attendance.

I'm definitely looking forward to building on the momentum from the last conference, especially given my new gig with OpenGeo (ok, I'm definitely not booth-babe material - but being a booth-geek is probably more fun).

Your Favourite Map Projection

2011-11-17T22:32:00.001-08:00

...and what it says about you.

XKCD goes geospatial! (Happens to everything eventually...)

OpenGeo Interview

2011-11-10T09:42:00.001-08:00

My name in lights once again. If this keeps up I'm going to have to start asking for an outrageous rider...

Sobering thought

2011-10-27T22:50:00.000-07:00

According to this interesting BBC page on population, the number of humans on Earth has more than doubled in my lifetime.

Anyone who has spent time trying to speed up an O(n^2) algorithm knows this can't be a good thing...

Using a web service for Elevation from JEQL

2011-10-25T12:17:00.000-07:00

MapQuest has a whole range of useful and freely available web services for geospatial queries. One of these is the Open Elevation Service. I thought it would be interesting to try it out using JEQL's capabilities of querying URLs and plotting datasets as images.

The Open Elevation Service is extremely simple to use. You just submit a URL containing the location:

http://open.mapquestapi.com/elevation/v1/getElevationProfile?callback=foo&shapeFormat=raw&latLngCollection=39.740112,-104.984856

and you get back a JSON (or XML) response with the elevation:

foo({
"shapePoints":[39.740112,-104.984856],
"elevationProfile":[{"distance":0,"height":1616}],
"info":{"copyright":{"text":"Â© 2011 MapQuest, Inc.","imageUrl":"http://tile21.mqcdn.com/res/mqlogo.gif","imageAltText":"Â© 2011 MapQuest, Inc."},
"statuscode":0,
"messages":[]}
});

JEQL doesn't (yet) do JSON parsing, but it's easy to pick out the height attribute with a simple RegEx:

height = RegEx.extract(elevJson, \'"height":(-?\d+)\}');

Querying over a grid of locations provides a dataset which is a gridded Digital Elevation Model (DEM). JEQL provides a function to generate a table which is a grid of integers, so it's easy to produce a grid of lat/long locations:

loc = select baseLat + i * cellSize lat, baseLon + j * cellSize lon
from Generate.grid(1, gridSize, 1, gridSize);

Once the elevations for all locations are retrieved, the locations are used to compute square cells (polygons) which cover the area, and the cells are symbolized with a fill value from a suitable color map based on elevation.

Here's the final result. It's slightly squashed in aspect ratio, since the data grid is in the lat/long coordinate system. The obvious data dropouts seem to be hard errors in the MapQuest service, which is slightly surprising. But's it's recognizably Mt. St. Helens - you can even see the lava dome in the crater!

Not surprisingly, this isn't quick to generate - the service runs at about 10 queries per second. (Actually, that seems pretty reasonable for a free web service!). The service does support querying multiple points per request - I might try to see if this decreases the latency (although this might be a bit complex to express in JEQL).

Here's the whole script:

//--------------------------------------
//
// Plots a DEM generated using the MapQuest Elevation service
//
//--------------------------------------
baseLat = 46.16 ;  baseLon = -122.25;    // Mt St Helens
areaSize = 0.10;
gridSize = 100;
cellSize = areaSize / gridSize;

//---- Generate location grid
loc = select     baseLat + i * cellSize lat, 
        baseLon + j * cellSize lon
    from Generate.grid(1, gridSize, 1, gridSize);

//---- Query elevation service for each grid point
telev = select lat, lon, elevJson, elev 
    with {
        url = $"http://open.mapquestapi.com/elevation/v1/getElevationProfile?callback=foo&shapeFormat=raw&latLngCollection=${lat},${lon}";
        elevJson = Net.readURLnoEOL(url);
        height = RegEx.extract(elevJson, \'"height":(-?\d+)\}');
        elev = Val.toInt(height);
    }
    from loc;
Mem telev;

//---- Create raster cell boxes, symbolize with color map based on elevation, and plot
minElev = 800.0; maxElev = 2500.0;
tplot = select Geom.createBoxExtent(lon, lat, cellSize, cellSize) cell,
        Color.interpolate("00a000", "ffb000", "aaaaaa", "ffffff", index) style_fillColor
    with {
        index = (elev - minElev) / (maxElev - minElev);
    }
    from telev;

textent = select geomExtent(cell) from tplot;

Plot     extent: val(textent)
    data: tplot
    file: "dem.png";

(r-i-p (john mccarthy))

2011-10-24T20:09:00.000-07:00

John McCarthy, inventor of LISP, has died at age 84.

Having finally balanced his parentheses, his atoms can now be returned to the free list.

Jobs, Ritchie, McCarthy - so many of the greats passing....

Extracting GTFS data using JEQL

2011-10-07T11:49:00.000-07:00

Once you understand the General Transit Feed Specification (GTFS) data model, the next step is to transform the data into a format usable in GIS tools. As usual, that means shapefiles (sigh...). Here's a JEQL script that extracts the geometry of all unique trips (aka "route patterns"), as well as the stop locations.

Some interesting aspects of the script:

the GTFS spatial data is in geographic coordinates (lat/long). The script projects this into BC-Albers (EPGS code 3005) using the CRS.project() function. Many other coordinate systems could be used (or none - e.g. for output to KML)
the geomConnect()aggregate function connects Points into LineStrings

/*=======================================================
Extracts Trips (with shapes) and stops from from a GTFS dataset. 
Includes shape, trip and route information.
Spatial data is converted from Geographic to BC-ALbers

Usage Notes:
- indir: directory containing the input GTFS files
========================================================*/

indir = "";  outdir = "";

//========================================================
//  Extract Trips with unique linework, with route information
//========================================================
CSVReader tshape hasColNames: file: indir+"shapes.txt";
CSVReader ttrip hasColNames: file: indir+"trips.txt";
CSVReader troutes hasColNames: file: indir+"routes.txt";  
Mem troutes;

crs_BCAlbers = "EPSG:3005";

//--- extract unique shapes
trips = select distinct route_id, trip_headsign, shape_id 
    from ttrip;

//--- extract trip pts and order them in sequence
tpt = select shape_id, Val.toInt(shape_pt_sequence) seq,
		Geom.createPoint(Val.toDouble(shape_pt_lon), 
                                 Val.toDouble(shape_pt_lat) ) pt
	from tshape
	order by shape_id, seq;

//--- connect pts into lines and project
tline = select shape_id, 
     CRS.project(Geom.toMulti(geomConnect(pt)), crs_BCAlbers) geom
	from tpt
	group by shape_id;
	
//--- join route info to trip shape
trouteLines = select r.route_id, r.agency_id, 
    r.route_short_name, r.route_long_name,
    r.route_type, r.route_url,
    trip_headsign, l.*
        from tline l
        join trips t on t.shape_id == l.shape_id
        join troutes r on r.route_id == t.route_id;

ShapefileWriter trouteLines file: outdir+"gtfs_trips.shp";

//========================================================
//  Extract Stop points
//========================================================
CSVReader tstopsRaw hasColNames: file: indir+"stops.txt";

tstop = select stop_id,stop_code,stop_name,stop_desc,
        CRS.project(Geom.createPoint(
	    Val.toDouble(stop_lon), 
	    Val.toDouble(stop_lat) ), crs_BCAlbers) pt,
        zone_id
        from tstopsRaw;

ShapefileWriter tstop file: outdir+"gtfs_stops.shp";

Using this script on the GTFS data for Metro Vancouver (available from TransLink here) produces a dataset that looks like this:

JTS & GEOS Wordles

2011-10-07T10:21:00.000-07:00

For my JTS talk at FOSS4G I created a couple of Wordles showing systems which use JTS and GEOS. Here they are for posterity (and because I love seeing Wordles...)

Lars Rasmussen on the startup of Google Maps

2011-09-29T13:48:00.000-07:00

Here's some interesting background to where Google Maps came from. Must feel pretty good to have created a revolution (slippy maps) - and maybe to have just missed creating another one (Google Wave as an alternative to email).

Data model diagrams for GTFS

2011-09-27T10:06:00.000-07:00

Recently I've been doing some work with the General Transit Feed Specification (GTFS). This is a simple data model initiated by Google, in order to allow transit organizations to publish their schedules for routing and visualization purposes.

As usual, Google has nice, succinct documentation for the GTFS format (which is a set of CSV files embodying an implicit data model). But I was surprised to find that they don't provide any kind of data model diagram showing the relationships between the various entities (files) in the model. I have a feeling that they think this would be "too technical" for users - or maybe they just don't believe in using a long-established body of theory?

So, to help my understanding of GTFS I put together a simple diagram of the data model. I used Google Diagrams, which is why this looks a little primitive. (Hmmm... maybe another reason they don't do diagrams is that they are religious about dog-fooding?)

After doing this I found the paper A Transmodel based XML schema for the Google Transit Feed Specification, which has a much more detailed UML model of GTFS:

The end goal of doing all this was to be able to transform a GTFS data feed into shapefile format. For this I used a simple JEQL script. But that's another blog post.

Paul Ramsey's Keynote at FOSS4G 2011

2011-09-19T13:02:00.000-07:00

As usual, Paul delivered a highly amusing and thought-provoking keynote at FOSS4G 2011. For the benefit of the hard-core twitterless, the slides are here.

Everything you wanted to know about UK Coordinate Systems

2011-09-01T21:55:00.000-07:00

Those helpful folks at the UK Ordnance Survey have provided a fine reference Guide to Coordinate Systems in Great Britain. It's well worth reading if you're interested in the intricacies of coordinate systems, datums, surveying and GPS. It's a bit technical, but if you can handle coding in Javascript you can probably get something out of it...

An interesting extract gives the general flavour:

The WGS84 Cartesian axes and ellipsoid are geocentric; that is, their origin is the centre of mass of the whole Earth including oceans and atmosphere.
The scale of the axes is that of the local Earth frame, in the sense of the relativistic theory of gravitation.
Their orientation (that is, the directions of the axes, and hence the orientation of the ellipsoid equator and prime meridian of zero longitude) coincided with the equator and prime meridian of the Bureau Internationale de l’Heure at the moment in time 1984.0 (that is, midnight on New Year’s Eve 1983).
Since 1984.0, the orientation of the axes and ellipsoid has changed such that the average motion of the crustal plates relative to the ellipsoid is zero. This ensures that the Z-axis of the WGS84 datum coincides with the International Reference Pole, and that the prime meridian of the ellipsoid (that is, the plane containing the Z and X Cartesian axes) coincides with the International Reference Meridian.
The shape and size of the WGS84 biaxial ellipsoid is defined by the semi-major axis length a 6378137.0 metres, and the reciprocal of flattening 1/f 298.257223563. This ellipsoid is the same shape and size as the GRS80 ellipsoid.
Conventional values are also adopted for the standard angular velocity of the Earth, and for the Earth gravitational constant. The first is needed for time measurement, and the second to define the scale of the system in a relativistic sense.

Now then, if you find yourself getting lost on the way from Foyle's to the nearest Lyon's tea shop, you can't say you haven't been warned!

Interview with Directions Magazine

2011-08-24T11:56:00.000-07:00

The Twittersphere is buzzing with my latest (well, only) interview with Directions Magazine on the State of the JTS Topology Suite.

Props to Rob Rutherford and Amber Weber at Clover Point for setting this up!

Would you be lost without it?

2011-07-14T16:07:00.000-07:00

Nowadays GPS is ubiquitous in electronic gadgets (no electric toothbrush is complete without it!) GPS is a classic example of iceberg technology ¹. An output which in one sense verges on trivial - two numbers! - in fact relies on a huge unseen infrastructure of technology, physics, organizations, and yes, government funding.

The UK Telegraph has an interesting article on GPS ² covering some of the technical, scientific, historic and political background to the system.

On a side note, I'm happy to observe that statements like this aren't as common as they used to be:

Slightly worryingly, when I was invited to watch a “contact” in another control room earlier in the day, the software crashed and a familiar, blue Microsoft Windows screen appeared on the wall

Notes:

yes I made this up. My entry for Internet memedom!
don't worry, it's still safe to use your cellphone after visiting this site

JTS 1.12 released

2011-06-26T21:41:00.000-07:00

JTS 1.12 has been released, and is now available for download at SourceForge.

Some highlights of this release include:

Single-Sided Buffers
MinimumClearance function
nearestNeighbours methods for STRtree
Vector2D class for vector operations
DD (DoubleDouble) enhanced precision arithmetic
improved robustness for Delaunay and Voronoi computation
enhanced geometry digitization in the TestBuilder, along with a dynamic grid

... along with many other features, enhancements and fixes.

Single-Sided Buffer

Apple walls getting higher

2011-06-08T16:04:00.000-07:00

ZDNet has an interesting long view on the Apple iCloud announcement. Money quote:
The mobile world is moving away from the chock-full-o’-content web and increasingly becoming a world of closed pipes of content, with Apple, Google, HP and Microsoft regulating the flow. Tech fiefdoms scattered across a vast open land have expanded into warring nation-states with adjacent borders. The Mac vs. PC vs. Linux argument from the early days of consumer computing has lost a great deal of its luster in recent years with the development of cloud computing on the open web, but the concept of platform wars is quickly making up for lost ground with the development of cloud computing in the closed mobile space.
I've always found the Apple walled garden a bit scary in its restrictions. Now the walls are getting higher and thicker - and other vendors will be following suit as fast as they dare.

I don't find Google's garden as threatening, for some reason. Perhaps because they have a different business model, based on page views rather than selling devices or software. For now that encourages them to not put any limits on where and how you access their services. But will that change if the Chromebook takes off? Is the fact that Honeycomb is not open source a tiny black cloud on the horizon?

Java gets Reheated at OSCON

2011-06-06T22:35:00.000-07:00

It's good to see that O'Reilly is adding a Java flavour to the OSCON conference. They have a good blog post highlighting why they think Java (and the JVM) is still one of the most important programming platforms around, especially for open source development.

Some of the interesting Java projects that will be covered at the conference are:

Incanter, a Clojure-based statistics library (this project is particularly interesting to me, since it overlaps with some of the target space of JEQL)
Gradle, a Groovy DSL for building, testing, and deploying software
Jenkins, a continuous integration platform
Neo4J, a graph database

Some may think that Java is entering the Red Giant phase of language evolution, but it still has the capacity to throw off some powerful solar flares. The longer the coffee pot sits on the stove, the stronger it gets...

JTS arrives in JavaScript

2011-05-19T11:58:00.001-07:00

As I predicted back in 2008, JTS has now colonized the JavaScript ecosystem, thanks to the work of Bjorn Hartell on JSTS. At least, the project has been launched - it's a bit unclear as to how much functionality is actually there.

I hope to see some slick browser-based UI clients pop up, using Canvas or perhaps SVG?

The language scorecard for JTS now looks like:

JTS - Java (and Groovy, Scala, Jython, etc)

GEOS - C/C++

NET Topology Suite - MS .NET

Shapely - Python (via GEOS)

Ruby - via GEOS

PHP - via GEOS

JSTS - JavaScript

FOSS4G is the place to be!

2011-05-04T20:51:00.000-07:00

FOSS4G 2011 is happening in Denver this September.

I've submitted two abstracts for presentations:

Spatial Processing using JEQL

JEQL is a simple yet powerful language designed for expressing spatial (and non-spatial) processes. It follows the Table-Oriented Programming paradigm and provides a SQL-like query language. This talk gives an overview of JEQL and show some examples of its use.

What's New in JTS

The JTS Topology Suite has had numerous improvements in the past few versions. These include performance improvements, bug fixes and new functionality such as Delaunay Triangulation, Single-Sided Buffers, and Hausdorff Distance. This talk will discuss the new features, and demonstrate them using the JTS TestBuilder utility. Potential further features will be presented for discussion.

Vote early, vote often - and vote for me!

See you in Denver....

Polygon Triangulation via Ear-Clipping with Delaunay Refinement

2011-04-08T10:24:00.000-07:00

After this thread on the JTS list Michael Bedward was inspired to create a polygon triangulation algorithm using the Ear-Clipping approach. Standard Ear-Clipping algorithms don't handle polygons with holes, but Michael made a nice extension to do this. (David Eberly has a good write-up on this subject here, and of course there's always Wikipedia).

One problem with ear-clipping is that it produces sub-optimal triangulations (in the the sense that it creates lots of very skinny triangles, which are visually and computationally unappealing). I suggested that he add a refinement step based on "flipping triangles" to improve the quality of the output triangle mesh. This is similar to the approach used in Delaunay triangulation algorithms, and in fact it turns out that a good flipping criteria is to test for the Delaunay condition. (Two adjacent triangles which form a convex quadrilateral are Delaunay if neither lies in the circumcircle of the other. Wikipedia has a nice visual explanation).

This code will get added to JTS in the next release. In the meantime, here's some cool pictures showing how it works.

A gnarly test polygon:

Before refinement

After refinement

A country that has been in the news recently:

Before refinement

After refinement

Dynamic Views in Google Blogs

2011-04-08T09:16:00.000-07:00

Check out the cool new Dynamic Views feature for Google Blogs. I'm not sure how useful this is actually going to be for readers (especially since you have to do URL editing to invoke them - WTB!? (Where's The Button 8^)

But they sure look purty. Here's a shot of the Flipcard view:

Slope/Aspect/Elevation using JTS

2011-04-07T15:00:00.000-07:00

David Skea is a longtime colleague, JTS contributor, and all-around geospatial guru. He's developing a Slope/Aspect/Elevation service to be used in forestry-related applications here in British Columbia. His work is a nice example of using JTS to perform real-world spatial processing.

The key to computing slope, aspect and elevation is to have a Digital Elevation Model (DEM) available for the terrain in the area of interest. In this case, the terrain data is provided by the TRIM irregular DEM, which is a dataset of over 500 million mass points covering all of British Columbia. To compute the required values for a given polygon, the first step is to extract only the mass points in the immediate region of the polygon (i.e. using the polygon envelope with a suitable buffer distance. The JTS Delaunay Triangulation API is used to compute a TIN triangulation from the TRIM mass points.

Using a JTS PointOnGeometryLocator, the triangles whose centroids lie in the polygon are selected. Since each mass point has an elevation value, each TIN triangle is located in 3D space. The normal vector can be computed for each triangle, which provides the slope and aspect values. The elevation is the height of the triangle centroid.

The SEA values for the triangles are averaged to compute the overall slope, aspect and elevation value for the polygon.

Here's a screenshot showing the results, using Google Earth as a convenient 3D visualization tool (click for full-size image).

GeoGeeks presentation on Geometry Libraries

2011-03-03T21:42:00.001-08:00

Paul Ramsey has been doing his usual excellent work of promoting geo-geekery by setting up a Victoria GeoGeeks Meetup. Tonight I gave a presentation on Geometry Libraries for Fun and Profit.

I was intending to give it back-to-back with a presentation on JTS, to make the whole subject more concrete - but I rambled on for so long I was yanked from the stage before I could start on the second one! That's actually good, since it will give me time to polish up the presentation a bit more. In the meantime, the current slide deck is here: JTS - A Libary for Geometry Processing.

Charting with JEQL

2011-01-11T22:34:00.000-08:00

SQL has an elegant syntax for grouping and aggregating data. Java has powerful libraries for charting and graphing (like JFreeChart). JEQL has easy handling of tabular data. These go together like chocolate and peanut butter - and, um, more chocolate. Put them all together and you get this code:


CSVReader troute hasColNames: file: "routeLine2.csv";

tCityCount = select count(*) cnt, fromCity city
 from troute
 group by fromCity
 order by cnt desc;

tdata = select city key, cnt value from tCityCount limit 20;

Chart type: "bar"
 data: tdata
 extrude:
 color: "00c0f0"
 showItemLabels:
 xAxisTitle: "Top Cities by Originating Air Routes"
 xAxisLabelRotation: -0.5
 width: 1000
 file: "cityRoutes.png";

producing this graph:

This uses the same air routes dataset created in a previous example, with a simple grouped summary to show the 20 cities with the most air routes originating in them.

JFreeChart is a bit notorious for being hard to use, but the JEQL command hides all the gory details behind a much simpler (but still powerful) Chart command interface. Currently Bar, XY, and Pie charts are supported. It will be easy to add other chart types as required.

Also on the ToDo list is to provide an option to emit Google Chart URLs, using the same set of options (at least, the ones that are applicable - and maybe some new ones).

Note: this is an experimental extension, which is not in a final state in the current JEQL release.

JEQL 0.9 released

2011-01-06T12:06:00.000-08:00

Good news for those who wanted to try out the geodetic air routes JEQL script. The script requires JEQL version 0.9 to run. This version is now available for download.

Goodbye LAMP, hello SMAQ

2010-12-28T21:08:00.000-08:00

A great article on the emerging SMAQ stack for big data.

I wonder if PIG does spatial?

Diving deep into Computational Geometry

2010-12-27T17:42:00.000-08:00

For a deep dive into the bracing waters of cutting-edge computational geometry, check out the online proceedings of the Canadian Conference of Computational Geometry.

Do NOT expect to see these algorithms appear in JTS anytime soon!

Visualizing geodetic information with JEQL

2010-12-26T12:00:00.000-08:00

The geo-blogosphere has been buzzing about the global Facebook friends visualization. This was done by Paul Butler using an R script and some clever techniques for working with geodetic data.

This kind of lightweight spatial analysis and visualization is squarely in the target zone for JEQL, so I thought I'd try something similar.

Of course I don't have access to the Facebook friends dataset, so I needed some other suitable dataset of global-scale links. An obvious candidate is airline routes. Luckily there is an excellent open data repository called OpenFlights. It has datasets which are tables of airport locations and air routes between airports:

airports.dat:


1,"Goroka","Goroka","Papua New Guinea","GKA","AYGA",-6.081689,145.391881,5282,10,"U"
2,"Madang","Madang","Papua New Guinea","MAG","AYMD",-5.207083,145.7887,20,10,"U"
3,"Mount Hagen","Mount Hagen","Papua New Guinea","HGU","AYMH",-5.826789,144.295861,5388,10,"U"
...

routes.dat:


0B,1542,AGP,1230,BBU,1650,,0,738
0B,1542,ARW,1647,BBU,1650,,0,340
0B,1542,BBU,1650,AGP,1230,,0,738
...

The first step is to prepare a suitable dataset for rendering. To get a table of FROM/TO locations, the routes table needs to be joined to the airport table. This is trivial to do in JEQL. After a bit of cleanup (such as removing missing data and duplicate routes), the final result is a dataset of links between airport locations using Lat/Long coordinates:


28,"Bagotville","Canada",48.330555,-70.996391,146,"Montreal","Canada",45.470556,-73.740833
29,"Baker Lake","Canada",64.298889,-96.077778,132,"Rankin Inlet","Canada",62.81139,-92.115833
30,"Campbell River","Canada",49.950832,-125.270833,119,"Comox","Canada",49.710833,-124.886667
30,"Campbell River","Canada",49.950832,-125.270833,156,"Vancouver","Canada",49.193889,-123.184444
...

As Paul found, a few other steps are needed to produce a visually appealing map:

Densify the route links to produce approximations to great-circle arcs
Break the arcs at the International Date Line to allow them to render correctly
Colour-theme the routes from longest to shortest using lighter colours for shorter routes
Render the lines with longer ones further back in the Z-order

For good measure I also added a background rendering of world land areas, as well as a country boundary layer on top. To avoid swamping the map, only routes with more than one flight listed are displayed.

The rendering is done using the following JEQL script:


CSVReader troute hasColNames: file: "routeLine2.csv";

trte = select  fromCity, toCity,
  Val.toDouble(fromLon) fromLon, Val.toDouble(fromLat) fromLat,
  Val.toDouble(toLon)   toLon,   Val.toDouble(toLat)   toLat
 from troute;
 
tlines = select fromCity, toCity, line, len
 with {
   line = Geodetic.split180(Geodetic.arc(fromLon, fromLat, toLon, toLat, 2));
   len = Geom.length(line);
 }
 from trte order by len desc;
 
tplot = select line,
 Color.interpolate("f0fff0", "00c077", "004020", len / 200.0 ) lineColor,
 0.4 lineWidth
 from tlines;
 
//----- Plot world landmasses for context
ShapefileReader tworld file: "world.shp";
tworldLine = select GEOMETRY, "22222277" lineColor from tworld;
tworldFill = select GEOMETRY, "333333"   fillColor from tworld;

width = 2000;
Plot width: width height: width / 2
 extent: LINESTRING(-180 -90, 180 90)
 
 data: tworldFill
 data: tplot
 data: tworldLine

 file: "routes.png";

That's about 40 lines of code, with only 9 statements. Not a bad LOC score... Of course the heavy lifting of handling geodetic data is done by Java functions, but that's part of the point. JEQL makes it easy to link to Java code, since that's a more appropriate technology for creating performant, resusable code.

Here's the final output:

The continent outlines aren't revealed as crisply as the Facebook friends map. That's because friend links tend to be more spatially coherent than airline routes (unless your acquaintances all have private jets). But it certainly shows where the world hotspots are for air traffic. Boy, those Europeans love to fly!

Next up: the KML version...

Single-Sided Buffers in JTS

2010-11-15T21:00:00.000-08:00

Due to popular demand I have added the capability to generate Single-Sided Buffers to JTS.

A single-sided buffer is the polygon formed by connecting a LineString to an offset curve generated on one side of the line.

Input Line

Single-Sided Buffer (width = 30)

Naturally either side can be specified, by choosing an appropriate sign for the offset distance (positive for the right side, negative for the left).

Single-Sided Buffer (width = -30)

At the moment there's a bit of a limitation, in that input linework with very narrow concave angles (relative to the buffer distance) create undesirable artifacts in the generated polygon. I'm hoping that some further thinking will come up with a way to avoid this, at least in most normal cases.

This functionality is accessed by setting an appropriate flag in the BufferParameters structure:

 BufferParameters bufParams = new BufferParameters();
 bufParams.setSingleSided(true);
 return BufferOp.bufferOp(geom, distance, bufParams);

Currently this code is in SVN. It will be released in JTS 1.12 (which will hopefully be shipping ~~before year-end~~ in Q2 2011).

Magnifying Topology using JTS

2010-08-19T10:00:00.000-07:00

An issue that comes up all the time in the JTS world is how to visualize the topology of geometries which have very close vertices and segments. For example, a question was recently posted on the PostGIS list about why in the situation shown below the spatial relationship predicate BLUE.contains(RED) evaluates to FALSE

At first glance it looks like the red polygon follows the boundary of the blue one exactly, which would result in BLUE.contains(RED) = TRUE. The immediate suspicion is that one of the apparently collinear points is actually in the exterior of the blue polygon. But which one? And how can this be confirmed visually?

Now it so happens that the rightmost vertex of the red polygon, which appears to be on the boundary of the blue polygon, is in fact in the its exterior - thus explaing why contains = FALSE. But it's so close to the boundary segment that no matter how far you zoom in, you can't see that this is the case. And it's certainly not obvious where to go looking for this error in the first place.

Back in the Dark Ages

The usual way to inspect these kinds of cases is is to tediously zoom in on each vertex. But this loses the visual context of the situation. And in very close cases it simply doesn't work, because the zoom factor is so great that the Swing graphics API is unable to display the scene correctly.

Zoomed in...

Zoomed further in...

Zoomed way in - FAIL!

Another alternative is a painstaking manual inspection of the coordinates of each vertex and segment (which by the way is straightforward in the TestBuilder and OpenJUMP, but can be difficult in other tools). But it's hard to convert the coordinate numbers into a mental image of the situation. And it's essentially impossible to do mentally if a vertex is near a non-rectilinear (slanted) line - in this case it's necessary to evaluate a complex mathematical algorithm to to determine the relative orientation of the vertex and line.

Into the 21st Century!

This limitation has bugged me for a long time, ever since JTS and the JCS Conflation Suite were being developed. And it keeps coming up as a question, since this kind of situation occurs a lot when overlaying polygons. Cutting new vertices into line segments almost always causes them to be non-coincident with the original segment, but with very, very small discrepancies.

So a while back I started to think about a tool that would somehow make subtle topological situations visible at convenient zoom levels. The idea has been gathering dust on the lab bench for years, but I've finally had a chance to implement it. It's now a feature in the JTS TestBuilder called Magnify Topology. Enabling it on changes the geometry view to provide easy and effective visualization of small topological differences.

Key aspects of Magnify Topology behaviour are:

Vertex displacement is done in a way that preserves the original topology (e.g. if a vertex is on the right side of a line it will stay on the right)
Vertices which are truly coincident or collinear remain unchanged in the magnified view.
It's easy and quick to toggle Magnify Topology on and off to compare the actual and magnified views.

Using Magnify Topology, the above case looks like this:

Now it's obvious where the red polygon violates the contains relationship! In addition, you can see that there are some very close vertices in the red polygon, that some of them are truly collinear with the blue boundary, and that the lower right red vertex is actually in the interior of the blue polygon.

Here's some more examples, showing actual and magnified views:

Example 1

Example 2

Note the truly coincident vertex along the boundary, which remains unchanged in the magnified view.

Example 3

Magnify Topology can also be used to detect and visualized differences between similar geometries (sort of like a visual geometric diff) Here's a contrived example, showing two copies of a JTS logo, in which one copy has two tiny discrepancies (in the 15th decimal place!):

Here's a more realistic real-world example:

This feature will be released in the next version of JTS. In the meantime it's available in the JTS SVN.

Cloudy Blogs

2010-08-02T21:43:00.000-07:00

In order to try and keep abreast of the most far-reaching change to IT and computing since the invention of the PC (or the Internet, or time-sharing, or LSI, or solid-state, or commercial computing, or binary logic...), I have inaugurated a Blog Roll for sites which focus on cloud computing (in all its myriad and ever-changing forms...)

See Cloudy Blog Roll in the RH side bar --->

Is JSON the CSV of the 21st Century?

2010-07-09T10:28:00.000-07:00

It strikes me that JSON might be the CSV of the 21st century. Consider these similarities:

They both use POT (plain old text) as their encoding
The basic datatypes are strings and numbers. JSON adds booleans and nulls - Yay for progress!
The only schema metadata supported is field names

JSON has the major advance of supporting hierarchical and array structures. Of course, this makes it correspondingly more difficult to parse.

CSV has stood the test of time extraordinarily well. According to good 'ol Wikipedia it's been around since at least 1967 - that's over 40 years!

And CSV is still well supported whereever tabular data is used. Let's see if JSON is still around in 2035... I suspect not, because the half-life of technologies is a lot shorter these days. (Maybe CSV is the stromatolite of file formats!)

It would be nice if JSON had a standard schema notation. (There is JSON-Schema. It copies the XML Schema idea of encoding the schema in JSON. It remains to be seen whether this makes it as easy to use and popular as XML Schema has been. 8^)

And why, o why, do field names have to be in quotes? Ok, I know why technically - they're just strings, and JSON strings need to be in quotes, because they need to be embeddable in JavaScript code. But this is a classic case of a vestigial artifact which has a detrimental effect in a new environment. Nobody should be evaling JSON as just another chunk of Javascript anyway, for obvious security reasons. And in the wider world of JSON use cases following Javascript synax is completely irrelevant.

YAML seems to have a lot advantages over JSON as a rich textual format. For instance, it has minimal use of quotes, and a richer, extensible set of datatypes including timestamps and binary (WKB, anyone?). But it's going to be pretty hard to dislodge JSON, which is solidly entrenched for all the wrong reasons.

Improving DoubleDouble performance with self-modifying methods

2010-06-15T22:08:00.000-07:00

In a previous post I discussed how the DoubleDouble extended-precision API provides more robust computation for the Delaunay inCircle test. Quite rightly there were questions about the performance impact of using DoubleDouble. Of course, there is a performance penalty, but it's not as large as you might think, since the inCircle computation is only a portion of the cost of the overall Delaunay algorithm . For larger datasets the performance penalty is about 2x - which seems like an acceptable tradeoff for obtaining robust computation.

But after a bit of thought I realized that there was a simple way to improve the performance of using DoubleDouble. I originally designed the DoubleDouble API to provide value semantics, since this is a 100% safe way of evaluating expressions. However, this requires creating a new object to contain the results of every operation. The alternative is to provide self-modifying methods, which update the value of the object the method is called on. In many arithmetic expressions, it's possible to use self-methods for most operations. This avoids a lot of object instantiation and provides a significant performance benefit (even with Java's ultra-efficient object allocation code).

I added self-method versions of all the basic operations to the DoubleDouble API. While I was at it I threw in operations which took double arguments as well, since this is a common use case and allows avoiding even more allocations (as well as simplifying the code). The self-methods are all prefixed with the word "self", to make them stand out since they are potentially dangerous if used incorrectly. (I suppose a more Java-esque term would be "this-methods", but in this case the Smalltalk argot seems more elegant).

I also decided to rename the class to DD, to improve the readability of the code. Another enhancement might be to shorten the method names to 3 characters (e.g. "mul" instead of "multiply").

As an example, here's the inCircle code in the original implementation and using the improved API. Note the use of the new DD.sqr(double) function to improve readability as well as performance.

Original code


public static boolean isInCircleDDSlow(
 Coordinate a, Coordinate b, Coordinate c,
 Coordinate p) {
DD px = DD.valueOf(p.x);
DD py = DD.valueOf(p.y);
DD ax = DD.valueOf(a.x);
DD ay = DD.valueOf(a.y);
DD bx = DD.valueOf(b.x);
DD by = DD.valueOf(b.y);
DD cx = DD.valueOf(c.x);
DD cy = DD.valueOf(c.y);

DD aTerm = (ax.multiply(ax).add(ay.multiply(ay)))
   .multiply(triAreaDDSlow(bx, by, cx, cy, px, py));
DD bTerm = (bx.multiply(bx).add(by.multiply(by)))
   .multiply(triAreaDDSlow(ax, ay, cx, cy, px, py));
DD cTerm = (cx.multiply(cx).add(cy.multiply(cy)))
   .multiply(triAreaDDSlow(ax, ay, bx, by, px, py));
DD pTerm = (px.multiply(px).add(py.multiply(py)))
   .multiply(triAreaDDSlow(ax, ay, bx, by, cx, cy));

DD sum = aTerm.subtract(bTerm).add(cTerm).subtract(pTerm);
boolean isInCircle = sum.doubleValue() > 0;

return isInCircle;
}

Improved code


public static boolean isInCircleDDFast(
 Coordinate a, Coordinate b, Coordinate c,
 Coordinate p) {
DD aTerm = (DD.sqr(a.x).selfAdd(DD.sqr(a.y)))
   .selfMultiply(triAreaDDFast(b, c, p));
DD bTerm = (DD.sqr(b.x).selfAdd(DD.sqr(b.y)))
   .selfMultiply(triAreaDDFast(a, c, p));
DD cTerm = (DD.sqr(c.x).selfAdd(DD.sqr(c.y)))
   .selfMultiply(triAreaDDFast(a, b, p));
DD pTerm = (DD.sqr(p.x).selfAdd(DD.sqr(p.y)))
   .selfMultiply(triAreaDDFast(a, b, c));

DD sum = aTerm.selfSubtract(bTerm).selfAdd(cTerm).selfSubtract(pTerm);
boolean isInCircle = sum.doubleValue() > 0;

return isInCircle;
}

The table below summarizes the performance increase provided by using self-methods for inCircle. The penalty for using DD for improved robustness is now down to only about 1.5x slowdown.

Timings for Delaunay triangulation using inCircle predicate implemented using double-precision (DP), DoubleDouble (DD), and DoubleDouble with in-place operations (DD-self). All times in milliseconds.

# pts	DP	DD-self	DD
1,000	30	47	80
10,000	334	782	984
10,000	7953	12578	16000

Improvements to robustness in JTS Delaunay Triangulation

2010-06-09T15:50:00.000-07:00

JTS 1.11 added the capability to compute Delaunay Triangulations of point sets. Although the triangulation code was extensively tested and used prior to release, it unfortunately didn't take long before someone uncovered a robustness issue. The problem occurred in a large dataset of over 288,000 points. When the JTS 1.11 Delaunay algorithm was run against this data, a TopologyException was thrown, preventing the computation from completing.

Here's a portion of the dataset which produced the problem:

Digging into the code , it turned out (not unexpectedly) to be caused by a robustness failure in the inCircle predicate. InCircle is a key test used in Delaunay triangulation. The standard algorithm for computing it involves determining the sign of the determinant of a 4x4 matrix.

This computation is notoriously prone to robustness failure when evaluated using double-precision arithmetic. The rounding errors inherent in using double-precision can cause the sign of the determinant to be computed incorrectly. (For an good explanation of the issue see this page by Jonathan Shewchuk.)

As a concrete example, consider testing whether the point

POINT (687958.13 7460720.99)

lies in the circumcircle of the triangle

POLYGON ((687958.05 7460725.97, 687957.43 7460725.93, 687957.58 7460721, 687958.05 7460725.97)

Visually this looks like:

Zooming in, you can see that the query point is NOT in the circumcircle, so that InCircle()=FALSE.

However, evaluating the inCircle predicate determinant using double-precision computes InCircle()=TRUE. This is because the large magnitude of the ordinate values relative to the size of the triangle causes the significant information to be lost in the roundoff error. The effect of this error propagates through the Delaunay algorithm. Ultimately this results in a convergence failure which is detected and reported.

Luckily, a solution was immediately to hand, in the form of the DoubleDouble extended-precision library I ported to Java a while ago. Re-implementing the predicate evaluation using DoubleDouble computed the correct results for inCircle in all cases. This eliminated the robustness failure, and allowed the Delaunay Triangulation of the entire 288K point dataset to be computed without errors (for the record, this took 5 min 20 s).

The DoubleDouble code had been a solution in search of a problem for quite a while, so I was happy to get to prove its usefulness in a real-world situation.

And the story doesn't end there - it gets even better...

More Random Points in JTS

2010-05-06T14:27:00.001-07:00

In my last post I talked about the request on the PostGIS list for a function to generate dot-density maps, and about a JTS class to implement it.

Currently the JTS implementation uses purely random points. Here's what a field of purely random points looks like:

As a few people pointed out, and as is obvious from the image, this doesn't look that great, since there tends to be a lot of clusters and blank areas. This doesn't give a very aesthetic effect when used for cartographic purposes.

So I experimented with a few other options.

Here's random points generated in a grid of cells (one point randomly located in each cell). Better, but there are still clusters and blank areas.

Following an idea by Paul Ramsey, here's a grid where the random points are located in circles centred on each grid cell. This is an improvementl, but still doesn't prevent points from ending up close together.

Next idea: use square cells, but add a "gutter" between each cell. No points are created in the gutter, ensuring that points cannot be closer than the gutter width. In this image the gutter width is 30% of the overall cell width.

Much better, I think. Although, as the gutter size increases, the underlying grid becomes apparent. Here's a 50% gutter:

Maybe's there's still improvements that can be made.... It would be nice to avoid the grid effect, and also to reduce the use of a gutter (which skews the density of the distribution).

As David William Bitner pointed out, these can all be restricted to polygonal areas by simply intersecting the point field with the polygon.

Random Points in Polygon in JTS

2010-05-06T09:50:00.001-07:00

Recently there was a thread on the PostGIS list about how to create "dot-density" maps. Essentially this involves creating a set of N randomly-placed points which lie within a given polygon.

JTS already has a lot of random shape creation functions provided in the TestBuilder (randomPoints, randomPointsInGrid, randomRadialPoints, randomRectilinearWalk, etc). But they aren't currently exposed as a class in the API. This seemed like a good use case to initiate the development of such a class.

So now JTS has a RandomShapeFactory class. The class allows setting an extent using either a rectangular Envelope or a polygonal geometry, and will create sets of N points within the defined extent.

Here's a screenshot of the TestBuilder showing the new function at work:

Update: it's been pointed out that what is really desired is to have the points evenly distributed through the polygon. This will take a bit more thinking... At least the API won't have to change much to support this.

Late night link roundup

2010-04-26T12:49:00.001-07:00

Here's a few interesting links that occupied my late-night browsing...

Facebook's Graph API: The Future Of Semantic Web?

This is interesting for two reasons. One is that this is a hardball play by Facebook to subvert many other sites whose business model is linking social networking to categories of cultural artifacts. The other is the implications for the Semantic Web. I'm not so sure that the latter is quite so easily accomplished, but perhaps the 80-20 rule will truly turn out to be key here.

Mahout 0.3: Open Source Machine Learning

Neat stuff. Pulls together some fascinating technologies like Hadoop and clustering techniques. Perhaps the best thing about this is the chance to learn more about how this stuff actually works in practice. It would be great if there's a spatial component to this.

Colt - a set of Open Source Libraries for High Performance Scientific and Technical Computing in Java. One more nail in the old "Java is too slow" canard.

Twitter heart JTS

2010-04-07T13:49:00.000-07:00

At least, that's what it looks like from their presentation on Handling Real-Time Datastreams at the recent Where 2.0.

They note that JTS does not have support for GeoRSS or GeoJSON. Actually there is a GeoJSON implementation sitting in the labs - but it really needs some funding to get it finished off (hint, hint, Twitter - what, you think this groovy open-source spatial stuff just codes itself?)

And as usual people have not noticed that the real source for JTS information is on the new home page and the Sourceforge site - not this stale web page. Sigh... if only URLs had expiry dates.

Google heart JTS

2010-03-10T14:54:00.001-08:00

... and a bunch of other OSS spatial tools and goodies, too, of course.

More Open-Source Geocoders

2010-03-09T17:39:00.000-08:00

To continue my previous post on open-source geocoders, here's a few more geocoding projects we've reviewed here at Refractions:

PAGC Postal Address GeoCoder ( ) is "a library and a CGI based web service written in ANSI C that uses an address-ranged street network shapefile". It uses a rule-based parser based on the Aho-Corasick string searching algorithm. The parser rules are user-configurable, which is nice (although the rule format is NON-user-friendly, consisting of opaque lists of integers!). Exact match, Soundex and Edit distance are used in the matching phase. Supported reference road networks include both the TIGER and the StatsCan networks. BerkeleyDB is used as the reference network data store.

The USC WebGIS Geocoder provides a free, size-limited geocoding service. It claims to be open source, however links to the source code are not obviously provided. It is documented as using a "rule-based parser", but it's not clear how a user could actually customize this and run their own instance. Matching uses attribute relaxation, substring matching, and Soundex. The reference dataset appears to be TIGER, stored in a MS SQLServer database.

The FEBRL Geocoder is a well-researched, well-documented system implemented in Python. It targets Australian road network data. It specifically does not attempt to work with North American data (but suggests that the address models are close enough that this would be possible.) The address parser is unique in using a trainable Hidden Markov Model, and also in being documented by a series of academic papers (e.g. [1] ) describing the approach in detail. An address cleaning module is supplied. Matching uses exact or "approximate matching".

The OpenGeocoder initiative appears to be a worthy attempt to create a geocoder under the auspices of OpenGeo (possibly as a port of PAGC?). However, this project has not had much recent activity, and doesn't appear to provide any actual code.

One salient aspect of these systems is that they provide address parsing algorithms which are based on well-understood parsing theory. This is of particular interest for our geocoder project - of which more later.

References

[1] A probabilistic geocoding system utilising a parcel based address file; CHRISTEN Peter, WILLMORE Alan, CHURCHES Tim; Data mining : ( theory, methodology, techniques, and applications ), 2006

Open Source Geocoders

2010-03-06T13:30:00.000-08:00

One of the more interesting projects we have going on here at Refractions is to build a geocoder for use in a crime-mapping application we are developing for a client. We do have an existing geocoder codebase developed for another project. But we're not 100% happy with its performance and customizability, so we decided to look into developing a new library specifically for this project.

Of course the first thing we did was carry out a technology review of all the open-source geocoders we could find. Here's a list of all the ones we looked at:

Geo-Coder-US - A Perl module developed by the ubiquitous Schuyler Erle. "For geocoding US addresses, that is, estimating the latitude and longitude of any street address or intersection in the United States, using the TIGER/Line data set". Probably no longer being developed, since it has been superseded by

GeoCommons Geocoder::US - a rewrite of Geo-Coder-US into Ruby (and also requiring C and SQLite). "Although it is primarily intended for use with the US Census Bureau’s free TIGER/Line dataset, it uses an abstract US address data model that can be employed with other sources of US street address range data"

JGeoCoder - A Java API loosely modelled after Geo::Coder::US. Works against a SQL database loaded with TIGER data (an H2 image is supplied). Last activity in 2008.

Explorer GeoCoder by SRC - A C++ library for "a data and country independent geocoding engine" which can "assign latitude and longitude coordinates to any United States street address or intersection". Has an active mailing list.

Frost Tiger Geocoder by Stephen Frost et al - a Postgres SQL library for geocoding against TIGER data

(This is summarized in tabular form on this Tsusiat page).

Some observations:

All of the engines implement parsing and matching logic purely in code. None of them provide a declarative description language to allow easy modification of parsing, standardization, and matching rules. (To be fair, this is bit of a tall order. And it's not clear that it's even possible to provide an understandable declarative language for the fully general case. For example, the ArcMap geocoder (which appears to be the old MatchWare engine) provides a geocoding definition language (actually 5 different ones) - but the languages look scarily complex! Nonetheless, this is an important feature for easy of maintenance and customization.)
JGeoCoder uses a large number of complex regular expressions to perform parsing. This looks like it would be difficult to customize, due to the well-known opaqueness of large REs, and perhaps also to the relative inflexibility of the RE paradigm
The GeoCoder::US Ruby module seems to be the simplest code base. (I ended up almost understanding its parsing algorithm 8^) It uses REs, but in a saner amount. However, it's unclear how well it deals with erroneous input data, and how easy it would be to modify for a different address model.
The Explorer geocoder uses a large amount of fairly complex C++ code. It also looked quite challenging to understand and modify.
In all the projects the parser design appears to be fairly ad-hoc and poorly documented. This situation doesn't inspire confidence that it would be possible to modify the parser to support a different address model, or to handle particular kinds of input errors. (GeoCoder::US is a possible exception to this - it has a relatively simple parsing algorithm with at least some documentation).

In the end we decided not to use any of these projects. I'll talk about what we did do in another post.

JTS Version 1.11 released!

2010-03-01T21:47:00.000-08:00

JTS Version 1.11 is now available for download from SourceForge.

The version contains numerous enhancements, including

Delaunay triangulation and Voronoi diagrams
AWT Shape reading and writing
Geometry similarity metrics
support for Geometry densification
Numerous improvements to the JTS TestBuilder

Full release notes:

Functionality Improvements

Added CoordinateArrays.isRing
Added CGAlgorithms.signedArea(CoordinateSequence)
Added CoordinateArrays.copyDeep(...) method to copy sections of arrays
Added CoordinateList.add(Coordinate[], boolean, int, int) method to add sections of arrays
Added LineSegment.toGeometry(), LineSegment.lineIntersection()()
Added LineSegment.hashCode()
Added geometric similarity classes (HausdorffSimilarityMeasure, AreaSimilarityMeasure)
Added MinimumDiameter.getMinimumRectangle()
Added MinimumBoundingCircle class
Added Densifier class
Added triangulation API, including QuadEdgeSubdivision, IncrementalDelaunayTriangulator, ConformingDelaunayTriangulator and supporting classes
Added VoronoiDiagramBuilder to perform Voronoi diagram generation
Added scaleInstance(scaleX, scaleY, x, y) to AffineTransformation
Added AffineTransformationFactory to allow generating transformations from various kinds of control inputs
Added BinTree.remove() method
Fixed BinTree.query() to allow null interval arguments
Added ShapeReader API to convert Java2D Shapes into JTS Geometry
Added ShapeWriter API to convert JTS geometry into Java2D Shapes
Added FontGlyphReader API to render Java2D text font glyphs into geometry
Added SdeReader to jtsio library
Added Debug break methods
Added Memory utility for reporting memory statistics
Added ObjectCounter utility for counting objects
Added createSquircle and createSuperCircle to GeometricShapeFactory

Performance Improvements

Improved performance of Geometry.getArea() and Geometry.getLength() when used with custom CoordinateSequences

API Changes

Deprecated WKBWriter.bytesToHex in favour of WKBWriter.toHexto regularize and simplify method name

Bug Fixes

Fixed Point.isValid() to check for invalid coordinates (ie with Nan ordinates)
Fixed Geometry.distance() and DistanceOp to return 0.0 for empty inputs
Fixed Buffer to handle degenerate polygons with too few distinct points correctly
Added illegal state check in LineSegment.pointAlongOffset()
Fixed exception strategy in BufferSubgraph to handle certain robustness failures correctly
Fixed robustness problem in OffsetCurveBuilder in computing mitred joins for nearly parallel segments
Fixed minor bug in BufferInputLineSimplifier which prevented simplification of some situations
Fixed bug in BufferInputLineSimplifier which caused over-simplification for large tolerances
Fixed bug in Angle.normalizePositive to handle values > 2PI correctly
Fixed WKTWriter to emit correct syntax for MULTIPOINTs
Fixed WKTReader to accept correct syntax for MULTIPOINTs
CGAlgorithms.isCCW now checks for too few points in the ring and throws an IllegalArgumentException
Fixed bug in AffineTransformation#eqals (logic bug)
Fixed bug in CoordinateList#closeRing (cloning closing Coordinate)

JTS TestBuilder

Functionality Improvements

WKT input is cleaned automatically when loaded (illegal chars are removed)
Added WKT-Formatted option to Test Case View dialog
Many new geometry functions added
Geometry functions are displayed in tree
Geometry functions can be implemented as Java static class methods.
Geometry function classes can be loaded dynamically from command-line
Improved handling of very large geometry inputs and results
Threaded rendering allows display of very large geometries without limiting usability
Added Draw Rectangle tool
Added Drag-n-drop loading of .SHP files
Added Info tool to provide persistent display of geometry point/segment information
Added display of memory usage

JTS and Google App Engine

2010-02-17T10:10:00.000-08:00

Nice to see that JTS is officially certified as compatible with Google App Engine.

JTS makes clouds easy!

A few people have tinkered with running JTS in GAE (eg here and here). But the killer app has yet to emerge... How about a Java-based App Engine version of this?

JTS & Jython

2010-02-17T09:12:00.000-08:00

Sean's post suddenly made me realize that it might be really cool to have a nice set of Jython bindings for JTS (a la what Shapely has done for GEOS).

Now, of course Jython can call Java classes directly, so maybe this is an empty task. But perhaps there are some impedance mismatches which could be removed via some simple glue code. And it would be nice to provide some examples of Jython code using JTS, to make it easier for people to figure out how to get started.

And of course I'd throw in Proj4J as well!

One more thing for my ever-growing task list...

If anyone has any ideas on what needs doing here, I'd like to hear them.

(This also makes me think that both Jython and JTS need some cool logos... I don't have any pictures to post!)

Opposites attract?

2010-02-05T18:58:00.000-08:00

This sounds like

Fine Swiss shade-grown organic chocolate and rancid peanut butter from the big-box store discount aisle

HatBox for Derby and H2

2010-02-05T08:48:00.000-08:00

I just saw the HatBox spatial extension to Derby and H2. (Cute name - Derby, HatBOX - get it?)

And of course HatBox uses JTS!

This is great - H2 is a fantastic pure Java database, which has been crying out for spatial support. (Perhaps if this extension proves its worth it will be merged into the main H2 codebase at some point?)

However, HatBox is still a "user-space extension" - which means that it has not enhanced the SQL evaluation engine itself with knowledge about spatial indexes and when to use them. So to utilize spatial indexing you have to explicitly join to the spatial index table, which results in ugly SQL like this:


select ID, GEOM from T1 as t
inner join
HATBOX_MBR_INTERSECTS_ENV('PUBLIC','T1',145.05,145.25,-37.25,-37.05) as i
on t.ID = i.HATBOX_JOIN_ID

This is the same approach used in Sqlite and ESRI SDE and other spatial extensions which operate in user space rather than DB engine space (Mike Butler of SDBE fame used to call this "staying above the blood-brain barrier" 8^). Basically you are adding the index filter condition which for scalar indexes the SQL engine adds automatically.

In contrast, the "big boys" like PostGIS, Oracle, SQL Server, DB2, Informix, etc have actually extended their database engine to handle spatial datatypes and indexes. Most of these systems actually have provided a general extensibility mechanism which allows a clean separation between the engine core and the new datatypes. PostgreSQL is probably the one which takes this to the ultimate extent.

User-space spatial extensions are for a first approach, but it would be really nice to be able to play with the big boys and incorporate knowledge of spatial indexes and functions directly into the database engine. This should be easierto do in Java than in C - are you listening, H2?

SlashGeo'ed!

2010-02-02T17:42:00.000-08:00

Woohoo! I got SlashGeo'ed!

Tagged with cool icons as Software, Open Source, and - er - Geocoding?

Announcing Proj4J

2010-01-30T06:57:00.000-08:00

It's been a while since I posted anything, because like a true programmer I've been too busy cutting code to write about it. Time to catch up!

My main focus for a while has been working on a Java port of the popular PROJ.4 projection library. This was motivated by finding the great work that JHLabs started with his JavaProj port. That seemed too good to be left to languish, so I dusted it off and started to clean it up. The library is now known as Proj4J. It has been substantially reworked to provide a more functional API and a cleaner codebase. Various bug fixes have been made to the core projections (although more remains to do!), and a formal test suite has been added.

To answer the question of "Why another Java projection library?", the main reason is that PROJ.4 is popular, well-tested and well-documented, so it seems like a good idea to make it available in the Java world. Other goals include creating a small, easy-to-understand, easy-to-use library, which can be embedded and/or extended as desired by small projects. A personal goal is to provide coordinate system transformation services in JEQL (which is now realized by exposing Proj4J via JEQL functions).

OSGeo is hosting the codebase as part of the MetaCRS umbrella project. There it lives in the good company of Proj4JS, CS-MAP, spatialreference.org and of course PROJ.4.

The code is shaping up nicely for a 1.0 release. It can also be downloaded and used as it stands. Check it out! Even better, contribute some tests and bug fixes!

Wagner VII Projection

Why you should not sit on Wolfram Alpha

2009-10-02T15:18:00.000-07:00

Unqualified Reservations has a great post dissecting the Wolfram Alpha hubristic User Interface.

Warning: this guy seems to be able to write faster than most people can read. Browse his blog at your peril!

OS and GM SXS for LEJOG in the UK

2009-09-21T17:12:00.000-07:00

Translation: Ordnance Survey and Google Maps side-by-side for planning the Land's End-John O'Groats walk in the United Kingdom.

My friend Steve is walking the LEJOG in 2010 (I guess that makes him a LEJOGger - as opposed to the JOGLErs who go North to South). Of course he is blogging about it - doesn't everybody?.

Even better, he's planning his route using Where's The Path, which is a fantastic side-by-side map site for the U.K. It shows Ordnance Survey topographic maps and Google Maps imagery in a cleverly linked view (similar to the VExGM web site I blogged about earlier this year, but even more useful). Here's a link to the most famous location in Britain (but I suspect it doesn't feature in many LEJOG itineraries, unless you're a real anorak for walking).

WTP also lets you digitize paths and export them to GPX and KML. Steve is finding the KML export particularly useful, since it allows him to locate all the pubs along the route of his walk.

Now, when is someone going to do this for Canada? All those prospective SJV'ers out there would be overjoyed!

Earn a diploma with JTS!

2009-09-15T17:26:00.001-07:00

(No doubt by choosing that title I've exposed by my blog to death by spam filter. Although if the ones with titles like "Increase your performance with JTS!" got through, maybe I'm ok.)

The Kungliga Tekniska högskolan in Sweden (isn't Unicode wonderful?) is offering a course on GIS Architecture. I was happy to see that they're using JTS as a tool for exploring the DE-9IM spatial relationship model, and also as an example of a Open Source geospatial library.

JTS - Links to Geometry APIs and papers

2009-08-25T15:06:00.000-07:00

Motivated by a thread on the GEOS list about the Boost.Polygon library, I've added some new resources to the JTS web site, including:

a list of geometry APIs
a section of references to papers about topics in Computational Geometry which are relevant to JTS.

The resources have been factored out onto this page.

Over the years of working with JTS I've read a ton of interesting and sometimes even useful academic papers about aspects of Computational Geometry. I hope to start documenting these on this page, perhaps with some (no doubt opinionated) comments about applicability. A treasure trove for Geometry geeks!

Super Zoom Control is really super!

2009-08-19T17:15:00.000-07:00

The web mapping site 192.com has a very nice map zoom control which dynamically displays a representative image of the map at the prospective zoom level.

This nicely addresses a problem which has occurred in a few applications I've been involved with recently - how to communicate to the user what a given zoom level actually looks like.

At first I thought the control might be truly dynamic - i.e. pulling a live tile from the centre point of the current map view. But it's actually just a set of tile snippets at a fixed point. Still, it provides a very nice effect. (The dynamic version would be simple to implement, but perhaps would be too slow in actual use, with unpredicatable latency).

Are you listening, OpenLayers?

Visualizations of Sorting Algorithms in your browser

2009-08-06T10:16:00.000-07:00

Here's a nifty web page which shows a way of visualizing the operation of various common sorting algorithms.

Sample output for Heapsort:

The coolest thing about this of course is the ability to dynamically generate rich graphics in the browser. All hail the HTML5 <canvas> element!

Meme of the Month

2009-06-09T20:21:00.001-07:00

Well, it's obvious, innit?

You can be the first to write the Wikipedia article!

UML Sequence Diagrams on the Web

2009-05-15T21:23:00.000-07:00

I find the sequence diagram to be one of the most useful UML diagrams - but it's also one of the most fiddly & annoying to generate in a diagramming tool. There's a few reasons for that:

there's a large amount of implicit structure which is tedious to maintain
sequence diagrams quickly get complex for processes with lots of actors and/or actions
I can never remember all the conventions for representing concepts like alternation, loops and nesting

Luckily, the web to the rescue! The websequencediagrams website has a on-line diagram generator which uses a simple language to describe the diagram. This works well precisely because of the structure in sequence diagrams. Because they are inherently linear in structure, they are more constrained than other UML diagrams.

The language supports just about everything you might want - signal types, groups, nesting, notes, lifelines, etc. It outputs in images or as PDF - and it even has cool styles! Here's the idea:

loop 1000 times
Me->Visio: draw sequence diagram
Visio->Me: frustration
end
Me->Google: search for better way
Google->Me: find websequencediagram tool
Me->WebSequenceDiagram: draw sequence diagram
WebSequenceDiagram->Me: happiness!

produces

I've blogged about the appeal of specifying UML diagrams using code before. I'm not sure how much traction TextUML is getting - but it's hard to resist the appeal of a web interface, a simple language, and sexy ouput.

Now, if only someone would develop a force-directed web-based state diagram engine...

Note: there's some other alternatives to the websequencediagram tool - the author blogs about them here. The most interesting from my point of view is sdedit, which is open-source and Java-based. It's more powerful, but the language looks a mite complex. (Too bad there's no standard language for describing UML - maybe the Three Amigos should skip a siesta and whip one up.)

Voronoi Diagrams in JTS 1.11

2009-05-04T16:37:00.000-07:00

As is well-known, the Voronoi diagram (or tesselation) is the dual of the Delaunay triangulation. So the new Delaunay Triangulation code in JTS has a natural extension to computing Voronoi diagrams. Thanks to the quad-edge data structure underlying the Delaunay algorithm this was relatively trivial to implement, after a few design issues were sorted out (such as:

efficiently enumerating all vertices in the QuadEdge data structure which provides the basis for Delaunay computation
computing the circumcentre of all Delaunay triangles in a consistent way
clipping the generated Voronoi cell polygons to a reasonable bounding area)

Some examples on randomly-generated point sets:

Delaunay and Voronoi diagrams of 20 points (15 ms)

Voronoi diagram of 100 points (63 ms)

Voronoi diagram of 100,000 points (7.3 sec)

The JTS implementation scales very well - a Delaunay/Voronoi diagram of 1 million points computes in under 5 minutes. The one downside is memory usage. As usual, Java is quite memory-hungry - a 1 M point Delaunay takes around 700 MB. This seems excessive, even for Java. Hopefully some memory profiling may reveal that this can be reduced by some tuning of the class structures involved.

Even better, the Delaunay/Voronoi algorithm seems to be quite robust, even though no special attempt has been made to provide high-precision or otherwise robust implementations of some of the key predicates (inCircle and orientation). This may yet prove to be an issue for some inputs, but at this point it seems possible to claim that for non-pathological inputs the algorithms execute correctly.

Delaunay Triangulation in JTS 1.11

2009-04-30T14:15:00.000-07:00

The next version of JTS (1.11) will include an API for creating Delaunay triangulations and Conforming Delaunay triangulations. For a thorough explanation of the differences between Delaunay, Conforming Delaunay, and Constrained Delaunay, and why they are actually quite difficult to compute, see Jonathan Shewchuk's wonderful web site. [Side note - yet another B.C.-grown spatial dude - must be something in the water up here!]

This Delaunay implementation arose out of the work I did on automated watershed extraction using a system called WaterBuG a while back. It's taken a while to make its way into JTS because there's quite a bit of work involved in turning a codebase targeted at a very specific project into a clean, user-friendly API. Not to mention writing documentation...

But it's there now, and I'll be interested to see if it's of use to JTSer's. There seems to be a sudden surfeit of Delaunay and CDT Java libraries (see here, here, here, here and here), so I make no claims that the JTS one is best-of-breed. But hopefully having a decent implementation easily accessible and embedded in a general-purpose library will meet some needs. Also, my hope is that it will serve as the basis for further algorithms in JTS (such as the much-sought-after Concave Hull!).

Here's some screenshots showing the triangulation API at work:

The input points and constraint segments:
The Delaunay triangulation (notice that triangle edges cross some of the longer constraint edges):
A conforming Delaunay triangulation (the triangulation edges are now faithful to the constraint edges):

Web Monkeys with Laserbeams like JTS

2009-03-04T13:14:00.000-08:00

...As they explain in this blog post about using JTS to simplify a polygonal coverage.

The really sweet thing is that not only do the Web Monkeys have laser beams, but also honkin' big computers as well. The post states that they use 7 GB of memory to process 41,000 polygons in a single batch (as is required for the simplification algorithm that they're using). I inquired and found out that they're using:

java version "1.6.0_11"
Java(TM) SE Runtime Environment (build 1.6.0_11-b03)
Java HotSpot(TM) 64-Bit Server VM (build 11.0-b16, mixed mode)

Niice... I've always wanted to experiment with large memory space for JTS processing, for things like large overlays, large TIN building, etc. So far I haven't had a machine large enough to let me try. But it sounds like 64-bit Java "just works", as expected. Another great reason for coding to a JVM - 64-bit memory space support with no recompilation!

GM and VE side-by-side and head-to-head

2009-03-03T10:55:00.000-08:00

Here's a nifty page which shows GM and VE side-by-side, with slaved navigation. It's quite handy for seeing differences in map rendering and imagery.

For my area of interest (Victoria B.C.) my 20-second appraisal is that they both have aspects of their rendering which are better than the other; and VE's imagery coverage is more limited than GM's (probably due to this deal).

More on Database Thawing

2009-01-13T10:58:00.000-08:00

I just saw this blog post in rebuttal to Martin Fowler's DatabaseThaw article. It's a typically well-thought out response from Typical Programmer. The short summary is that he rejects Fowler's criticism of using RDB's as the mechanism for application integration. (And don't dismiss him as simply a RDB bigot - he's not shy about nailing relational gurus, as in Relational Database Experts Jump The MapReduce Shark).

TP's arguments ring true to me, although in my experience it takes a very concientious DB shop to fully maintain the "encapsulation of data and operations" across many applications, many custodians, and many developers.

It would be great if Fowler's vision of the integration point being HTTP rather than SQL solved all our problems. Loose coupling is a wonderful thing to have. But so far I'm not seeing how this provides equivalent performance for all cases, and how it avoids the problem of data model mismatch.

Is Global Database Warming happening?

2009-01-09T17:22:00.000-08:00

Martin Fowler has a great bliki^TM post on DatabaseThaw. The soundbite is something like "What happens after relational DBs?". He has some interesting links to things like Drizzle.

His opinon of relational DBs is that

their dominance is due less to their role in data management than their role in integration

This makes sense, but I think they also have offered the benefit of providing a fairly powerful, standard way of modelling and querying data. Over the lifetime of this technology this has fought off some powerful challengers, notably object-oriented data modelling. (Although perhaps this battle was only won by becoming more like the "loser"). The latest challenger is semantic data modelling (RDF, SPARQL, etc). Perhaps the world is ready to make this transition - although I'm not rushing to sell my Oracle stock.

He also makes a good point that the focus of integration is shifting from the DB to the Web. Hard to argue with this... the clouds are moving in!

Computing Geometric Similarity

2009-01-08T06:21:00.000-08:00

The GEOS team is working on porting the JTS CascadedPolygonUnion algorithm. Reasonably enough they asked whether there were unit tests that they could use to check the correctness of their code. I was a bit dismayed to realize that in fact there weren't any unit tests for this class (although having used the code extensively I'm pretty confident that it's correct.)

So fine, some unit tests are needed. This should be easy, right? Just create or obtain some polygonal datasets, union them using both CascadedPolygonUnion (fast) and Geometry.union (slow), and compare the results.

But there's a catch (in geometric processing there usually is). Due to rounding effects, there's no guarantee that the results of the two algorithms will be vertex-by-vertex identical. Of course, they should be very, very similar... but how to check this?

In geometry processing it's usually much harder to test "similar" than it is to test "exact", and this case is no exception. In fact, there's many different tests that could be used, depending on how you want to define "similar". In the context of unit tests, similarity testing is essentially checking for discrepancies which might be introduced into a theoretically correct result. So the tests to use may depend on the operation(s) that are being performed, since different kinds of algorithms can produce different kinds of discrepancies. A further issue which needs to be considered is to detect gross differences which might result from catastrophic algorithm failure.

So now the task is to write a SimilarityValidator for geometries. For polygons there's various characteristics which can be compared:

A simple thing to do is to compare basic quantities like the area and perimeter length of the polygons. Paradoxically, these are good for detecting small discrepancies, but not for detecting gross ones (e.g. two identical rectangles which are offset by a large distance)
One obvious thing to do is to compute the symmetricDifference of the polygons and inspect the area of the result. This has a couple of issues. One is what area tolerance to use? A more serious issue is that the symmetric difference operation is itself an approximation to an exact answer. This is especially true in situations where the inputs are very close - which is exactly the situation we are trying to check! So there may be a certain lack of confidence that this is detecting all discrepancies
A more robust test is to compute the Hausdorff distance between the rings of the polygons. This allows expressing the tolerance in terms of distance, which is more intuitive. It's also fairly robust and easy to confirm the answer. There's a challenge in developing an efficient Hausdorff algorithm - but that's a topic for another blog post.
Other tests might include comparing structural things like comparing the number of rings in the polygons.

Hausdorff Distance between two polygons

With this validator written and some test datasets run I can finally confirm that CascadedPolygonUnion actually works!

JTS Version 1.10 released

2009-01-02T12:32:00.000-08:00

I'm happy to announce that after a long gestation JTS 1.10 has been released. (This is my contribution to help fulfill James Fee's prediction 8^)

The package is available on SourceForge here.

There are numerous enhancements in this version. The highlights are:

Dramatic improvements to buffer performance, robustness and quality
Moving the GML I/O classes into the core library, and provided more control over the emitted GML
numerous bug fixes and performance improvements.

The full list of changes is:

Functionality Improvements

Added Geometry.reverse() method for all geometry types
Added setSrsName, setNamespace, setCustomRootElements methods to GMLWriter
Added Envelope.getArea method
Added copy, copyCoord methods to CoordinateSequences
Added area method to Envelope
Added extractPoint(pt, offset) methods to LengthIndexedLine and LocationIndexedLine
Added CoordinatePrecisionReducerFilter
Added UnaryUnionOp(Collection, GeometryFactory) constructor to handle empty inputs more automatically
Added DiscreteHausdorffDistance class
Made LineMerger able to be called incrementally
Added GeometricShapeFactory.createArcPolygon to create a polygonal arc
Enhanced Geometry.buffer() to preserve SRID

Performance Improvements

Improved performance for EdgeList (by using a more efficient technique for detecting duplicate edges)
Improved performance for ByteArrayInStream (by avoiding use of java.io.ByteArrayInputStream)
Unrolled intersection computation in HCoordinate to avoid object allocation
Improved performance for buffering via better offset curve generation and simplification.
Improved performance for IsValipOp by switching to use STRtree for nested hole checking

Bug Fixes

Fixed Geometry.getClassSortIndex() to lazily initialize the sorted class list. This fixes a threading bug.
Fixed RectangleContains to return correct result for points on the boundary of the rectangle
Fixed error in com.vividsolutions.jts.simplify.LineSegmentIndex which caused polygons simplified using TopologyPreservingSimplifier to be invalid in certain situations
Fixed error in DouglasPeuckerSimplifier which caused empty polygons to be returned when they contained a very small hole
Fixed PackedCoordinateSequence to return NaN for null ordinate values
Fixed Geometry.centroid() (CentroidArea) so that it handles degenerate (zero-area) polygons
Fixed Geometry.buffer() (OffsetCurveBuilder) so that it handles JOIN_MITRE cases with nearly collinear lines correctly
Fixed GeometryFactory.toGeometry(Envelope) to return a CW polygon
Fixed UnaryUnionOp to correctly handle heterogeneous inputs with P/L/A components
Fixed UnaryUnionOp to accept LINEARRINGs
Fixed CentroidArea to handle zero-area polygons correctly
Fixed WKBWriter to always output 3D when requested, and to handle 2D PackedCoordinateSequences correctly in this case
Fixed NodedSegmentString to handle zero-length line segments correctly (via safeOctant)
Cleaned up code to remove unneeded CGAlgorithms objects
Fixed GeometricShapeFactory.createArc to ensure arc has requested number of vertices

API Changes

Moved GML I/O classes into core JTS codebase
Changed GMLWriter to not write the srsName attribute by default
In DistanceOp switched to using nearestPoints method names
Exposed STRtree.getRoot() method

JTS TestBuilder

UI Improvements

Added ability to read GML from input panel
Added GML output to View dialog
Added file drag'n'drop to Geometry Input text areas
Add display of computation time
Added Stats panel
Added Scalar functions panel, with extensible function list
Added Save as PNG...

JTS TestRunner

Functionality Improvements

Added -testCaseIndex command-line option

OGRS 2009: International Opensource Geospatial Research Symposium

2008-12-15T10:24:00.000-08:00

Via the OpenJUMP list comes this notice of the OGRS 2009: International Opensource Geospatial Research Symposium conference in Nantes, France.

France and Australia in one year sounds like a pretty good training plan to me!

KML Pie Charts in JEQL

2008-11-28T15:43:00.000-08:00

Pie Charts are a nice way of displaying thematic visualization in Google Earth. They're also a good test of the chops of a KML generator. So naturally I was keen to see how to produce pie charts with JEQL.

For simplicity I decided to make my test statistic an orthographic comparison of the names of countries, showing the relative length of the country names and their vowel/consonant distribution. (This wasn't because this is a particularly interesting statistic, but it uses easily available data and exercises some of the data processing capabilities of JEQL).

The solution ended up using lots of existing capabilities, such as splitting multigeometries, regular expressions, JTS functions such as interior point, boundary and distance, and of course generating KML with extrusions and styling. The only new function I had to add was one to generate elliptical arc polygons - which is a good thing to have.

The results look pretty snazzy, I think - and would be even better with more meaningful data!

Wordlicious

2008-11-04T09:02:00.001-08:00

After seeing this post on Wordle, I had to try it....

and there's no stopping at just one...

Nostalgic Trivia

2008-10-21T03:12:00.000-07:00

When I was but a wee nerdling, I took a course taught by a grizzled veteran of the computer industry. I can no longer remember the subject matter of the course, but I do remember that at one point he referred to the main players in the computer business as "IBM and D'BUNCH". D'BUNCH were DEC, Burroughs, Univac, NCR, Control Data, and Honeywell. (And yes, I had to resort to Wikipedia to remember all these names.)

The moral of the story? Computer manufacturers come and go, but IBM remaineth eternal, apparently.

Dating myself even more, in the early part of my career I used machines made by the first 3 of these. The Univac had the distinction of having the most obtuse, unwieldy, difficult-to-use OS I have ever encountered. DEC, in contrast, had the best OS (of proprietary ones, that is - *nix blows 'em all away).

Untangling REST

2008-10-20T15:59:00.001-07:00

Thanks to Sean I just learned about Roy Fielding's blog.

I don't know why it never occurred to me that Roy Fielding would have a blog, and it would likely to be a good source of commentary on the evolving philosophy of the Web, but it didn't. He does, and sure enough it's chock full o' goodness.

Highlights include this post about how to efficiently build a RESTful Internet-scale event notification system for querying Flickr photo update events - using images as bitmap indexes of event timeslices! Or the post which Sean noted, along with this one - both cri-de-coeurs about the pain of seing the clean concept of REST muddied to the point of meaningless.

Anyone confused about REST would do well to avoid inhaling too much smoke and get a dose of fresh air from the source...

Improvements to JTS buffering

2008-10-07T21:08:00.000-07:00

By far the most difficult code in JTS to develop has been the buffer algorithm. It took a lot of hard graft of thinking, coding and testing to achieve a solid level of robustness and functionality. There have been a couple of iterations of improvements since the first version shipped, but the main features of the algorithm have been pretty stable.

However, it was always clear that the performance and memory-usage characteristics left something to be desired. This is particularly evident in cases which involve large buffer distances and/or complex geometry. These shortcomings are even more apparent in GEOS, which is less efficient at computation involving large amounts of memory allocation.

I'm pleased to say that after a few years of gestating ideas (really! - at least on and off) about how to improve the buffer algorithm, I've finally been able to implement some enhancements which address these problems. In fact, they provide dramatically better performance in the above situations. As an example, here are timing comparisons between JTS 1.9 and the new code (the input data is 50 polygons for African countries, in lat-long):


Buffer
Distance     JTS 1.9    JTS 1.10

0.01        359 ms     406 ms
0.1        1094 ms     594 ms
1.0      16.453 s     2484 ms
10.0     217.578 s     3656 ms
100.0     728.297 s      250 ms
1000.0    1661.109 s      313 ms

Another tester reports that a buffering task which took 83 sec with JTS 1.9 now takes 2 sec with the new code.

But wait, there's more! In addition to the much better performance of the new algorithm, the timings reveal a further benefit - once the buffer distance gets over a certain size (relative to the input), the execution time actually gets faster. (In fact, this is as it should be - as buffer distances get very large, the shape of the input geometry has less and less effect on the shape of the buffer curve.)

The algorithm improvements which have made such a difference are:

Improved offset curve geometry - to avoid some nasty issues arising from arc discretization, the original buffer code used some fairly conservative heuristics. These have been fine-tuned to produce a curve which allows more efficent computation, while still maintaining fidelity of the buffer result
Simplification of input - for large buffer distances, small concavities in the input geometry don't affect the resulting buffer to a significant degree. Removing these in a way which preserves buffer distance accuracy (within tolerance) gives a big improvement in performance.

A nice side effect of this work is the development of a solid methodology for validating buffers, and a thorough test suite for correctness, robustness, and performance.

This code will appear in JTS 1.10 Real Soon Now.

Java Power Tools cuts straight and true

2008-08-22T15:43:00.000-07:00

Part of my summer holiday reading is the book Java Power Tools, by John Ferguson Smart.

I count a computer book a good buy if I get one new idea from it; two is stellar; and three or more goes on my "Recommend to Colleagues" list. This one is on the list... Ideas I`ve picked up include:

the XMLTask extension for Ant, that provides easy and powerful editing of XML files. This should make configuring things like web.xml and struts-config.xml a lot easier. It even provides a way to uncomment blocks of XML markup.

SchemaSpy, which generates database documentation (including ER diagrams!) from JDBC metadata. The tool also also comes with profiles for interpreting some vendor-specific metadata. It will be interesting to see how it handles spatial datatypes in Oracle and PostGIS...

using Doxygen to generate documentation for Java source. Doxygen provides more capabilities than Javadoc, including UML diagrams and a variety of output document formats.

UMLGraph also allows generating UML diagrams from Java source, and embedding them directly in Javadoc.

For graph visualization, SchemaSpy, Doxygen and UMLGraph all use the GraphViz application. This looks like a great tool in its own right. It provides a DSL for specifying graph structures and node and edge symbology, along with a layout and rendering engine which outputs to numerous different formats.

JPT of course covers all the better-known tools such as Ant, Maven, CVS, SVN, JUnit, Bugzilla, Trac, and many others. It doesn`t replace the documentation for these tools, but it does give a good comparative overview and enough details to help you decide which ones you`re going to strap around your waist for the next project.

Be the most popular tile on your block

2008-08-15T19:38:00.000-07:00

You might think that the image below is a map of North America population density. You'd be off by one level of indirection...

In fact it's a heat map of the access frequency for Virtual Earth map tiles.

So really it's not an image of where people are, but where they want to be...

The image comes from a paper out of Microsoft Research: How We Watch the City: Popularity and Online Maps, by Danyel Fisher.

Makes me wonder if there are tiles that have never been accessed. Like perhaps this one? (It took a looong time to render....)

And what is the most-accessed tile? This one, perhaps?

Revolution is Happening Now

2008-08-14T22:47:00.000-07:00

This great graph shows why we're all going to wrassling with parellelization for the rest of our coding lives:

Source: Challenges and Strategies for High End Computing, Kathy Yelick

Also see this course outline for an sobering/inspiring view of where computation is headed.

Krusty kurmudgeon Knuth kans kores & kommon kode

2008-08-04T16:01:00.000-07:00

Andrew Binstock has an interesting interview with Don Knuth.

Professor Knuth makes a few surprising comments, including a low opinion of the current trend towards multicore architectures. Knuth says:

To me, it looks more or less like the hardware designers have run out of ideas, and that they’re trying to pass the blame for the future demise of Moore’s Law to the software writers...

But then he goes on to admit:

I haven’t got many bright ideas about what I wish hardware designers would provide instead of multicores...

Which seems to me to make his complaint irrelevant, at best. (Not that I don't sympathize with his frustration about banging our heads against the ceiling of sequential processing speed. And as the sage of combinatorial algorithms he must be more aware than most of us about the difficulties of taking advantage of concurrency.)

Another egregious Knutherly opinion is that he is "biased against the current fashion for reusable code". He prefers what he calls "re-editable code". My thought is that open source gives you both options, and personally I am quite happy to reuse, say, the Java API rather than rewriting it. But I guess when most of your code is developed in your own personal machine architecture (Knuth's MIX) then it's a good thing to enjoy rewriting code!

In the end, however, I have to respect the opinions of a man who has written more lines of code and analyzed more algorithms than most of us have had hot dinners. And I still place him in the upper levels of the pantheon of computer science, whose books all programmers would like to have seen gracing their shelves - even if most of us will never read them!

And yes, this post is mostly an excuse for some korny alliteration - but the interview is still worth a read. (Binstock's blog is worth scanning too - he has some very useful posts on aspects of Java development.)

Quote of the Day

2008-07-21T12:09:00.000-07:00

Love him or hate, you have to admit that John Dvorak gives good copy:

Vista is essentially the old hooker with a bad facelift and too much makeup. She also can't remember her customers

Database design tips for massively-scalable apps

2008-06-24T10:27:00.000-07:00

Here's an interesting post on design practices for building massively-scalable apps on database infrastructure such as Google BigTable.

The takeaway: this ain't your granpappy's old relational database system, so throw out everything he taught you. Denormalize. Prefer big fluffy things to small granular things. Don't bother with DB constraints - enforce the model in the application. Prefer small frequent updates to large page updates.

The good news (or bad, depending on how fed up you are with your local DBA) - don't bother with all this unless you intend to scale to millions of users.

GeoSVG, anyone?

2008-06-23T11:00:00.000-07:00

The GeoPDF format seems to be gaining traction these days. I have to admit, when I first heard of this technology I had the same reaction as James Fee - "What's it good for"? But I'm coming round... A live map with rich information content and a true geospatial coordinate system - what's not to like?

My excuse for such scepticism is my finely-honed technical bullsh*t reflex, which uses the logic of "If this is such a good, obvious, simple idea then why hasn't it been implemented ages ago?".

To be fair, there have been lots of SVG mapping demos, which fill the same use case and provide equivalent functionality. Sadly that concept hasn't really caught fire, though (perhaps due to the ongoing SVG "always a bridesmaid, never a bride" conundrum).

Of course, an idea this good is really too important to be bottled up in the murky world of proprietary technology. It seems like this area is ripe for an open standard. SVG is the obvious candidate for the spatial content (sorry, GeoJSON). What it needs is some standards around modelling geospatial coordinate systems and encoding layers of features. It seems like this should be quite doable. The goal would be to standardize the document format so that viewers could easily be developed (either stand-alone, as modules of existing viewers, or as browser-hosted apps). Also, the feature data should be easy to extract from the data file, for use in other applications.

Perhaps there's already an initiative like this out there - if so, I'd love to hear about it.

B.C. winter causes frost buckling in Google Earth

2008-06-02T16:45:00.000-07:00

The Google Earth imagery of Revelstoke Dam in B.C. (below) looks like it was taken in the depths of winter. Since this is a massive concrete dam, I'm guessing the frost buckling in the image is an artifact of the surface model. Maybe Google need to add some more antifreeze to their TIN algorithm... or perhaps light a twig fire under their rendering engine?

Database Architecture monograph

2008-05-01T09:09:00.000-07:00

In the era of cloud computing, map/reduce, dynamic languages and the semantic web, the stalwart Relational Database Management System is looking a bit fusty. But RDBMSes were perhaps the earliest widely-deployed example of many of the techniques of distributed computing, concurrent programming, and query optimization that are still highly relevant.

Hellerstein, Stonebraker and Hamilton have published a monograph on Architecture of a Database System. With names like that involved you'd expect high quality and some deep insight, and the article delivers. It's a good, accesible summary of the state-of-the-art in RDBMS technology.

JAQL pegs the cool technology mashup meter

2008-05-01T08:48:00.000-07:00

JAQL is a query language and engine which has XQuery-like syntax, SQL-like operators, JSON as a native data format, and runs using the Hadoop ma/preduce framework. (Although not mentioned explicitly, it's probably great for social networking as well...)

You might think that JAQL and JEQL were separated at birth, but they actually have no genetic material in common. But it's interesting to see the J*QL acronym space being rapidly populated. The best two vowels are now gone - who's going to be next to pile in?

Taxonomy of Software Bugs

2008-04-30T14:19:00.000-07:00

This software bug taxonomy is great! Heisenbugs, Bohr Bugs, and the dreaded Schroedinbugs....

Ted Nedward takes on the Tower of Babel

2008-04-29T16:01:00.000-07:00

Here's another (as usual) fascinating, detailed, doesn't-this-guy-work-for-a-living post from Ted Nedward. This one starts as a meta-critique of Groovy VS Ruby and morphs into an interesting summary of what the Tower Of Babel IT department is using this year.

Money quote:

I wish I could get back to [C++]for a project in the same way that guys fantasize about running into an old high school girlfriend on a business trip.

Personally, my reaction to my old C++ girlfriend would be "TG I didn't get hitched to this chick - she's way too high-maintenance". Although Ted says she's changed...

Microsoft's MVP's use... Google?

2008-04-20T22:31:00.000-07:00

An article about a candid presentation by Steve Ballmer.

The XP-versus-Vista debacle just reinforces the core value of Open Software. Current version tested, deployed, and working fine? Then nobody can force you to upgrade...

Who's conspicuously absent from the PaaS fray?

2008-04-18T22:45:00.000-07:00

Here's a hint: who was using the slogan "The Network is the Computer" 10 years ago? And who was the first company to deliver a RIA technology?

So why have they been MIA in the PaaS goldrush?

Let's think about this another way. What database are people most likely to run on their slice -o'Linux-in-the-cloud? mySQL perhaps? Which was just bought by...?

The Register has an article about a possible JavaOne announcement about how this situation might change (with a leaked slide presentation! Fell off the back of an ftp packet, I guess..)

(The weird thing is is that the presentation talks only about PostgreSQL. An old file? Or a different corporate camp? Didn't get the memo maybe?)

KML Craziness

2008-04-18T11:22:00.000-07:00

Why oh why did KML choose to specify colour values as ~~AGBR~~ ABGR rather than RGBA? Does anyone have a rational explanation for this anomaly?

Is that cloud on the horizon going to start raining applications?

2008-04-15T19:45:00.000-07:00

Timothy O'Brien speculates that the transition to cloud-based computing is happening sooner than expected. He's talking about the new integration between Salesforce.com (which is apparently the poster child for SaaS) and Google Apps (the poster child for desktop replacement by the Web). And he generalizes this to include EC2, SimpleDB, and the "twenty or thirty other companies that are going to join the industry".

He also warns here that this transition could transform the model for software development in ways uncomfortable for IT professionals.

He could be right. Cloud computing does seem to be poised to finally provide the right platform to suck the juice out of corporate data centres. The idea of virtual everything certainly has an appeal (especially to someone like me who is basically a software guy).

But questions occur... Salesforce and Google seem like a perfect match - but what about the other companies that want a piece of this action? Does it matter that you will have to commit everything to a given cloud platform? And what happens if that platform goes away? The more advantage you take of the cloud, the bigger the pain when it disappears. And what about apps which are a bit more specific than CRM (which in my naive view seems like just a fancy Contacts list - and hence an obvious and easy thing to integrate with an office suite).

Tim would probably call these kinds of questions "self-interested observations from one with the most to lose". He mentions a Salesforce meeting where business types applaud a sign showing "Software" with a big red slash through it... Well, maybe. Last I noticed no-one has quite managed to automate generating code from requirements documents (let alone automating the generation of implementable requirments documents out of people's heads 8^). So I would say it's more like "different software" than "no software".

One thing's for sure.. there's going to be some gigantic platform turf wars going on up there in the stratosphere.

(One big disappointment - it sounds like the Salesforce platform is based on their proprietary Apex language. Ugh. Just what the world needs - one more language to debate over. At least Google App Engine picked a real language for their launch!)

Ontogeny recapitulates Phylogeny in the life of a programmer

2008-04-04T10:56:00.001-07:00

(C'mon, admit it - you've always wanted to use that as the title of a blog post too...)

Paul's epiphany seems like the equivalent of Ontogeny recapitulating Phylogeny in the evolution of a programmer. "Hey, C has arrays! Hey, C arrays are really just syntactic sugar for pointer dereferencing! Hey, I can index to anywhere in memory really easily! Hey, I can store anywh...."

SEGFAULT - CORE DUMPED

Sh*t.

"Hey, there's this new language called Java! And it has arrays too! Hey, if I index past the end of an array I get a nice error message telling me exactly where in my code the problem occurred! Hey, I think I can knock off work early and go to the pub!"

8^)

JTS at the sharp end of many arrows

2008-03-28T17:29:00.000-07:00

Miguel Montesinos and Jorge Sanz from the gvSIG project have made a nice diagram showing the relationships between a bunch of GFOSS projects. It' s nice to see JTS close to the centre of the diagram - although having so many arrows pointed at it makes me a little nervous!

They show JTS having a dependency on Batik for some reason - that must be an error, there's no relationship between the two. Or does Batik use JTS?

It would have been nice to see a "parent-of" relationship between JTS and GEOS and NTS, since the latter two also form a key component of quite a few projects. And I'm pretty sure MapGuide OS uses GEOS, as does OGR.

But it's not surprising there's a few errors and omissions - it's a pretty complicated web of relationships. And this is over only what - 8 years? I wonder what the diagram will look like in another 8...

Time for JSTS?

2008-03-24T08:58:00.000-07:00

Like a lot of stuff, spatial functionality is moving out into the browser. Signs of the times:

proj4js
GeoJSON
This comment: "The DOJO client-side libraries provide support for performing some simple spatial operations like ‘intersection’ on the client-side." (Although I haven't been able to find this functionality in a quick browse of Dojo - can anyone confirm this?)

Seems like maybe the time is ripe for a port of JTS to JSTS - the Javascript Topology Suite.

Take it away, someone - I'm too busy!

Swimming taught by telephone

2008-03-22T21:25:00.000-07:00

Ok, this is like popcorn... you can't have just one.

Just think - they had no idea that one day you would be able to simply download a learn-to-swim podcast and listen to it on your waterproof MP3 player...

Has Automation affected YOUR job?

2008-03-22T21:16:00.000-07:00

Can't resist posting this (from Modern Mechanix).

I'm definitely enjoying not having grimy hands, but what happened to the shorter work week and more leisure time?

World Population Cartograms

2008-03-18T23:01:00.000-07:00

The Daily Green has some cartograms showing the change in distribution of world population since 1900.

But there's another aspect to this that the original images don't show - the increase in the absolute number of people in the world. So here's the images with that factor applied:

1900 - 1.65 B

2007 - 6.64 B

2050 - ~ 9 B

A good kick in the pants for the GeoWeb?

2008-03-18T15:49:00.000-07:00

Reading the blog posts that are starting to come out about the ESRI Dev Summit, I'm struck by a few things:

REST! KML! JSON! AJAX! Dojo! I haven't seen this many tech buzzwords out of ESRI since ArcGIS on Windows was released with COM! VBA! DLLs! Hopefully some of these have more legs
Clearly ESRI is embracing the GeoWeb concept with a vengeance. It will be very interesting to see how these new modes of access to GIS functionality plays out. To what extent will the marriage of web services and GIS processing be an effective model?
They also seem to be accepting Google Maps/Earth and MS VE as valid spatial delivery platforms. It sounds like there is some pretty full-featured capabilities to deliver data to these platforms. It's going to be interesting to see the uptake on these capabilities, and whether ESRI's heart is really in making these platforms perform to their full capability. No doubt there will be some fascinating business implications as well that get played out over time...
I'll be interested to see whether ESRI's "legitimizing" spatial-via-web-service will have any effect on the OGC W*S world. It seems to me that while OGC was early out of the gate with a web service suite, they seem to be wallowing in the doldrums as far as making the specs effective for real-world use. The OGC W*S suite was quickly adopted by the OSS world, and for good reason - open source tends to be very faithful to open standards, since a design goal is usually to have a high degree of interoperability. Not to mention that it's easier to code to a standard which has already done a lot of the hard thinking. But - the cool kids are losing interest in the crusty old W*S interfaces, since they're not keeping up with the rapid emergence of exciting new web paradigms.
Ultimately ESRI's trailblazing will be a good thing for OSS technologies. Nothing like having a working system to inspect, copy, and improve. And the more open, standard technologies that system uses, the easier it is to steal - um, learn from. Also, as the GIS stack gets more open interface technologies accepted, it becomes easier to plug in heterogeneous components into that stack.

Now to start looking into that ArcGIS Server REST API...

Tired of those boring old conformal map projections? Make your own!

2008-03-17T09:59:00.001-07:00

Flex Projector is an interesting tool that allows you to make a custom map projection by adjusting the location and shape of meridians and parallels.

Here's a nice projection I defined to maximise the area of tropical vacation spots 8^)

The downside of this app is that as far as I can tell, there's no way to export a projection once it's defined. Instead, you have to use the Flex Projector application to reproject datasets. So it doesn't look like you can make your own custom projection for use in say, PostGIS or OGR.

I guess it might be asking a little much for the app to spit out some custom Proj4 C code with an associated EPSG code and CRS WKT... But hey, it's an open source app, so come on someone - how about it?

Quote of the (Pi) Day

2008-03-14T08:55:00.000-07:00

Sir, I send a rhyme excelling
In sacred truth and rigid spelling
Numerical sprites elucidate
For me the lexicon's full weight

Maybe not the greatest lyric poem - but list the number of letters in each word. (If you prefer a shortcut this site has them already listed - along with 9, 979 more)

And notice the value of the date as MM.DD...

Branch-and-Bound algorithms for Nearest Neighbour queries

2008-03-03T21:26:00.000-08:00

This paper by Roussopoulos et al is a fine expositions of how to use a Branch-and-Bound algorithm in conjunction with an R-tree index to efficiently perform Nearest-Neighbour queries on a spatial database.

Nearest-neighbour is a pretty standard query for spatial database. Oracle Spatial offers this capability natively. It would be great if PostGIS did too. If the GIST index API offers appropriate access methods, it seems like it might not be too hard to implement the Roussopoulos algorithm. (How about it, Paul, now that you're dedicating your life to becoming a PostGIS coding wizard...)

I'm also thinking that this approach might produce an efficient algorithm for computing distance between Geometrys for JTS. It's always bugged me that the JTS distance algorithm is just plain ol' O(N^2) brute-force. It seems like there has to be a better way, but as usual there seems to be precious little prior art out there in web-land. This should also work well in the "Prepared" paradigm, which means that it will provide an efficient implementation for PostGIS as well. Soon, hopefully...

The Four Programmers

2008-02-17T08:35:00.000-08:00

Here's an amusing adaptation of Monty Python's Four Yorkshiremen sketch...

I feel increasingly like this myself (more so now that I'm in a company where I am the oldest employee)...

When I started coding we had to type out our programs on punchcards. If you made one typo you had to retype the entire card, so to avoid mistakes we wrote out our code on paper pads with 80-column grids. You had to stand in line to submit your card stack to the guy running the card reader, and then pick up your output once it had been separated and filed by some other guy. And if you had a syntax error - back to the cardpunch to do it all over again!

We thought we'd died and gone to heaven when we got online accounts and were allowed to use a hardcopy DecWriter terminal. It even had an APL character set (don't forget to change the charset when you switched back to FORTRAN). This was better - we could "erase" (actually just strikeout) and change mistakes on the line. But forget about printing out your entire program - at 300 baud this could take many minutes, which was all chewing up your connect time allocation.

But we had it lucky.. I worked with a guy who started out coding accounting routines for a magnetic drum-based system in the early 60's. A big chunk of their time was spent reordering the individual instructions around the drum to reduce read latency. Fun stuff!

And he was lucky compared to Don Booth, who was at the oceanographic research centre where I worked during my undergrad days. He was one of the pioneers of computing in Britain. All they had for storage was a 1000-word mercury delay tube... and no doubt they spent their coding time plugging wires and changing tubes.

But you try and tell kids with their touch-sensitive palmtops that these days, and they won't believe you...

The End of an Architectural Era?

2008-01-30T19:59:00.000-08:00

Stonebraker et al have an interesting paper pointing out the antiquity and consequent limitations of the classic relational database architecture in today's world of massive disk/cycles/core.

If they are correct (and in spite of the recent MapReduce blunder Stonebraker has made a lot of great calls in the DB world), the world of data management is going to get awfully interesting in the coming years. The DBA's & DA's of this world have been living a relatively comfortable existence compared to those who are wandering across the stormy badlands of the middle tier. But Stonebraker postulates at least 5 radically variant database architectures to address specific use cases of data management. This would seem to lead to a much more complex world for data architects. But maybe a windfall for the consultants who find their niche?

Quote of the Day

2008-01-20T21:48:00.000-08:00

Java - learn once, write anywhere

"From my personal experience, that is quite true. I started programming in Java in 1997, and since then I have built web applications, database applications, mobile applications for Palm and Pocket PC, an application server for CTI applications, CORBA-based distributed applications, network management applications, server-side business components for application servers, fat-client business applications, an IDE, a Rich Client Platform, a modeling tool among other kinds of software. All that across different operating systems and using similar products by different vendors.

Of course I had to learn something new for each kind of "application style", but the programming language and core class library were always there for me. That is a huge thing. Before Java, it was really hard to move from one domain to another, or even move from vendor to vendor. Sun has my eternal gratitude for bringing some sanity to the software development industry."

- Rafael Chavez

The Paradoxically Poor Power of Visual Programming

2008-01-20T21:00:00.000-08:00

I've just been reading about TextUML, which is a language and IDE for textually defining UML diagrams by a start-up company called abstratttechnologies.

This seems like both a stroke of brilliance and painfully obvious. It makes me wonder why UML isn't already defined in terms of a serializable language. The big advantage of this I think would be the ability to have a clearly defined semantics. In the past when reading about UML I've been quite frustrated by an apparent lack of rigour in the definition of the various UML concepts and diagrams. It's always seemed to me that a metalanguage like UML is more in need of fully-defined semantics than application languages. Most (all?) application languages after all are executable, which gives provides a final authority for the meaning of a program written in them - run it and see what happens. AFAIK UML isn't really (or not conveniently) executable in the same way.

Which brings me to the paradox promised in the title of this post. One of the claims for TextUML is that it is easier to write and express complex models in than a purely diagram-based UML tool. I can easily believe this - developing a complex model by diagrams seems cumbersome and limited compared to writing a textual description. And I think this generalizes to the concept of visual programming in general. We've had easy access to powerful graphics capabilities for over 20 years now, culminating in today's basically unlimited in graphical capabilities. In spite of this, text-base programming still rules the roost when it comes to expressiveness, flexibility and speed.

So the paradox is: why is a 1-dimensional representation more powerful than a 2-dimensional representation? To put this another way, why does a 1D representation seem less "flat" than a 2D representation?

For further study: would the same apply to a 3D representation? Or would a move to 3D jump out of some sort of planar well, and end up being more expressive than 1D?

By the way, abstratt is right here in l'il ol' Victoria, and the lead designer (and CEO) Rafael Chavez is giving a talk at VicJUG in March. I'm definitely going to attend - I suspect he may have an interesting take on this issue.