PostGIS - Fast area computation on large overlapping (or not) polygon dataset

Question

I'm co-developing an PostGIS based API that will work with complex and potentially large sets (>10k) of polygons, extracted from a large table following custom, user defined filters. I have precomputed the area of every polygon and put it on an 'area' field. Sometimes the selected polygon set will have no overlapping at all, most of the times there will be ~10% overlapping. I need to efficiently compute the total, non-overlapping area of the filtered dataset. The easy answer is to use st_Area(st_Union(geom)::geography)), but it will be inefficient on large datasets with little overlapping, and completly unnecessary if there's no overlapping (I'd just need to add up the 'area' field). I wonder if there is way to create a spatial function (let's call it smart_area) that will:

1. Evaluate if there's any overlapping at all on the input dataset
2. If there's no overlapping, it will return the sum of the 'area' field
3. If there's overlapping, it will compute the area of the overlapping polygons and then add it to the summed area of the 'area' field of the rest of the polygons.

To generate a working example, I have modified the routine presented on http://boundlessgeo.com/2014/10/postgis-training-creating-overlays/ :

DROP TABLE IF EXISTS pts;
DROP TABLE IF EXISTS circles;
-- CREATE RANDOM POINTS
CREATE TABLE pts AS
  WITH rands AS (
  SELECT generate_series as id, 
         random() AS u1, 
         random() AS u2 
  FROM generate_series(1,10000)
)
SELECT
  id,
  ST_SetSRID(ST_MakePoint(
    10*u1,
    10*u2), 4326) AS geom
FROM rands;
-- CREATE CIRCLES WITH AREA (in km²)
CREATE TABLE circles AS
  SELECT id, ST_Area(ST_Buffer(geom, .01)::geography)/1000000 as area, ST_Buffer(geom, .01) AS geom 
    FROM pts;
-- COMPUTE TOTAL AREA
SELECT SUM(area) FROM circles;
-- COMPUTE TOTAL NON-OVERLAPPING AREA
SELECT ST_Area(ST_Union(geom)::geography)/1000000 FROM circles

This piece of code will generate 10.000 circles, some of them will overlap. The second query, which computes the non-overlapping area (the area that I want to compute) took around 10 seconds on my computer, while the first one is almost instantaneous, but inaccurate. The 'smart_area' function would be a mix of both queries, as it would add up the 'area' field of the non-overlapping polygons and compute the st_union area of the overlapping ones. I guess (I hope) that this function will be way faster than the second query.

Any insight on this problem?

Answer 1

It might be possible to discriminate between sets with NO overlap and sets with SOME overlap by creating a MultiPolygon from the set and checking whether it is valid. If it is invalid then there is at least one pair of polygons which overlap. Checking validity is fairly efficient, since it returns as soon as a single overlap is found.

It does seems like there should be a way to efficiently separate a set into non-overlapping and overlapping parts, but not sure how that could work at the moment. It will almost certainly require a net new function to do that.

Answer 2

The same way you precomputed area, you could precompute overlaps into an "overlap" column. When a polygons overlaps, it does not mean it also overlap in the subset of polygons, but when there is no overlaps you are at least sure there is also no overlap in the subset.