Add nearest way and R-tree

[jarodlam]

Add an R-tree based on SpatialIndexing.jl to OSMGraph to support a nearest_way interface.

Like the K-D tree, the R-tree stores locations based on the Earth-frame Cartesian coordinate system. Each R-tree element is a way bounded by a cube. The R-tree allows for a very fast bounding box check between a point/volume and all ways.

The new nearest_way and nearest_ways functions use the R-tree to quickly find nearest ways. This is not possible with the K-D tree because it only stores node points; therefore, it cannot account for the edges between nodes in a nearest ways check.

In addition to the way ID and distance these functions also return an EdgePoint type:

struct EdgePoint{T<:Integer}
    n1::T
    n2::T
    pos::Float64
end

This represents the exact nearest point along the way. n1 and n2 are the two nodes that make up the nearest edge, and pos is the distance along the edge starting from n1 represented by a number between 0.0 and 1.0. I've also got a shortest_path implementation between EdgePoints coming soon.

I welcome feedback on the interface for this, I've tried to make it similar to nearest_node.

[jarodlam]

Looks like I broke subgraph tests, will have a look at this tomorrow.

[jarodlam]

Looks like I broke subgraph tests, will have a look at this tomorrow.

Fixed the issue :))

[codecov-commenter]

Codecov Report

Merging #80 (a5c8e5a) into master (bdbf786) will increase coverage by 0.88%. The diff coverage is 90.12%.

@@            Coverage Diff             @@
##           master      #80      +/-   ##
==========================================
+ Coverage   78.91%   79.80%   +0.88%     
==========================================
  Files          13       14       +1     
  Lines        1053     1129      +76     
==========================================
+ Hits          831      901      +70     
- Misses        222      228       +6     

Impacted Files	Coverage Δ
src/graph.jl	87.32% <78.57%> (-1.57%)	:arrow_down:
src/nearest_way.jl	93.93% <93.93%> (ø)
src/geometry.jl	100.00% <100.00%> (ø)
src/subgraph.jl	96.66% <100.00%> (+0.37%)	:arrow_up:
src/types.jl	59.25% <100.00%> (+1.56%)	:arrow_up:
src/graph_utilities.jl	35.71% <0.00%> (+14.28%)	:arrow_up:

Help us with your feedback. Take ten seconds to tell us how you rate us. Have a feature suggestion? Share it here.

[jarodlam]

Have reviewed this PR with @bjmommers. @captchanjack this is ready to merge when you get the chance.

[Datseris]

cc @AayushSabharwal maybe this can lead to accelerations in Agents.jl. Thanks a lot for this PR @jarodlam , I've learned of SpatialIndexing.jl that I had no idea existed, and I was searching dynamic search trees in Julia for a long time...

[jarodlam]

cc @AayushSabharwal maybe this can lead to accelerations in Agents.jl. Thanks a lot for this PR @jarodlam , I've learned of SpatialIndexing.jl that I had no idea existed, and I was searching dynamic search trees in Julia for a long time...

@Datseris No worries mate, I did notice the possible use case in Agents.jl when writing this. Look forward to seeing what you do with it!