Finding Similar Map Paths

I'm looking for an algorithm which, when given a particular route on a map with attributes such as incline/distance/shape/etc, can find a route which is similar (in terms of the attributes) but starts at a different point or in a different region on the globe.

Obviously it will be impossible in almost all cases to find a perfect fit but I'm looking for a "best match" sort of system with a method of measuring the similarity as well ideally.

I have tried looking, but most of my queries come up with either Map Matching problems or route similarity for GPS points along the same path. I may not know the correct terminology! Is there a name for this problem? What algorithm I can use to solve this?

• Are "routes" constrained to a line (road/path/etc) network? How do you prevent the algorithm deciding the closest route is the source route but just a tiny bit shorter/longer? Commented Feb 5, 2017 at 20:40
• "Similar in terms of the attributes" makes sense but it's so vague that it permits a wide array of possible solutions. Could you be more specific? Commented Feb 5, 2017 at 22:17
• @Spacedman Yes, the routes are constrained to a road network. The intention is to take a road route from, say, China, and find a very similar path that is near, say, my house. I'm not sure the best way to actually implement that constraint. Commented Feb 6, 2017 at 4:12
• @whuber Sorry. To clarify, having similar inclines (in similar areas of the route) and similar total distance are the most important. Commented Feb 6, 2017 at 4:13

Map matching is different from what you are looking for. Map matching is the proper way of matching an erroneous GPS observation to the linear street network. Your question has nothing to do with GPS points either. Because you want to compare the pattern of the static routes (non temporal) and find the similar ones. What you are looking for is linear feature matching. The literature related to the GPS trajectory is spatio-temporal pattern matching that goes under the title of the Trajectory Pattern Mining.

For further info, have a look at the chapter Trajectory Pattern Mining from the book computing with spatial trajectory. You will get some ideas on how to compare and contrast (e.g. via azimuth, segments length, sinuosity, beeline, etc) various trajectories.

Your question is based on vector data. I do however think that you are better served with converting the question to a raster analysis. In doing so you will also to some extent generalize your question.

An algorithm to solve your question would be as follows:

1. Rasterize the original route and make each cell carry parameters according to your specifications (incline/distance/shape/etc). The fact that a road is present is also a parameter. This becomes a one dimensional list with n objects -> routelist(n)

1. Find a test area where you know there is a at least one replica of your original route. Rasterize this area with the same parameters as your original route. This is raster a.

1. Start with cell 1,1 in raster a and move through the whole raster in an orderly way.
2. For each cell a function is called. This function checks if the cell corresponds to routelist(0), if so the same check is done on the surrounding cells. With success the function goes on to check the cell for routelist(1) and so on. If successfull all the way to routelist(n) the coordinates are stored as an alternative route in routelistcopy(n)
3. Repeat until you reach the last pixel in the raster.

Above you will see three options for routes according to the parameters in routelist.

Futhermore:

• The sample rasters above are measured according to just one parameter. In your real world challenge one pixel will be a combination of several parameters.
• Should I have this task I would try to write the function mentioned above in a recursive way. This would be more efficient and solve the issue of "diverging tracks" - where you have several alternative tracks with the same starting point.
• The turns of your route is not considered an issue. This means that answers are a list of pixels connected in the same order as your original route. Twists and turns are not an issue. You might have to write the algorithm so that self-intersecting routes is not a part of the solution.
• Design the algorithm so that you can set different tolerance levels for the criteria in play. This will give you more flexibility.
• In an operative setting the whole process can be made more efficient by screening the area for occurrence of pixels according to your specifications. If they are not there the survey area is a negative, so no reason to use time to analyse the area.