Smathermather's Weblog

Remote Sensing, GIS, Ecology, and Oddball Techniques

Voronoi in PostGIS

Posted by smathermather on December 21, 2013

PostGIS has for a time had ST_DelaunayTriangles for Delaunay Triangulation, and since 2.1 apparently can even natively create a 2.5D TIN using said function, which is pretty cool. I think with SFCGAL, we will eventually have true 3D TINs as well.

Overlay of Delaunay and Voronoi

We’re still waiting on native Vororoi support for PostGIS though. According to http://trac.osgeo.org/postgis/wiki/UsersWikiPostgreSQLPostGIS

“GEOS 3.5 is still in development but will have Voronoi which will be a feature in 2.2 only if you have GEOS 3.5.”

Vishal Tiwari through a Google of Summer of Code under the mentorship of Sandro Santilli completed the port of Voronoi to GEOS from JTS Topology Suite. Now we just need to wait for PostGIS 2.2….

In the mean time,

http://geogeek.garnix.org/2012/04/faster-voronoi-diagrams-in-postgis.html

One caveat– this python function doesn’t always provide just Voronoi but some artifact polygons.

Voronoi polygons with some artifacts

Once we have a table with Voronoi, we can filter out just the true Voronoi cells by counting the number of original points we find within them, and only return the polygons which contain a single point:

CREATE TABLE true_voronoi AS
WITH tvoronoi AS (
	SELECT COUNT(*), v.geom
		FROM voronoi v, input_points p
		WHERE ST_Intersects(v.geom, p.geom)
		GROUP BY v.geom
		)
SELECT the_geom FROM tvoronoi WHERE count = 1;

voronoi without extra polygons

But it’s still not a perfect solution. I can’t wait for PostGIS 2.2….

4 Responses to “Voronoi in PostGIS”

  1. dustymugs said

    Since you’re wanting to dabble in C, you could give yourself a crash course on GEOS and PostGIS/PostgreSQL by writing PostGIS hooks to the Vororoi C functions.

  2. housec01 said

    Have you revisited this with ST_VoronoiPolygons? This is something I use every day with creating partitions for endangered species. I’ve been using other processing tools but would love to store this in a view if I could find a working example. For instance I want to create them on point data that that is also stored in a view. So that view would be my input for the voronoi calculations. This helps us maximize capacity when translocating from other places to our area. Anyhow, mainly just wondering if you have revisited this.

    • I have used ST_VoronoiPolygons and it works a charm. Depending on the size of the dataset, you may want to do a materialized view (for performance reasons), but otherwise, there’s no reason you couldn’t use the function.

      CREATE VIEW AS (
      SELECT id, ST_VoronoiPolygons(geom) AS geom FROM
      favorite_point_table
      )

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: