Implement the AbstractTrees interface

[asinghvi17]

This is currently in an extension, but we could also move it into the package proper. AbstractTrees is a zero-dependency, super lightweight package.

The code here simply implements the AbstractTrees.jl interface for STRtree, STRNode, and STRLeafNode. This allows you to use AbstractTrees iterators on STRtree structures without any fuss, like AbstractTrees.Leaves, AbstractTrees.PreOrderDFS, etc.

I personally use this to extract all tiles below a certain size (or leaf nodes), and then extract the indices they contain. Such nodes might be close to or far away from the root node.

Some example code:

"""
    extract_idxs(node)

Extract the indices of the geometries that an `STRNode` covers.

Returns a vector of integers that are indices of the geometries that made the tree.
"""
function extract_idxs(node::Union{STRtree, STRNode, STRLeafNode})::Vector{Int}
    return mapreduce(Base.Fix2(getproperty, :indices), vcat, AbstractTrees.Leaves(node))
end

[maxfreu]

Hey! I currently don't have the time to give things an in-depth look. As AbstractTrees looks pretty generic I suggest to include it in the package properly, not as extension. If you want, I invite you to co-maintain the STRTree package - then you can merge it yourself ;-)

[maxfreu]

Oh and tests would be cool, as always.

[asinghvi17]

Oops, missed these comments! Yes, will add tests soon.

[maxfreu]

@asinghvi17 do you want to fix the conflict and add a little bit of tests? Then I'd merge and tag a new version afterwards. @rafaqz AbstractTrees as a direct dep should be fine, or what do you think?

[rafaqz]

Yeah its tiny and has no deps, should be fine

[rafaqz]

Needs some minor fixes for extents

[asinghvi17]

This should be ready for review and merge now!

[rafaqz]

@maxfreu can we get a merge and register? I'm keen to use this in a project tomorrow :)

[maxfreu]

Sorry, I was occupied by real life.

Thanks again for the PRs! It's cool to be the one who's merging - and now I'm keen on benchmarking the changes :) And I also wonder how the graphs in JuliaGeo/GeometryOps.jl#259 improve.

[rafaqz]

Best avoided if you ask me ;)

But GO got quite a bit faster! I was thinking it would be good to benchmark this package against implementations in other languages, maybe it's the fastest now

[asinghvi17]

Definitely not the fastest, that throne goes to Clipper in C++ (that's what all the 3D printer folks use). But fastest in pure float64, without snapping to an integer grid - maybe! At least on some problems

[rafaqz]

For sure, although I just meant the STRtree part.

But I guess sort and extent comparisons will be a lot faster with Ints but then that's your whole paradigm.

(Also I think this isn't even pure Float64, units or dates or whatever should also just work?)

[asinghvi17]

True, we could benchmark against LibGEOS STRtree which should also be a good target for more tests

[rafaqz]

And like libspatialindex

[rafaqz]

I just realised this package would already work fine with Int64 base and would be much faster. All the extent comparisons and sorts will just be on Int with no changes.

We could try scaling some polygons up to Int64... it might just work in GO already too? Of course there would be some precision handling required to make it correct...

[asinghvi17]

It wouldn't just work unfortunately, there is a lot of T <: AbstractFloat going on. But nothing fundamentally stopping it I think

[rafaqz]

Here or in GO? I thought we were passing around T for that in GO

[asinghvi17]

We are! But something is casting to float64. Turns out the AbstractFloat constraint was only on some of the higher level methods though, so I could pull it through. But there's some point where points become Float64 anyway, which kind of ruins things.

julia> @be GO.union($(GO.Planar()), $p1, $p2, $Int64; target = $(GI.PolygonTrait()))
Benchmark: 4965 samples with 11 evaluations
 min    1.356 μs (23 allocs: 1.906 KiB)
 median 1.481 μs (23 allocs: 1.906 KiB)
 mean   1.716 μs (23 allocs: 1.906 KiB, 0.06% gc time)
 max    330.212 μs (23 allocs: 1.906 KiB, 98.58% gc time)

julia> @be GO.union($(GO.Planar()), $p1, $p2, $Float64; target = $(GI.PolygonTrait()))
Benchmark: 4664 samples with 12 evaluations
 min    1.330 μs (23 allocs: 1.906 KiB)
 median 1.431 μs (23 allocs: 1.906 KiB)
 mean   1.679 μs (23 allocs: 1.906 KiB, 0.06% gc time)
 max    208.368 μs (23 allocs: 1.906 KiB, 98.43% gc time)

[asinghvi17]

And T is not passed all the way through in quite a few functions, so there's still a lot of work to be done there