OpenStreetMap

Sorting route relations

Posted by lonvia on 10 September 2017 in English (English)

waymarkedtrails.org, the site to show all things route related, has always taken care to try to put route relation members in a sensible order before displaying them. A couple of weeks ago this has changed. The site now assumes that the members of each relation are already in the correct order. The reason for that is simple: sorting route relations is hard.

Before explaining why sorting is hard, let me explain why order even matters. As long as you simply want to display the route on a map, the order is not important. Simply color each way in the relation to your liking and the route is nicely visible for a human reader. However, waymarkedtrails.org does a bit more than that. It displays an elevation profile and allows to download a GPX of the route, so you can put it onto your favourite mobile device. When the route is not sorted in the expected order, then the GPX is unusable for many applications, for example in Garmin Basecamp.

So why not sort the route automatically? On first sight, this seems to be a simple task. After all, a route should be a simple linear connection from A to B. Unfortunately, the real world is much more messy.

Even the most simple case of a linear route from A to B already has two solutions to the problem. The route may go from A to B or from B to A. In most cases the direction doesn't really matter but there are exceptions. Take a downhill mountain bike route, for example, or a nature trail with information panels that should be visited in the correct order.

Then there are loop routes which end at the point where they started. When sorting automatically there is no way to determine the starting point of the route. In both cases, we could add extra tagging to mark the start and end points. But why add the extra work when sorted route give the start and endpoints clearly at the beginning and end of the list?

Also, not all routes in OSM are strictly linear: there are routes with directional deviations. This can often be found in cycling routes which might go through oneway streets. Sometimes these deviations mapped with forward/backward roles but not always. Then there are routes that contain alternatives, side trips to lookout points and alternative access points.

waymarkedtrails could surely use some heuristics to get all these cases right most of the time but then there is no way to fix the decision if it gets it wrong. I think that is much better to leave the final decision about the order to the mapper.

Keeping your routes in the right order isn't too much work either. The JOSM relation editor is a very powerful tool when it comes to sorting relations. In the list of relations there is a column that immediately shows you the connectivity of your relation members. It can even handle directional deviations and roundabouts. Keeping an eye on the connectivity column is always a good idea while clicking your route together. It gives you immediate feedback when you've missed part of the route or created a small dangling end when you forgot to split a road. If you already have mapped your routes without sorting them, there is even a button to sort the members for you.

So, overall sorted routes are an advantage for everybody. They don't solve all problems with routes but they are a huge step forward in improving the quality.

Finally some numbers about the current state.

Hiking routes:

  • 74337 linear routes already sorted (65 %)
  • 14608 linear routes, not sorted (13 %)
  • 24992 non-linear routes (22 %)

Cycling routes:

  • 28020 linear routes already sorted (55 %)
  • 5164 linear routes, not sorted (10 %)
  • 17639 non-linear routes (35 %)

Comment from Tomas Straupis on 10 September 2017 at 13:39

So how do you expect non linear and non circular routes being mapped/sorted? Say the route of the shape Q - you start on the end of tail, get into a curcular part, then go back the tail route section to get back to start/end point? Or what has to be done with side trips? Because when its simple linear/circular, you can do as well as josm button "sort relation members" (except showing the start point).

Hide this comment

Comment from lonvia on 10 September 2017 at 17:04

For the Q-shaped route: add the tail twice, once at the beginning of the relation and once at the end. Then it boils down to a linear route.

Side trips and similar should be marked with a special role. The situation there is a bit messy at the moment because there is no agreed schema yet. Looking into that is on my todo list.

Hide this comment

Comment from NunoCaldeira on 10 September 2017 at 19:05

One thing I wished that would be fixed on that website is profile elevation when there's tunnel (first node of tunnel elevation - last node of tunnel). Simple task to properly display the elevation of routes that have tunnels. Currently it doesn't display elevation profile if a tunnel is part of the relation.

Hide this comment

Comment from Tomas Straupis on 10 September 2017 at 20:24

lonvia: brilliant! Putting way twice would also solve a problem of actual route length calculation.

Hide this comment

Comment from lonvia on 10 September 2017 at 21:16

@NunoCaldeira Indeed, same problem with bridges actually. I have opened a ticket for this: https://github.com/waymarkedtrails/waymarked-trails-site/issues/282

Hide this comment

Comment from Polyglot on 11 September 2017 at 05:44

JOSM's PT_Assistant plugin now also helps with cleaning up bicycle and hiking routes. Where the ways forks and thus forward/backward roles are needed, it will colour both 'legs' in different colours. This makes adding those roles and especially knowing whether forward or backward is needed a lot easier. This is not only necessary on oneway streets. Bicycle routes will also fork when cycleways are drawn on both sides of the road and on roundabouts with split ways, where they might not use the whole roundabout.

Polyglot

Hide this comment

Comment from ToniE on 11 September 2017 at 12:05

@lonvia: really brilliant. I never assumed that you sort the routes. @Tomas Straupis: and it allows calculating the elevation profile.

Toni

Hide this comment

Leave a comment

Parsed with Markdown

  • Headings

    # Heading
    ## Subheading

  • Unordered list

    * First item
    * Second item

  • Ordered list

    1. First item
    2. Second item

  • Link

    [Text](URL)
  • Image

    ![Alt text](URL)

Login to leave a comment