[postgis-devel] Faster ST_Intersection

[Martin Davis]

A bit more information on the Franklin Area-Of-Intersection algorithm,
after an initial pass at implementing it:

1. It does seem to work! (which wasn't really in doubt, but still it seems
a bit magical...)
2. I am no longer optimistic that it will provide a faster algorithm.  The
reasons are that it still has to determine all segment intersections, which
is the main cost of overlay.  And, it has to do a lot of point-in-polygon
tests, which might actually make it slower. This is the downside of using a
structure which contains only the vertices, with no topological information.
3. It should be fully robust, up to numerical approximation.  Not sure if
this makes it appealing to use - this depends on how often topology issues
are encountered in actual use.

On Tue, Oct 23, 2018 at 10:35 AM Martin Davis <mtnclimb at gmail.com> wrote:

> 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/20181105/0e3a3ac6/attachment.html>