[geos-devel] Possible speed improvement for overlay operations
mtnclimb at gmail.com
Tue Dec 4 17:10:53 PST 2018
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 ). And would
be even worse for computing the intersection of two *nested* Sierpinksi
carpets. But doubt that happens very often in the real world... :)
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...
More information about the geos-devel