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

**URL:** <https://discourse.julialang.org/t/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/22787>\
**Category:** Performance\
**Created:** [April 5, 2019, 9:12am UTC](https://discourse.julialang.org/t/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/22787 "2019-04-05T09:12:49Z")\
**Posts on this page:** 13\
**Page:** 1

<div class="post-metadata">

**Author:** ![bsnyh](https://avatars.discourse-cdn.com/v4/letter/b/ce7236/32.png) [@bsnyh](https://discourse.julialang.org/u/bsnyh)\
**Post date:** [April 5, 2019, 9:12am UTC](https://discourse.julialang.org/t/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/22787/1 "2019-04-05T09:12:49Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![pszufe](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pszufe/32/23452_2.png) [@pszufe](https://discourse.julialang.org/u/pszufe)\
**Post date:** [April 5, 2019, 9:38am UTC](https://discourse.julialang.org/t/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/22787/2 "2019-04-05T09:38:57Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![bsnyh](https://avatars.discourse-cdn.com/v4/letter/b/ce7236/32.png) [@bsnyh](https://discourse.julialang.org/u/bsnyh)\
**Post date:** [April 5, 2019, 2:54pm UTC](https://discourse.julialang.org/t/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/22787/3 "2019-04-05T14:54:03Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![pszufe](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pszufe/32/23452_2.png) [@pszufe](https://discourse.julialang.org/u/pszufe)\
**Post date:** [April 5, 2019, 8:58pm UTC](https://discourse.julialang.org/t/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/22787/4 "2019-04-05T20:58:08Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![ctrebbau](https://avatars.discourse-cdn.com/v4/letter/c/5f9b8f/32.png) [@ctrebbau](https://discourse.julialang.org/u/ctrebbau)\
**Post date:** [October 12, 2022, 3:13pm UTC](https://discourse.julialang.org/t/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/22787/5 "2022-10-12T15:13:22Z")

</div>

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](https://global.discourse-cdn.com/julialang/original/3X/1/2/1221e5f91aee038d4f43902c47c92eb7b96ed134.png)

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)](https://github.com/alyst/SpatialIndexing.jl) and others listed here [https://juliageo.org/](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.

---

<div class="post-metadata">

**Author:** ![pszufe](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pszufe/32/23452_2.png) [@pszufe](https://discourse.julialang.org/u/pszufe)\
**Post date:** [October 12, 2022, 7:37pm UTC](https://discourse.julialang.org/t/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/22787/6 "2022-10-12T19:37:17Z")

</div>

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!

---

<div class="post-metadata">

**Author:** ![Optimization](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/optimization/32/32462_2.png) [@Optimization](https://discourse.julialang.org/u/Optimization)\
**Post date:** [April 28, 2023, 9:53pm UTC](https://discourse.julialang.org/t/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/22787/7 "2023-04-28T21:53:50Z")

</div>

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 `i`and `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!

---

<div class="post-metadata">

**Author:** ![pszufe](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pszufe/32/23452_2.png) [@pszufe](https://discourse.julialang.org/u/pszufe)\
**Post date:** [April 29, 2023, 12:04am UTC](https://discourse.julialang.org/t/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/22787/8 "2023-04-29T00:04:45Z")

</div>

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

Suppose you have the map:

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

```

Than you can do:

```julia
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.

---

<div class="post-metadata">

**Author:** ![Optimization](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/optimization/32/32462_2.png) [@Optimization](https://discourse.julialang.org/u/Optimization)\
**Post date:** [April 29, 2023, 8:33am UTC](https://discourse.julialang.org/t/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/22787/9 "2023-04-29T08:33:29Z")

</div>

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?

```julia

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

```

---

<div class="post-metadata">

**Author:** ![pszufe](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pszufe/32/23452_2.png) [@pszufe](https://discourse.julialang.org/u/pszufe)\
**Post date:** [April 29, 2023, 11:45am UTC](https://discourse.julialang.org/t/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/22787/10 "2023-04-29T11:45:09Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Optimization](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/optimization/32/32462_2.png) [@Optimization](https://discourse.julialang.org/u/Optimization)\
**Post date:** [April 29, 2023, 2:01pm UTC](https://discourse.julialang.org/t/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/22787/11 "2023-04-29T14:01:27Z")

</div>

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!

---

<div class="post-metadata">

**Author:** ![pszufe](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pszufe/32/23452_2.png) [@pszufe](https://discourse.julialang.org/u/pszufe)\
**Post date:** [April 29, 2023, 2:55pm UTC](https://discourse.julialang.org/t/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/22787/12 "2023-04-29T14:55:46Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![pszufe](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pszufe/32/23452_2.png) [@pszufe](https://discourse.julialang.org/u/pszufe)\
**Post date:** [October 31, 2023, 4:55pm UTC](https://discourse.julialang.org/t/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/22787/13 "2023-10-31T16:55:16Z")

</div>

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](https://github.com/pszufe/OSMToolset.jl)

Here is the code:

```julia
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))

```