[geos-devel] Possible speed improvement for overlay operations

[Martin Davis]

re why so many PIP checks - actually I don't think there are that many,
relatively speaking.  There are O(n+m) PIP checks, where n and m are the
number of rings in the two geometries.  In this case that is about 4300.
That is a small number relative to the total number of vertices.  And with
the envelope test each PIP test is pretty fast, so this step probably
doesn't take a very large percentage of the overall time.  So indexing
probably won't move the needle much here.

This would be worse for a pathological geometry with the same order of
magnitude of holes as vertices (e.g. a Sierpinkski carpet [1]).  And would
be even worse for computing the intersection of two *nested* Sierpinksi
carpets.    But doubt that happens very often in the real world... :)

[1] https://en.wikipedia.org/wiki/Sierpinski_carpet

On Tue, Dec 4, 2018 at 4:29 PM Martin Davis <mtnclimb at gmail.com> wrote:

> It turns out that the SimplePointInAreaLocator envelope check has been in
> place in JTS for quite a while.  Guessed it got missed as a item to port.
>
> Still have to think about whether indexing would improve things.  And I
> don't see right now why there needs to be so many PIP checks at all, since
> the hole assignment is known at the outset in this case.
>
> On Mon, Dec 3, 2018 at 1:40 PM Paul van der Linden <
> paul.doskabouter at gmail.com> wrote:
>
>> Ok, first test with my big polygon and the envelope tests in place is
>> giving a 27% speedup!
>>
>>
>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/geos-devel/attachments/20181204/46f43059/attachment-0001.html>