Voronoi in PostGIS

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.

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.

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;

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