Good Julia function / algorithm idea to find the nearest node to a given point location based on some given road network (for example, open street map data)?

General Usage Performance
1

Hello. In python, we have the nice function to get the nearest node to a given point location using the osmnx package as the following.

import osmnx as ox
ox.config(log_console=True, use_cache=True)
G = ox.graph_from_place(‘Buffalo, New York, USA’, network_type=‘walk’)
point1 = (42.891310, -78.871355)
ox.get_nearest_node(G, point1, return_dist=True)

I have not dig deeply of the function

ox.get_nearest_node()

yet. I was just wondering, under the hood, what is the algorithm / idea to get the nearest node to a given point location. I believe this is also implemented in Julia package,

OpenStreetMapX.jl,

@pszufe. It should be easy with a not so huge data set. But with a huge data set, like several millions of potential nodes in the road network which could be chosen as the closest potentials, is there an efficient idea to attack it? Or do you know some references / links which might be helpful.

2

OpenStreetMapX provides this functionality via point_to_nodes(::LLA, ::MapData)

Hence you can simply provide coordinates as the first paramater, the map as the second and get the node.

However under the hood it is using the nearest_node function that does a full scan. For a network of new millions nodes it will be still fast.
However if you need to scan millions of times you should built a spatial index. Consider using LibSpatialIndex.jl. The drawback is that building an index of course takes some time. If you decide to do it you are welcome to propose point_to_nodes(::LLA, ::MapData, ::SpatialIndex) function for OpenStreetMapX.

4 Likes
3

@pszufe, that’s very helpful. Two questions remain:

1: In the nearest_node function, which distance measure did you use? Is it great circle distance or the Euclidean distance. For several millions of nodes, how did you ensure that it is still fast? Is it because of the “natural property” :smile: of Julia?

2: I hope it’s not a naive question. But what is a “spatial index”? What’s the idea that using it can make scan millions of times possible?

Many thanks indeed.

4

Ad. 1.
It is Euclidean distance that include also altitude. The point is that each road segment is so small that we do not care about great circle.
“how did you ensure that it is still fast?” - a full scan over 1 million floats is a cheap operation (if you need to do it once)

Ad. 2.
Spatial index is a data structure that makes to possible to efficiently search data aligned in more than one dimension.
An excellent explanation with all examples and self explaining pictures can be found here: DM-66 - Spatial Indexing | GIS&T Body of Knowledge

5

Hi @pszufe, I have around 8M coordinates I’d like to associate with nearest node on an OpenStreetMapX with around 800,000 nodes, but I’m finding it hard to compute even 10,000 points. Here is a graph of benchmarks

image
image1446×960 31.1 KB

computed like this:
b4 = @benchmark [ point_to_nodes(pt, mad) for pt in ptsOrig ] setup=(ptsOrig = zip($(df.dLat[1:10_000]), $(df.dlng[1:10_000])))

Is there a quick way around this? if spatial indexing is the only solution, there’s a native Julia option here GitHub - alyst/SpatialIndexing.jl: Spatial data indexing in pure Julia (R*-trees etc) and others listed here https://juliageo.org/

Do you recommend any one in particular nowadays and is there a quick tutorial somewhere as to how to build the index given an OpenStreetMap and any of these libraries?

Thanks in advance.

6

Dear @ctrebbau,
the spatial indexing that you have mentioned is exactly the way to go.
You should get the list of coordinates for all nodes on the map, build the spatial index and then query the index.
Since you have only 10k points perhaps it does not matter which spatial indexing library you use. I have not used the one you mentioned but it looks fine. Please write what performance you got!

All the best!

7

Hello @pszufe

When I use the functions point_to_nodes and nearest_node, the outputs are some node ids. for instance 56684. I can call any traversal function on them and works perfectly fine.

However, If I want to check whether two node id form a links or not, how to check it? This (i,j) in map.e (where iand j are node ids), doesn’t seem to be correct and always return Tuple{Int64, Any}[]

How to find out which of the node id s that are coming from nearest_node function form an edge in the map?

Thanks!

8

You need to translate those two nodes to graph node ids and than ask using the Graphs.jl interface.

Suppose you have the map:

using OpenStreetMapX, Graphs
m = get_map_data(joinpath(dirname(pathof(OpenStreetMapX)),"..","test/data/reno_east3.osm");use_cache=false);

Than you can do:

julia> Graphs.has_edge(m.g,  m.v[140267934], m.v[140267942])
true

Using this translation you can of course do any other graph manipulation in a similar fashion.

1 Like
9

Thank you very much. I’ll give it a try.
But why the foolowing does not work. Is there something that I have to change?


function add_graph_edge!(m::MapData, va::Int, vb::Int; symmetric=false)
    Graphs.add_edge!(m.g, va, vb)
    push!(m.e, (m.n[va], m.n[vb]))
    symmetric && add_graph_edge!(m, vb, va; symmetric=false)
end
10

The information on nodes and edges is kept in several places. There is no API for map mutation.
Maybe one day someone will develop one.

P.

1 Like
11

Thanks again @pszufe

I have one other issue that wanted to solve with nearest_node command but it’s quite computationally expensive. Do you know any altenative?

Suppose I have a map with a boundy of min_lat= x1, min_lon= y1, max_lat= x2 max_lon= y2 and have a csv file contanning 6M rows of latitude longitude coordinated points across USA. I’ curious to know if OSMx or julia in general can automaticlly find all rows that are inside the map? I think from that 6M only 2M are within the map boundary I have.

Thanks again!

12

For efficient searching you need to have a spatial index.
This was already mentioned in this thread together with SpatialIndexing.jl

1 Like
13

So i implemented and published a new Julia package that covers the “find on map” functionality that you have mentioned. GitHub - pszufe/OSMToolset.jl: Tools for Open Steet Map: Point-of-Interest extraction and tiling of map data

Here is the code:

using OSMToolset
using OpenStreetMapX
md = get_map_data("somemap.osm"; use_cache=false, only_intersections=false);
ixnodes = NodeSpatIndex(md; node_range=1500.0)  # index range 1500 meters
distance, osmnodeid = findnode(ixnodes, LLA(39.0, 77.0))