Point-in-Polygon Shortcuts

The code for spatial predicates in PostGIS is largely dependent on the GEOS topology library, because doing predicate calculations in generality is hard, and GEOS already exists. However, moving geometry from PostGIS into GEOS format incurs a cost. And not all predicate algorithms are hard. Point-in-polygon tests, for example, are relatively easy.

So, for performance reasons, a couple years ago, Mark Leslie (at Refractions at the time) implemented a point-in-polygon test directly in the PostGIS library. Whenever ST_Contains(), ST_Intersects(), etc, are called, the geometries are first checked to see if they are points and polygons, and if they are, GEOS is avoided and the calculation is done in PostGIS.

But, why stop at one shortcut?

What if you are testing hundreds (or thousands) of points against one, or a small number, of polygons? Why iterate through all the segments of the polygon for every point, to carry out the test? By indexing the segments of the polygon, you can reduce the computational effort of doing a point-in-polygon test from O(NumberOfPolygonEdges) to O(log(NumberOfPolygonEdges)). However, for the index to be effective, you have to re-use it for each new point, not re-build it for every polygon/point pair. That means it has to be cached between function calls.

A bit over a year ago, Mark implemented a caching version of the point-in-polygon shortcut, with an indexing algorithm from Martin Davis, and that shortcut currently resides in the 1.3 release series. However, it has two drawbacks.

Last week I took a couple days to delve deeply into what this shortcut was doing, and made the following improvements.

The point-in-polygon caching shortcut is extremely effective. Using the un-cached code, a spatial join of 8000 points to 80 polygons, where there are an average of 100 points per polygons, takes about 30 seconds on my workstation. With the caching segment indexes, the same join returns in 6 seconds.

The improved code is currently on trunk only, but I will back-port it into 1.3.X next week, so it will be available in the next points release.

Update: These changes have now been back-ported to 1.3 and will be generally available in 1.3.4 when it is released.