I'm building a navigation application and need to calculate the shortest distance between a point on a walking route and a point of interest, e.g. a cathedral.
Imagine someone travelling a route from point A to C (highlighted in red below), via point B. I need to calculate the shortest possible distance between a point on that route to point D. All distances / lengths of the triangles are known (e.g. A to B might be 10, B to D might be 4).
I need to find k and j (wherever they are located between their respective points) - I can compare them later to see which is shorter and drop the longer distance. In reality, A, B, C and D are GPS coordinates.
Any help is much appreciated - many thanks.
EDIT: updated diagram --> Need to find (Kx, Ky), (Jx, Jy), where K and J are the shortest distance along their respective routes to D.
This is a Dijkstra's algorithm a shortest path algorithm. To summarize it, 1-)Add all vertices into a array. 2-)Select a start vertex. 3-)Create a adjacent array for each vertices that you can know which vertices are adjacent to your starting vertex.(all vertices has key and initially infinity) 4-)Change your adjacent vertex's key to each distance A->B 3, B's key 3 ( if B.key=A.key+distance < B.key change ) 5-)Extract your starting vertex from array,select minimum key,continue with it 6-)until your array will be empty