HotPixelIndex: Use STRtree instead of KdTree

[dbaston]

This PR modifies HotPixelIndex to back it with an STRtree instead of a KdTree. It provides about a 15% performance gain in a buffer benchmark that heavily uses the HotPixelIndex. I don't know if that's worth the change. Peak memory usage increases by about 10%. There may be room for more tuning.

gps_tracks.txt

bin/geosop -t -q -a ~/data/gps_tracks.txt buffer 20

(test case is from https://github.com/r-spatial/sf/issues/2039)

[pramsey]

Is there any implementation improvement left to wring out of kd-tree? The "conventional wisdom" on kd-tree is that for points it should be superior to r-tree in principle. If it's not in practice that would be an important learning.

[dbaston]

I poked at this a bit, writing a KdTree implementation that uses bulk loading so it can be fully balanced, with nodes in a contiguous block of memory. That gets us most of the performance gain of switching to STRtree but is still a bit slower. And then you could probably make STRtree faster, either using float envelopes (https://github.com/libgeos/geos/pull/757) or a SIMD implementation (https://github.com/dbaston/libgeos/commit/7af0847aa3f0296d6c1ce375254acf554f323f69).

[pramsey]

I think you proved the point: it's faster, it's not worse. Why not merge?

[dbaston]

Why not merge?

Merge conflict, modest benefits, general conservatism about differences from JTS