[geos-devel] Possible speed improvement for overlay operations

[Martin Davis]

On Sun, Dec 2, 2018 at 8:04 AM Paul van der Linden <
paul.doskabouter at gmail.com> wrote:

>
> I also noticed that in
> https://github.com/libgeos/geos/blob/8bc1ea0f8019bcb83c60126e7883ae428ea7c677/src/algorithm/locate/SimplePointInAreaLocator.cpp#L49
> and/or
> https://github.com/libgeos/geos/blob/8bc1ea0f8019bcb83c60126e7883ae428ea7c677/src/algorithm/locate/SimplePointInAreaLocator.cpp#L72
> there's no envelope-check done
>

Yes, that's a good point.  The original reason for not including an
envelope check is following the JTS design principal of not doing checks
which may have already been done externally.  But in this case the check is
fairly low-cost, and not including it is (obviously) a common source of
inefficiency.  So it makes sense to add an envelope check into the default
code path.  (If an unchecked path is needed that could be added as a
separate method).

>
> Another thing: as that pointinpolygon is going to be called from
> https://github.com/libgeos/geos/blob/8bc1ea0f8019bcb83c60126e7883ae428ea7c677/src/geomgraph/EdgeEndStar.cpp#L165
> and findEdgeRingContaining quite a number of times, perhaps its possible to
> prepare the lot and use a IndexedPointInAreaLocator?
>
> You have found an area in the overlay code which isn't optimized as much
as it could be.  Although whether it's worth building an index on the holes
depends on the number of holes and rings that are being checked.  But for
geometries with many holes it might be advantageous.  Are you going to test
this?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/geos-devel/attachments/20181203/20ee87ed/attachment.html>