add a function to calculate distance from each cell to geometries

[tiemvanderdeure]

This is something terra has and could be a nice addition: https://rdrr.io/cran/terra/man/distance.html

The use case is something like easily getting a layer with the distance to roads, rivers, cities, etc. for ecological modelling.

@rafaqz we once implemented something with a KDtree but there has to be something more efficient

[asinghvi17]

ImageFiltering has this for the Planar case I think

[rafaqz]

I think we would need to do it with STRtree and GO distance on the decomposed edges of the geometry. KDTree is for points and won't find the closest edge accurately?

@asinghvi17 we should formalise our geometry -> edge STRtree pipeline in GO as an developer interface, like GO.egdes(someobject) flattens whatever it is to a vector of edges and GO.edgetree(someobject) makes a tree you can query with extents

[asinghvi17]

We could do that as well. I believe the ImageFiltering approach is based on rasterization which may not be the best approach, but we can have multiple options / algorithms here.

@rafaqz it would be nice to also take some lessons from Rasters here. Maybe we have an unsorted and sorted edge list according to some criterion?

[asinghvi17]

Also, str will fail if the cell is outside the extent of the box. We could write our own query though.

[rafaqz]

Yes rasterizing first is easier but not very accurate at local scales.

In Rasters.jl edges are somewhat special as we round Y to Int for faster sorting and comparisons, leaving X as Float64. It's like Clipper etc but different reasoning, we just already know where all the Y line crossings will happen in advance because our target points are on a grid.

For this (distance rather than crossing point) I think we need generic floating point edges. We could have an Edges{issorted} object that knows it's sort state somehow, in the type or as a Bool field.

[rafaqz]

Also, str will fail if the cell is outside the extent of the box. We could write our own query though.

Will it fail or just return no indices?

It would be good if we could cheaply iterate over growing extents... Like find the first extent that intersects any other extent, then the larger one where the minimum distance is the distance to the first thing we found (in case it was in a corner and there is one closer in a larger extent).

[asinghvi17]

We can find the closest extents to the point using a custom tree query i think. Very happy we have AbstractTrees integration now :)

[asinghvi17]

Also could be nice to think of output formats , we may want to associate distances with the geometry they are associated to.

[asinghvi17]

And we may want an R* tree not STR for this, see the open issue on the STR repo

[asinghvi17]

It will fail as in not return any indices. Sorry for the deluge of messages - at the airport on mobile lol

[tiemvanderdeure]

Okay you two are way ahead of me. But then again what did I expect. ;)

You're talking about this package, right https://github.com/maxfreu/SortTileRecursiveTree.jl ?

I suppose we will need an extension then?

I think there are many use cases where precision does not matter all that much. If you're calculating distance to the coast or to rivers on a global grid for an SDM then rasterizing first or calculating the distance to the center of gridcells is acceptable. Or another case is where you want to calculate the distance to grid cells (e.g. to non-missing values)

Another question is how to do this with haversine distance - otherwise distance to the coast would get quite distorted in some regions.

terra has all these options and it's not even that slow but I don't know how precise it is or how well it scales, but I could take a look at what it does

[rafaqz]

That package is tiny native julia GeoInterface / Extents.jl based. GO depends on it too. So we can just depend on it. But we might need to add a nearest extent method or something.

Then I have no idea for haversine.

Rasterized distance should have a fast alg I guess but it might just be knn or STRtree where sorts are not needed? Normally skipping the sort is the main optimisation

[asinghvi17]

Might also be worth chunking tree queries to decrease the area we have to cover - just a thought!

[asinghvi17]

And if you could see what Terra does that would be great as well. If it uses s2 we might not have much of a speed bonus though. And we still need to figure out how to do extent queries on a sphere...