[postgis-devel] Faster ST_Intersection

[Darafei "Komяpa" Praliaskouski]

On Fri, Oct 26, 2018 at 8:20 PM Martin Davis <mtnclimb at gmail.com> wrote:

>
> 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?
>

Usages I see for BOX are storing raster's pixels and things like parts
clipped off by ST_Subdivide. This can also fix things like BoundingDiagonal
having to exist in this form, as there's no easy option to store a
multi-dimensional axis-aligned BOX in geometry.


> 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.
>

I've tried replacing box clipping with clip_to_ordinate range:
https://github.com/Komzpa/postgis/pull/6

First observation: ST_Buffer can't reliably fix all the topological
incorrectness after this clipping, and ST_MakeValid can't either. Any ideas
of ready made functions that can help fix it?

Second observation: ST_Subdivide is a lot faster when it doesn't try to get
valid geometry out, and only needs to check one axis. Point-in-polygon and
ST_Area should work well for this case of invalidity, so it may be of some
use there either.


>
> 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.
>

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