9

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?

  • 1
    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? – Spacedman Feb 5 '17 at 20:40
  • 1
    "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? – whuber Feb 5 '17 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. – Chris Foster Feb 6 '17 at 4:12
  • @whuber Sorry. To clarify, having similar inclines (in similar areas of the route) and similar total distance are the most important. – Chris Foster Feb 6 '17 at 4:13
6
+100

Map matching is different from what you are looking for. Mapmatching is the proper way of matching an errorness 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 (in the sense of GIS not i.e. machine learning) matching. The literature related to the GPS track is spatio-temporal pattern matching that goes under the rubric of the "Trajectory (spatial temporal) Pattern Mining".

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

4

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)

enter image description here

  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.

enter image description here

  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.

enter image description here

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.