How to predict routes using clustering data I've been working on a ship route prediction algorithm such that given the past and current trajectory of a ship I am able to estimate the future one. The trajectories are represented as a sequence of coordinates (latitude,longitude).
This is what I have done so far:

*

*Route clustering: Using past information of ship trajectories within an area of interest, group these routes according to proximity and similarity, as illustrated in this image:




*Classification: Given the past and current trajectory of the target ship, determine its corresponding cluster, e.g. the black line is the current trajectory and it should be associated with the blue cluster:




*Prediction: Predict the upcoming trajectory.

I was successful in steps 1 and 2 and I'm trying to figure out how to proceed with step 3.

*

*First I tried to perform linear regression to each cluster in order its "identifying route" and then try to overlap it with the black line. Unfortunately this is not good in many scenarios, e.g. by moving the line it may end up overlapping land when the cluster is near shore.

*I tried to use a neural network trained to accept sequences of (lat,lon) points as input and output the next ones, but I had little success in terms of precision.

I wonder if I am looking at this all wrong and if there are better approaches to address step 3. Does anyone have any suggestions?
 A: Because of my low reputation I'll use this reply as a comment. 
Fitting a curve over the points of the blue course isn't enough? There are a lot of methods out there, one of them being the classic spline. 
You can also try your own heuristic. I'll give some that came in mind.
Depending on the number of points you could create a graph in which the coordinates are the nodes and the vertices have cost measured by the euclidean distance (or any other distance method) between the coordinates. Then, you use some graph theory algorithm to take the minimum cost spanning tree of this graph. It will be like, given the route from the other ships, the optimal one. 
Another method would be based on the KNN. Take the origin point of the ship. Then take the N (arbitrary value) points and do the mean. From this next point, do the process of finding the next one from the N closest points. For this you will have to create some rule to discard coordinates, so you don't move back.
Hope it give you some more ideas. Please comment back if you like me to throw more, as I would like to  discuss this in more detail
