title: GPS Navigation Algorithm
body: <p>I have thousands of input GPS values from a vehicle that I want to map to specific values given by nodes on a road graph. Take the below image. Each Node (A-F) has information about the previous edge that connects to it (as well as latitude/longitude). I want to match some of this information to each GPS point in my input GPS coordinates.</p>
  
  <p>Road Graph
  <a href="https://i.stack.imgur.com/L3Yli.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/L3Yli.png" alt="enter image description here"></a></p>
  
  <p>So far I am able to do so, but there are some edge cases. Take the image for example, when we reach node B we think we could be on path BCD or path BEF. It isn't until the nodes are far enough apart that we know which route we have taken with the input. This is because roads aren't simply a 2D line. They have width and the vehicle could be on the edge of the road. Determining which road it is on is difficult because we do not know the width of the road. So, when we arrive at node B the vehicle can be between BC or BE. It isn't until later down each path do we know where we are at.</p>
  
  <p>That being said, we can traverse each route until we have only one option and therefore we know we are on that road. We can backfill the data from all the previous nodes on the correct route. I have issues coming up with an algorithm for this, however.</p>
  
  <p>How can I handle this in code? I've thought about doing a DFS at every intersection and figuring out which path has the highest count of edges that contain input points from the vehicle. Is there a better way?</p>