On Sun, Aug 18, 2019 at 09:25:01AM -0700, Richard Fairhurst wrote:
> But just as long established in OSM is the principle that - since mappers
> are our most precious resource - we optimise for the mapper, not for ease of
> consumption. Allowing relations to be unsorted is an example of that. If a
> relation represents a linear route, it's a SMOP to put the ways in the right
> order.
Sure, we are not talking about the 80% linear routes (of which less than a
quarter is unsorted btw, so it doesn't seem to be a too difficult thing to
do for the mapper.) Happy to processed them in any order.
We are talking about routes which are non-linear by design (split direction,
alternatives, accesses, circular, self-intersecting), broken relations,
unfinished relations, directed routes (think MTB downhill) and truely
botched relations.
> There are two obvious strategies. 1 is: create an empty polyline P with
> endpoints P1 and P2; iterate through the relation members; every time you
> encounter a way with an endpoint P1 or P2, add it to the polyline
> (potentially in reverse order) and remove it from consideration; repeat
> until there are no ways left. This is broadly the approach I've used until
> now.
>
> 2 is more involved but more fault-tolerant and flexible; create a routing
> graph, then route from the relation's startpoint to its endpoint using a
> very heavy uplift for members of this relation. This is a useful approach
> where the route actually _is_ non-contiguous but you nonetheless want to
> include connecting routes between the sections. (Quite a lot of American
> rail-trails are like this, as are several UK National Cycle Network routes.)
> This is an approach I'm investigating at present.
I have experimented quite extensively with using routing algorithms for the
relation assembly. Even determining a start and endpoint of the relation is
already messy. There are corner cases everywhere. Example: a relation with
exactly two open ends should be an open and shut case, right? Wrong! It might
also be a circular route with two access ways.
Any sorting suggestion that either starts with "Step 1: install a planet-
wide OSRM with a foot profile" or involves a complicate algorithm that makes
a lot of undocumented assumptions about the relations cannot be in the
interest of OSM.
The first hinders the use of our data. You shouldn't need be able to afford a
2000$ server just to assemble a couple of routes.
The second makes life harder for mappers because it becomes non-obvious how
they can fix their stuff when it breaks in their favourite software. And
worse, even if they fix it for one, it might acutally breaks the other software
which is working on different assumptions.
We do happen to have a clear rule for unbroken linear routes: just assemble
in the obvious way, no matter if sorted or unsorted. We don't have any rule
for anything more complicated that mappers can follow to get the desired
effect. We already fail with something as simple as a directed unbroken
linear routes and circular routes. There is no single recommended way to
define the start point.
> Approach 1 does of course fail if the relation doesn't represent a single
> linear route. That would, however, still be true if the route was ordered.
With sorted routes, your approach 1 becomes quite a bit simpler: just take
ways in order, adapt direction so that the gaps are minimal. Assemble.
That algorithm gives you reasonable results for the following cases
automatically: linear, broken, unfinished, circular and self-intersecting
routes.
Assuming we don't care what happens to really botched relations, all cases
except one that I listed initially are covered with one single simple
instruction to the mapper: sort your route.
What remains are routes which are split/have alternatives/access routes etc.
Gut feeling tells that roles will solve those cases but I get back to you
on that once I had a go at implementing it.
Sarah
_______________________________________________
Tagging mailing list
Tagging@openstreetmap.org
https://lists.openstreetmap.org/listinfo/tagging
