[postgis-devel] Faster ST_Intersection

[Darafei "Komяpa" Praliaskouski]

It looks like for polygon / box intersection area can be calculated in
O(n), by just clamping the ordinates (
https://github.com/postgis/postgis/commit/3233ccd19cdb6958b53164262cd812d3f6d70fb2
).

It also may be adapted for any convex polygons, with O(n*m) though. Convex
check also seems to be O(n). Building dataset tends to be mostly convex
(and mostly 4-corner), so this may be a specialized fast path.

Is there a chance we may want BOX() as new geometry primitive to save a
is_convex / is_box check? :)

Any other thoughts?

On Tue, Oct 23, 2018 at 8:04 PM 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



-- 
Darafei Praliaskouski
Support me: http://patreon.com/komzpa
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/postgis-devel/attachments/20181026/a765c48d/attachment-0001.html>