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)?

#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.

2 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: https://gistbok.ucgis.org/bok-topics/spatial-indexing