Add an optimised "GEOSPreparedDistancesWithin" method

[nyalldawson]

The recently introduced GEOSPreparedDistance_r is fantastic, and is showing great benefits for client applications.

One similar use case I'd love to see optimised in GEOS is to be able to quickly test whether two geometries are within a certain distance of each other. Right now I can use GEOSPreparedDistance_r to obtain the minimum distance between them and then check if this is less then the desired tolerance, but there's likely huge wins to gain if the minimum distance calculation could be shortcut early as soon as a distance <= this threshold distance is found.

E.g. if the first segment tested from a massive polygon is found to be within the search distance, then it's just wasted work to continue to calculate the distance to all other segments.

[nyalldawson]

@robe "GEOSPreparedDistancesWithin" isn't correct -- that sounds like it would return a list of distances.

[strk]

Filed upstream: https://trac.osgeo.org/geos/ticket/1124

[strk]

I've given the code a review. The "PreparedDistance" operation is building an index on "facets" of the geometry, then querying for the "closest" facet to the query point. The distance computation only happens once, against the "closest" facets between two prepared trees. The only speed gain we could obtain would be avoiding to build a tree for the query geometry (if not already prepared) if it's known to be too far away, maybe by looking at bounding boxes. @nyalldawson can you give a pointer to the QGIS code doing the operation you describe ?

[nyalldawson]

@strk

Here's a good example:

A reference geometry is prepared upfront here:

https://github.com/qgis/QGIS/blob/master/src/core/vector/qgsvectorlayerfeatureiterator.cpp#L150

Then as features are iterated they are tested in turn to check that they fall within the required distance of the reference geometry here:

https://github.com/qgis/QGIS/blob/176ab296587b015dab98efea54a593856d0ead6b/src/core/vector/qgsvectorlayerfeatureiterator.cpp#L906

(This is exposed by "extract within distance" algorithm if you're looking for a tool you can use to test with)

In my testing I found that this code behaves very poorly in certain circumstances. One example was when the reference geometry was a complex multipolygon with many parts, where the geometries being compared to it are relatively close vs the overall size of the multipolygon.

[strk]

Thanks @nyalldawson -- I've started from the outside in qgis/QGIS#45057 by exposing a distanceWithin in the QgsGeometryEngine class.
I'll try the "extract within distance" algorithm to check exactly what happens underneath.

[strk]

I only realized now that this ticket is in the GEOS github issue tracker (sorry, I'm not used to this tracker being open).
Is there a QGIS ticket for this ?

[pramsey]

This seems to have happened.