Elevation should be guessed from start and end if going through a tunnel #713

Closed
karussell opened this Issue May 4, 2016 · 21 comments

Projects

None yet

4 participants

@karussell
Member
karussell commented May 4, 2016 edited

This Arlberg tunnel is the best example, which is I think a lot smoother than we show ;)

The same should be done for bridges like here

@karussell karussell changed the title from Should elevation be guessed from start and end if going through a tunnel? to Elevation should be guessed from start and end if going through a tunnel May 27, 2016
@highsource
Contributor

Hi,

I'd like to give it a try (as a "getting started in Graphhopper" issue)
I understand the issue pretty well but I need a couple of pointers to get started.

Here's my understanding of the task.

Elevation providers give elevation on the surface - which is very different for nodes of the bridge or tunnel. So instead of taking the provided elevation we should somehow calculate elevation of tunnel/bridge nodes.

To do this, for each tunnel/bridge (for verbosity I'll only refer to bridge from now on) we'll need to find "entry" nodes and "inner" nodes of the tunnel. Then we'll need to calculate the elevation of "inner" nodes based on the "outer" nodes, possibly taking into account the surface elevation as maximum (for tunnels) or minimum (for bridges). The tunnel may "dive in" in places where surface elevation is too low.

The connected component of the tunnel will be normally quite simple (just connecting two entry/exit nodes), but there may be more complex structures with multiple entry/exit nodes. Still, these structures will be relatively small.

Now to do this we'll need to identify individual tunnels and find out inner and outer nodes.
A tunnel is basically a connected component where all edges have type "tunnel". Outer nodes are those which have "tunnel" as well as non-"tunnel" edges. Inner nodes only have "tunnel" edges.

The easiest would to traverse the graph in some postprocessing step. If we encounter a "tunnel" edge then we build the connected component from this edge (starting from the nodes of the edge), detect inner/outer nodes (by looking at edges), the calculate elevations of inner nodes and then mark edges as "tunnel-processed".

However this postprocessing will require (and modify) the already built graph. I'm not sure it this is OK, maybe this is needed to be done while reading?

If this is the case then it is harder. We'll need to maintain some kind of tunnel nodeset structure while reading and use them to recalculate elevations after everything's read.
Something like:

  • When we read a tunnel edge, we check if its nodes already have associated tunnel nodesets.
    • If not, we create a new tunnel nodeset, add nodes to it and associate this nodeset with nodes.
    • If yes then this may be the same nodeset or two different nodesets
      • In case it's the same nodeset there's nothing to do - nodes of this tunnel edge already belong to the very same tunnel nodeset
      • In case it's a different nodeset then we have to merge them to one nodeset and reassociate nodes with the merged nodeset
  • We'll also need to mark nodes as "tunnel", "bridge" and "normal" to find out inner nodes (only marked with "tunnel" or only marked with "bridge") vs. outer nodes (marked as "tunnel" + something else)
  • Finally we will have one nodeset for each of the tunnels and we'll know which are the inner and the outer nodes
  • Calculation of elevation is some vector math, some averaging based on coordinates and proximity, should not be too complex

The latter approach will work but will require more memory when reading:

  • We'll have to track "bridge"/"tunnel"/"normal" per node
  • We'll need tunnel nodeset - at least one per tunnel, at most (during processing) ~ one per tunnel edge/2
  • We'll need to associate "tunnel" nodes with nodesets

So this won't be quite memory efficient on reading.

I'd be grateful for a couple of pointers on what do you think would be a way to go and maybe a couple of interfaces/integration point for where to build it in.

My goal with this issue is primarily to start learning GH internals and I think it fits quite well.
If you've another issue candidate for me, I'm open for suggestions.

Best wishes,
Alexey

@karussell
Member

Would be really nice if this issue get be resolved!

If you've another issue candidate for me, I'm open for suggestions.

This is a relative complex issue as getting started but you can try. It would involved several parts: storing bridge/tunnel attributes in the graph, post-processing hook (very simple), in-place geometry storing (see below) and math stuff for interpolation.

Some other important and a bit simpler problems are the issue mentioned below (#500) and #236 but maybe less fun :)

The tunnel may "dive in" in places where surface elevation is too low.

What do you mean here?

I'm not sure it this is OK, maybe this is needed to be done while reading?

This is okay, although we have to implement an optimization for the geometry storage. Currently if we update the geometry a new point list is appended, but as especially geometry storage is very limited (#500, will run out of capacity in ~12 months) we have to do some "inplace" geometry replacement if length is unchanged.

I would also prefer the procedure with the post-processing as then it gets much simpler. I'm not sure I have understood the other option for "while reading" as the elevation is not known and/or needs to be interpolated from e.g. two entry nodes and would still need a geometry update.

@highsource
Contributor

The tunnel may "dive in" in places where surface elevation is too low.

What do you mean here?

Assume we have a tunnel with entry points at 100m but the surface goes as low as 90m somewhere in the middle. The tunnel will the probably go down (below 90m) and then up.
Ok, this is probably too weird (if real at all) to consider. Let's dismiss it.

Could you please point me to the post-procesing hook?

I'll also take a look at #500.

@karussell
Member

Could you please point me to the post-procesing hook?

We bundle together the low-level API parts in the GraphHopper class, and post processing would then take place there (GraphHopper.postProcessing) https://github.com/graphhopper/graphhopper/blob/master/core/src/main/java/com/graphhopper/GraphHopper.java#L943

@highsource
Contributor

Hi,

Ok, thank you.

Let me reiterate individual points:

Store bridge/tunnel attributes in the graph

I can detect tunnels and bridges via way.hasTag("tunnel", "yes") or way.hasTag("bridge", "yes"). This value should be stored in the graph. I guess this is what flags are for. I'll need at least two bits to store at least three values (bridge/tunnel/neither). Probably another bit to mark processed edges?
flags seem to be stored as int or optionally long so that storage space is quite limited. Can I have two or three bits from there? I'd assume so.
FlagEncoders seem to be the right place to implement storage of these attributes.

Post-processing hook

After the graph is built I could iterate over edges. For each non-processed edge build a connected component, calculate outer/inner nodes, calculate/update new elevations, mark edges as processed. This routine would work on Graph and could be invoked in GraphHopper.postProcessing.

I've checked AStar and Dijkstra so see how routing is done, I think I'll be able to figure out the connected component.

In-place geometry storing

I think what's need for elevation updates is implemented in #769. Elevation updates won't grow maxGeoRef since they don't make PointLists longer.

Math stuff for interpolation

Have no idea yet but should be doable.

Any hints, corrections or suggestions?

Sorry if I write a bit too much. That's basically the third hour that I look into GraphHopper code. I want to be sure I'm on the right track therefore so elaborate.

Best wishes,
Alexey

@karussell
Member
karussell commented Aug 18, 2016 edited

FlagEncoders seem to be the right place to implement storage of these attributes.

Yes, exactly. See e.g. the roundabout bit in the abstract flagencoder. Of course every flag encoder then duplicates this information, see this discussion how I think we could solve this (later)

I've checked AStar and Dijkstra so see how routing is done, I think I'll be able to figure out the connected component.

You should be able to use simple bread first search (BreadthFirstSearch), no need for weights.

I think what's need for elevation updates is implemented in #769.

Yes, that is cool 👍

Any hints, corrections or suggestions?

No, sounds all good. Regarding the math: for now you could just pick all entry nodes and calculate a mean value for the elevation. Later on we could improve this if this makes too much trouble?

@highsource
Contributor

I'm not quite sure if I should add my bit fields to the AbstractFlagEncoder or to create an extra elevation encoder.

Adding new flags to the AbstractFlagEncoder seems more natural. But then they are duplicated in every encoder and that takes too many bits.

Extra encoder saves bits but would require explicit configuration.
Also elevation looks a bit weird in the sequence of car,foot,bike,bike2,mtb,....

I currently tend to a separate encoder - what do you think?

@highsource highsource added a commit to dbsystel/graphhopper that referenced this issue Aug 21, 2016
@highsource highsource Issue #713 part 1: saving K_TUNNEL and K_BRIDGE flags. Due two
additional bits we'll now have to use 64-bit flags in most cases.
78e16ae
@highsource highsource added a commit to dbsystel/graphhopper that referenced this issue Aug 21, 2016
@highsource highsource Using 8-byte flags. #713 29fb33b
@highsource highsource added a commit to dbsystel/graphhopper that referenced this issue Aug 21, 2016
@highsource highsource First draft implementation of #713. ee0ec44
@karussell
Member

In a later work we should move those bits into a data encoder like I've done in this PR #730

@highsource
Contributor

I've got the first draft of elevation estimation for tunnels:

dbsystel@ee0ec44

Seems to work but requires more brushing up and testing. I was quite surprized to see that Arlberg tunnel goes up but apparently it has a very small surface section.

I'm also not quite sure about the math for 3+ outer points. For each of the inner nodes I calculate distances to all of the outer nodes and then use 1/distance as weights to average the elevation.

@karussell
Member

Thanks - looks really nice at the first glance!

I was quite surprized to see that Arlberg tunnel goes up

You mean, that the tunnel itself has an elevation difference?

but apparently it has a very small surface section.

what do you mean here?

I'm also not quite sure about the math for 3+ outer points.

An iterative heuristic approach could work where one starts with two entry nodes with maximum elevation difference (to try to pick the tunnel ends), then doing the interpolation and calculating new entry nodes for the potentially new other subnetworks. Do you know what I mean :) ? I think we should for now not overcomplicate things, just make it working for >90% of the tunnels :)

@highsource
Contributor

Thank you.

I was quite surprized to see that Arlberg tunnel goes up

You mean, that the tunnel itself has an elevation difference?

but apparently it has a very small surface section.

what do you mean here?

I was wondering why the tunnel goes up and peak after around 6 km:

If there's just one entry and one exit point, I'd expected the tunnel to go more or less linear. But this did not happen here.

Then I've taken a closer look and it appeared that around that point the tunnel goes to the surface. There is a small surface section - which gets the right elevation from the elevation provider. See the goal point here - there's no tunnel, there's a surface area. It actually looks like a bridge in the middle of the tunnel. :)

I think we should for now not overcomplicate things, just make it working for >90% of the tunnels :)

If so then I'd say my math is quite simple. I'm not quite sure if it gives acceptable performance, but from the conceptual POV averaging the elevation depending on distance feels fine. The closer you get to one of the entry points the higher is it's influence. With distance=0 its influence should be "infinite" meaning we should be getting exactly its elevation.

I'll try to clean up in the next days and then send you a PR.

@karussell
Member

Then I've taken a closer look and it appeared that around that point the tunnel goes to the surface.

Oh, interesting. So it looks like this is then already correctly handled :) ? Still a bit strange from the tunnel design perspective (maybe security?)

The closer you get to one of the entry points the higher is it's influence.

Sounds good. And will it give you a linear interpolation of just two points or will it be some curvature?

@oblonski
Member

This is what Wiki writes about the Arlberg-Tunnel: "Vom Ostportal (1223 m ü. A.) steigt der Tunnel über 3940 m mit 1,67 % bis zum Scheitel bei der Rosannaquerung (1318 m ü. A.) an. Danach fällt er auf 10.032 m Länge mit 1,3 % bis zum Westportal auf 1188 m ü. A. ab.". Thus, there should be 95m up and 130m down :).

@highsource
Contributor

There are extra routines for 1 and 2 entry points (linear). This reverse-distance-averaging is only applied to 3+ points.

Here's a Wolfram Alpha request for the 2-point case where points are in the distance of 20 and have elevations 10 and 100. This looks pretty linear, maybe there's some curvature but not noticeable.

Looks a bit worse for 3 points:

Maybe go quadratic, I'll see later on.

@highsource
Contributor

@oblonski I think it matches: start and end point are not set exactly at the ends of the tunnel. I'll test more later on.

@highsource highsource added a commit to dbsystel/graphhopper that referenced this issue Sep 16, 2016
@highsource highsource Issue #713 part 1: store tunnel and bridge tags. b0b3c8a
@highsource
Contributor

For testing purposes: Tunnel de Monaco.

@mprins
Contributor
mprins commented Sep 19, 2016

Assume we have a tunnel with entry points at 100m but the surface goes as low as 90m somewhere in the middle. The tunnel will the probably go down (below 90m) and then up.

Ok, this is probably too weird (if real at all) to consider. Let's dismiss it.

actually this is a common case, where a tunnel goes sub-marine, eg. Westerscheldetunnel

@highsource
Contributor

@mprins Right. However we can't do much in this case because we don't know how deep the water is.

Generally we can assume that the tunnel goes deeper that the Earth surface - probably even, like 2-5-10 meters deeper. This could improve a few cases for mountain tunnels - but probably not for the submarine tunnels.

@karussell karussell added a commit that closed this issue Sep 23, 2016
@highsource @karussell highsource + karussell interpolate elevations of tunnel/bridge structures #798, fixes #713 90a3844
@karussell karussell closed this in 90a3844 Sep 23, 2016
@highsource
Contributor

Maybe tag with improvement and 0.8?

@karussell
Member
karussell commented Sep 23, 2016 edited

Sure, done (already done for #798). I find it a bit ugly this separation of issue and pull request. IMO there is one issue with all the tags and stuff and then you can have multiple PRs inheriting most settings ...

@karussell karussell added this to the 0.8 milestone Sep 23, 2016
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment