Finding the distance between two coordinates (longitudes/latitudes) which are not found as nodes in OSM

Question

I intend to make my own OSM Router, and I do not want to use third party OSM routers.

WHAT I HAVE DONE: I have downloaded OSM data in XML format and applied different algorithms to find the shortest path between two nodes in map using their coordinates (longitude/latitude). Everything is working fine.

THE PROBLEM: The only problem is OSM XML data has only limited number of coordinates (longitude/latitude). I want to find the distance between two coordinates (longitudes/latitudes) which are not found as nodes in OSM. I could not find any thing related to this on internet.

FOR INSTANCE, I have a random longitude/latitude for point A, and I have a random longitude/latitude for point B. These longitudes and latitudes are not available in OSM XML data. How can I find the distance between these two points?

Answer 1

Unless you're in the desert or somewhere like that, then there are likely to be nodes nearby. You should never expect to find a node at exactly the same point as you are searching for. (if this isn't 'obvious', I recommend you read up on floating point comparisons)

So you need to find the closest node(s) to each of your query locations. I used a KD-Tree for something like this, see: Looking for an algorithm to quickly find the closest point on a road network (or other graph)

You will need to modify the basic search to find "all points within distance X", or "closest point" depending on your precise needs.

In a city there's a good chance the closest node is within 10s of metres. In rural areas, it might be kilometers. Areas with sparse road networks in OSM (eg. one of my customers uses my routing engine in Africa) will have to search for larger distances.