The problem I'm trying to solve is that I have a number of routes coded as a list of latitude-longitude pairs, where every pair is a coordinate of an intersection on the route, such that the route can be drawn properly on the map. A user can search for a suitable route that takes him from the point he's at right now to some point on the map that he specifies. My algorithm just runs through the routes and calculates the distance between every coordinate of a route and both the user location point and the destination point, trying to figure out a route that passes near these points.
The trouble is that since a route is coded as a list of its intersections, there is not enough points to be compared with user location and the destination and the algorithm is not able to calculate a suitable route. I'm trying to find a way to interpolate the points, means having two points A and B with a distance of 100 meters between them, find some more points that lay on the line drawn between A and B with a step of 10 meters.
Can anyone describe the algorithm that can provide this kind of functionality?