[postgis-devel] Faster ST_Intersection

[Martin Davis]

W. R. Franklin was one of the early researchers into polygon overlay, and
he published a paper "Calculating the Area of Overlaid Polygons Without
Constructing the Overlay" back in 1994 [1]. Unfortunately behind a paywall,
but maybe further sleuthing will uncover it in a dusty corner of the net.

It's not obvious to me that his algorithm could have a lower computational
complexity, but the constant factor might be lower.  And possibly there's a
robustness advantage too.

[1]
https://www.researchgate.net/publication/2804714_Calculating_the_Area_of_Overlaid_Polygons_Without_Constructing_the_Overlay

On Tue, Oct 23, 2018 at 10:04 AM Paul Ramsey <pramsey at cleverelephant.ca>
wrote:

> The first GIS system I ever used had an “intersection area” function that
> was distinct from, and faster than, the full-on “intersection” function
> that output a new geometry. I wonder if there is some possibility there…
>
> P
>
> On Oct 23, 2018, at 6:01 PM, Darafei Komяpa Praliaskouski <me at komzpa.net>
> wrote:
>
> Hi,
>
> I have two polygonal layers to intersect and need to measure area of
> intersections.
>
> ST_Area(ST_Intersection(a.geom, b.geom)) works fine, but is rather slow.
> Typical polygon on first side has <10 edges, on second 200..1000 edges.
>
> What are my options to make it faster? Any ideas, links, experiences to
> share are welcome.
>
> For starters, this seems to work faster than vanilla ST_Intersection in my
> case:
>
> create or replace function clipped_st_intersection(geom1 geometry, geom2 geometry)
>   returns geometry
> as $$select ST_Intersection(
>               case
>                 when ST_MemSize(geom1) > 160 then ST_ClipByBox2D(geom1, geom2)
>                 else geom1 end, case
>                 when ST_MemSize(geom2) > 160 then ST_ClipByBox2D(geom2, geom1)
>                 else geom2 end)$$
> language sql
> immutable
> strict
> parallel safe;
>
> --
> Darafei Praliaskouski
> Support me: http://patreon.com/komzpa
> _______________________________________________
> postgis-devel mailing list
> postgis-devel at lists.osgeo.org
> https://lists.osgeo.org/mailman/listinfo/postgis-devel
>
>
> _______________________________________________
> postgis-devel mailing list
> postgis-devel at lists.osgeo.org
> https://lists.osgeo.org/mailman/listinfo/postgis-devel
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/postgis-devel/attachments/20181023/80017acc/attachment.html>