Introducing a spatial index interface

[asinghvi17]

There are multiple implementations of spatial index trees in Julia: SortTileRecursiveTree, SpatialIndexing, LibSpatialIndex. The problem lies in that there is no single API to query any of these. They all return the same thing, we just need a common API to query them.

If we get GeoPackage.jl going then there is even the possibility of extracting the SQLite R-tree from there, which would be interesting. In any case, to my mind it makes sense to have some form of interface here - maybe the following on the implementor's side,

GO.trait(x)::GI.SpatialIndexTrait
GO.query(::GI.SpatialIndexTrait, x, extent)::Vector{Int}

Then, in GI,

GO.query(x, geom) = GI.query(GI.trait(x), GI.trait(geom), x, geom)
GO.query(::SpatialIndexTrait, ::AbstractGeometryTrait, x, geom) = GO.query(SpatialIndexTrait(), x, GI.extent(geom))
GO.query(::SpatialIndexTrait, ::Nothing, x, ext::Extent) = GO.query(SpatialIndexTrait(), x, ext)

[evetion]

Great to read your thinking on spatial indexing, we absolutely need this in the ecosystem.

As far as I'm aware, indices do not necessarily query on the same thing, depending on the type of index. There can be (k-)nearest neighbour lookups, combined with retrieving distance(s). Or indeed, (possible) candidates in an area of interest (with variations for different dimensions/distance metrics).

What you're proposing has been implemented to some higher-level extent in https://github.com/evetion/GeoAcceleratedArrays.jl. it uses the API from Acceleratedarrays to do these lookups. The package could be refactored to work with other index packages (provided they implement geointerface) as package extensions.

The remaining work then is to make (spatial) joins make use of these indices.

[asinghvi17]

The join part is already implemented in JuliaGeo/GeometryOps#75 - we would just need a way to get an arbitrary index from, say, a database, or a pregenerated index. LibSpatialIndex is also not threadsafe, so I would rather use SpatialIndexing.jl or RTrees.jl.

I think the lowest common denominator is that all of these spatial indexing methods return a list of neighbor indices given some area of interest, though? For spatial joins and other similar tasks, getting a list of neighbours is all you need, since they have to be filtered by some predicate afterwards in any case. Perhaps we could pass arbitrary kwargs through here, though.

(Now that you mention it, perhaps knn trees may not follow this interface - but I haven't heard of those being used for GIS much either...)

[asinghvi17]

Now that I think about it, we could implement this first in GeometryOps, to see if it makes sense, and then upstream to GeoInterface once we've hashed it out...package extensions in GeometryOps should do the work for this!

[rafaqz]

Now that I think about it, we could implement this first in GeometryOps

Absolutely, playing with new ideas is pretty hard post 1.0. Even GO.apply could move to GeoInterface, but best to wait until its been stable for a long time before we do anything like that. For that reason I kind of regret putting the geometry types in GeoInterface rather than in a separate but closely related package.

[asinghvi17]

I started introducing something like this in #259, called it SpatialTreeInterface and it's built specifically for immutable trees. The idea is that it provides utilities to accelerate workflows which traverse trees from parent to child, rejecting branches as you go along via some predicate, and then get to the child nodes, where you can perform extent checks and then apply some function to that index.

I didn't build in any ability to go from e.g. child to parent (as would be required for some algorithms like KNN) yet, but one could potentially do so. But this interface can handle both single and dual tree queries for R-tree style indexes and other styles (Natural indexing from tg, potentially y-binning, etc).

A big piece of the puzzle here is to do this in a non-allocating way. We often don't need to store query results in a vector, but can instead process them incrementally. This interface allows that, and the usecase I was interested in when writing it (fast edge queries) is one such case, at least for natural tree/indexing. STRtrees are still unordered and we would need to sort those, but it's a lot easier to have an interface that allows that without too many allocations.

[asinghvi17]

Closing since SpatialTreeInterface is now merged. It is also extent-agnostic in some sense.