[postgis-devel] Faster ST_Intersection

[Martin Davis]

On Fri, Oct 26, 2018 at 6:09 AM Darafei "Komяpa" Praliaskouski <
me at komzpa.net> wrote:

> 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?
>
> Isn't BOX axis-aligned (ortholinear)?  Is this really a common occurrence
in building footprints?

There's probably more optimal intersection code that could be developed for
quadrilaterals.  I'm still optimistic that the Franklin Fast Overlay Area
approach holds some promise as well.

It's pretty fast to check for rectangular or quadrilateral geometry where
an optimization for those exists.  So that doesn't seem like a reason to
incur the overhead of developing and maintaining a new Geometry type.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/postgis-devel/attachments/20181026/ae3768a8/attachment.html>