Monday, September 20, 2010

Voronoi Diagrams in PostGIS

(Update: A faster version of this code is here: Faster Voronoi Diagrams in PostGIS)

I found myself in a situation where I needed to create a Voronoi diagram from a set of points using PostGIS. This isn't built in, but a little googling turned up a function written by Mike Leahy. I adapted it and made it a bit more generic, so it shouldn't require any editing to make it work for many (most?) cases.

Call it as: select * from voronoi(table_name text,table_primary_key text,geom_col text)  as (id id_type, the_geom geometry)


For example:



select * from voronoi('oregon_cities', 'id', 'the_geom_centroids') as (id integer, the_geom geometry);


The 'as' clause is required because we don't know and don't want to assume what type your primary key might be. But, because we're returning a record type, the query planner wants to know what type to expect. If you're always using the same type, say an integer for your primary key, then it would be easy to define a type thusly:


create type my_type as (id integer, the_geom geometry);


Then change the code at line 24 from 'rec record;' to 'rec record%my_type;' and you will no longer need the 'as' clause.


Code at this URL: http://db.tt/aInuiJ2.  Enjoy.





Sunday, April 4, 2010

Pondering vector representations.

So one thing I've wondered is why more GIS systems can't/don't use B-splines, opting instead for simple lines. The OGC Simple Features standard defines a Curve, which must specify its method of interpolation between points, but then only defines one method – straight linear interpolation.

Obviously there are disadvantages to using b-splines, such as the assumption of accuracy which permeates so many people's interactions with GIS data. At least when you using simple linear features, as you move to a large scale map, you can see the clumsy straight lines that make up your data. But it sure would look nicer when outputting the same data to use B-splines.

Not being hugely math skilled anymore (woe for math atrophy), I'm not even sure how to go about answering the question. But some of the more interesting issues that bounce around in my mind are:

1) Do B-splines/bezíer curves even work in non-euclidean (in particular spherical) geometry?
1a) If they do, then how would one go about projecting them into a euclidean space – if one can meaningfully do so at all?
2) Assuming a "bezíer polygon" were defined as closed series of curves just like linear polygons, how would one calculate the area of said polygon?

Any math über-geeks out there in my vast (hah!) readership have any insights?