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

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.

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

@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” 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.