2
$\begingroup$

I have a first data set which is a list of train stops with coordinates (lat, lon), but not the "links" between the nodes/stops (this could thought of as a null or empty graph).

I have a second data set which has the start / end stop coordinates of a particular train line and also intermediary stopping points. However the data for the train line is missing some of the intermediary stops, so parts of the trip are represented as straight line segments which pass more or less closely by the missing intermediary train stops coodinates from the first data set.

What kind of (pathfinding?) algorithm would allow me to infer from this data set the full path of the train ? I've heard about pathfinding algos like A*, breadth-first-search, etc. but i'm not sure if these can be applied to this particular problem.

Thanks for any help or tips you can provide.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Algorithm

  1. create the two-nearest-neighbors graph $N_2$ using the first data set. That is, let each station be connected to the two closest stations.
  2. for a path in the second data set, assume that the train must have been traveling along a geodesic (shortest path between two vertices) on $N_2$, and fill in the missing stations accordingly.

Example: BART

Bay Area Rapid Transit

On input the partial path (MacArthur, Lafayette), the Algorithm outputs

(MacArthur, Rockridge, Orinda, Lafayette),

which is correct, even though $N_2$ has a spurious edge between Rockridge and Ashby.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Great, this clarifies a lot for me. Now i just need to put it into code ;D. Thanks, answer accepted. $\endgroup$
    – thogrhm
    Commented Oct 27, 2014 at 8:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .