Finding Similar Map Paths

Question

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?

Answer 1

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.

Answer 2

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)

2. 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.

3. Start with cell 1,1 in raster a and move through the whole raster in an orderly way.
4. 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)
5. 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.