Finding the nearest way (line string) to a given point

Specific Domains
, , ,
1

I have got a few ways (i.e line strings) and a point, using the point, I need to find the closest way to a given point. How do I do that.

Ignore the grey box and the small red circle in the image.

bb
bb1262Ă—829 109 KB

ways_map = Dict(
"OSM&&WAY10592122" => [[145.0352298,-37.8374751],[145.0349665,-37.8374204],[145.0347479,-37.8373876],[145.0344542,-37.8373537],[145.0342236,-37.8373346],[145.034013,-37.837324],[145.0338078,-37.8373198],[145.0335839,-37.8373219],[145.0333626,-37.8373304],[145.0331507,-37.8373431],[145.0329643,-37.8373621],[145.032747,-37.8373886],[145.0325713,-37.837414],[145.0323943,-37.8374469],[145.0321448,-37.8374988],[145.0318029,-37.837575],[145.0315467,-37.8376343],[145.0312879,-37.8376894],[145.0310827,-37.8377339],[145.0308949,-37.8377678],[145.0306723,-37.8378038],[145.0304939,-37.837826],[145.0303169,-37.8378451],[145.030128,-37.8378619],[145.0299588,-37.8378674],[145.029759,-37.8378684],[145.0295414,-37.8378635],[145.0293322,-37.8378507],[145.0291689,-37.8378332],[145.0289908,-37.8378107],[145.0287668,-37.8377738],[145.0284598,-37.837689],[145.0281995,-37.8376017],[145.0280017,-37.8375254],[145.0277925,-37.8374397],[145.0276122,-37.8373553],[145.0274176,-37.8372527],[145.0272614,-37.8371596],[145.0271053,-37.8370584],[145.0269363,-37.8369281],[145.026669,-37.8367093],[145.0265103,-37.8365467],[145.0263191,-37.8363432],[145.0259387,-37.8359123],[145.0254405,-37.8353373],[145.0248245,-37.8346331],[145.024076,-37.8337694]],
"OSM&&WAY10592129" => [[145.0242202,-37.833699],[145.0249771,-37.8345629],[145.0255818,-37.8352643],[145.0261807,-37.8359464],[145.0263563,-37.8361408],[145.0266897,-37.8364842],[145.0269932,-37.8367649],[145.0271473,-37.8368942],[145.0274437,-37.8370893],[145.0276962,-37.8372252],[145.0279431,-37.8373415],[145.0282033,-37.8374456],[145.0284439,-37.8375247],[145.0286924,-37.837598],[145.0289724,-37.8376538],[145.0292708,-37.8377009],[145.0295253,-37.8377236],[145.0297765,-37.8377265],[145.0300567,-37.8377233],[145.0303277,-37.8377053],[145.0305851,-37.8376725],[145.0308601,-37.837629],[145.031135,-37.8375761],[145.0315011,-37.8374903],[145.031764,-37.8374268],[145.0321489,-37.837341],[145.0324144,-37.8372869],[145.032684,-37.8372425],[145.0329562,-37.8372064],[145.0332164,-37.8371842],[145.033499,-37.8371691],[145.0337609,-37.8371651],[145.0340264,-37.8371715],[145.0342987,-37.8371863],[145.0345682,-37.8372086],[145.0348405,-37.8372467],[145.0350497,-37.8372816],[145.0352732,-37.8373251]],
"OSM&&WAY756852509" => [[145.0290871,-37.834018],[145.0289588,-37.8340363],[145.028506,-37.8339769],[145.0283699,-37.8339298]],
"OSM&&WAY756852510" => [[145.0283699,-37.8339298],[145.0285162,-37.8339201],[145.0289616,-37.8339774],[145.0290871,-37.834018]]
)

point_input = [
          145.02898273876292,
          -37.83403333426016
        ]

output :
OSM&&WAY756852509
2

Melbourne, by the river, 2 kms, I’ll take it

1200Ă—598 352 KB

5 Likes
3

What’s this a reference to??

4

Is this a Julia question or are you asking about an algorithm? What have you tried? Why hasn’t it worked?

5

rainbolt, the guy who’s memorized Google Maps…

6

Looking for a algorithm + julia solution to the above problem.

What I’ve tried.

  1. Calculate the nearest point to the each way
geos_point = LibGEOS.Point(point_to_find_nearest[1], point_to_find_nearest[2])
 geos_line_string = LibGEOS.LineString(line_string)
point_on_linestring, point_on_point = LibGEOS.nearestPoints(geos_line_string, geos_point)
  1. Calculate the distance from each point on the way to the given point using haversine
function get_point_distance(
    point1::Vector{Float64},
    point2::Vector{Float64},
)::Float64
    return haversine(point1[2], point1[1], point2[2], point2[1])
end
  1. Then find the linestring which creates the shortest distance between the given point and the point on the line string.

Not sure, whether this is the correct approach or the optimum way to achieve this, but it seems to be producing the results which I wanted.

1 Like
7

A term of art for this type of problem is “route planning” algorithms.

Of course there is a lot involved if your plans involve constraints
like staying on a road or path, going around obstacles,…