RFC: Consider heightmeters for routing
Hello, this is an idea which I think about some months, but have not had the time to do some programming. Maybe anyone else has the same thoughts, so I describe my idea here. As I use my etrex mostly for biking, I think it may be usefull to consider th height differences of the ways ar routing. In my area are a lot of hills and there are often ways across the hills and ways surrounding the hills with not much difference in length, but obviously a difference in height meters. It would be reasonable if the etrex chooses the way around the hill. So my idea is, to virutally lengthen the roads by the height distance. This is, if a road has 1km and goes straight then it gets an entry of 1 km in the routing data.. If another road has a length of 1km and a height difference of 10m, then it gets a length entry of 1.1km. And a really hilly road with a length of 1km and a height of 100m will get an entry of 2km. In other words, I would add a percentage of the height to the lenght. This should made the etrex choose the flater roads. 1. What do you think in general of this idea? 2. Is it usefull to implement the heigth calculation for each segment into mkgamp or splitter or should it be an external tool? 3. Is there an existing java library, which calculates me the height of each coordinate from an world model (maybe based on the SRTM data)? Any comments? Regards, Johann
Hi Johann,
So my idea is, to virutally lengthen the roads by the height distance. This is, if a road has 1km and goes straight then it gets an entry of 1 km in the routing data.. If another road has a length of 1km and a height difference of 10m, then it gets a length entry of 1.1km. And a really hilly road with a length of 1km and a height of 100m will get an entry of 2km. In other words, I would add a percentage of the height to the lenght. This should made the etrex choose the flater roads.
What happens when you go downhill, does it make the roads shorter? Personally, I like the hills when I am cycling so I don't think I would use such a feature. Cheers, Mark
Mark Burton schrieb:
Hi Johann,
So my idea is, to virutally lengthen the roads by the height distance. This is, if a road has 1km and goes straight then it gets an entry of 1 km in the routing data.. If another road has a length of 1km and a height difference of 10m, then it gets a length entry of 1.1km. And a really hilly road with a length of 1km and a height of 100m will get an entry of 2km. In other words, I would add a percentage of the height to the lenght. This should made the etrex choose the flater roads.
What happens when you go downhill, does it make the roads shorter?
No, it doesn't matter, which direction the road goes. It has an height difference an gots therefore an penalty. See the following example: Start at height 500m Destination at height 520m Maybe there are four alternatives, how I can get to the destination 1. +20m 2. +100m, -80m 3. -80m, +100m 4. +30m, -15m, +5m All height differences get a positive penalty, no matter which direction. So the route with the least 'up and down' gets the least penalty and should be prefered. If I would consider the direction (which is impossible at gmapsupp creation time) then the resulting penalty would always sum up to the real height difference and there will be no difference.
Personally, I like the hills when I am cycling so I don't think I would use such a feature.
In general I agree with you. I like the hills too. For my recreation cycling I choose the ways, which looks best to me at the moment, not the ones which tells my etrex me to take. :-) But sometimes I do really long rides (>140km), and then I don't want to waste my condition on some hilly routes, if I can reach the destination on a flat alternative, maybe alongside a river. I expect, for the 'short range' routing there will be not much effect, as there are to less alternatives to choose from. But on the 'long range' routing it may be the difference between a route over hilly region or alongside a river. As I have said in my first mail, this is only a idea, how it could be work. I have not written a single line code for this, and as the summer is comming, I think I will go more cycling than sitting in front of my computer. :-) Greetings Johann
And where do you intend to get your height information from???? Outside of mountaineous regions SRTM is fit for use, in the mountains where it matters it is useless. Even Jonathan de Ferrantis 1" files are not really good (often 20-50m off). Rather penalise by using the inclination key. I like the idea, but I don't think it will work on Garmin handhelds. If you really want to lengthen the roads, do you think this is possible CPU wise? 1. You would have to attach to every polyline highway=* a height profile - which will take a very long time, 2. you will have to lengthen it (how do you want to do that? Insert curves into straight lines? - that will not look good. You can't make the curves to abrubt, otherwise the PNA thinks it has to turn (imagine going a straight line and the routing popping up --> turn left... Better put your efforts into decrypting the Garmin DEM so that we can rebuilt it. Then after the route is calculated just have a look at the profile and correct it at places where there is too much incline (You could instead export it to another program and add height information to it but inside Mapsource would be more comfortable). However having other systems (I think there is even one webpage based on OSM which does exactly what you want) that do work, why not use them and omit to try to implement it onto your PNA? Also steepness plays a part. A steady rise will be nicer for going up than 100m at 30% and then 500m flat - while another street 600m long with steady rise would be penalised the same (but much easier to cycle up). I agree that you don't need to know whether it goes up or down, but you need the incline. Now taking that into account will make calculating the penalty even more CPU heavy (not only the difference, but also correlating the incline). Is it better to push up 100m then go level or to go up 130m at easy incline and then 30m back down? Johann Gail wrote:
Mark Burton schrieb:
Hi Johann,
So my idea is, to virutally lengthen the roads by the height distance. This is, if a road has 1km and goes straight then it gets an entry of 1 km in the routing data.. If another road has a length of 1km and a height difference of 10m, then it gets a length entry of 1.1km. And a really hilly road with a length of 1km and a height of 100m will get an entry of 2km. In other words, I would add a percentage of the height to the lenght. This should made the etrex choose the flater roads.
What happens when you go downhill, does it make the roads shorter?
No, it doesn't matter, which direction the road goes. It has an height difference an gots therefore an penalty.
See the following example:
Start at height 500m Destination at height 520m
Maybe there are four alternatives, how I can get to the destination
1. +20m 2. +100m, -80m 3. -80m, +100m 4. +30m, -15m, +5m
All height differences get a positive penalty, no matter which direction. So the route with the least 'up and down' gets the least penalty and should be prefered. If I would consider the direction (which is impossible at gmapsupp creation time) then the resulting penalty would always sum up to the real height difference and there will be no difference.
Personally, I like the hills when I am cycling so I don't think I would use such a feature.
In general I agree with you. I like the hills too. For my recreation cycling I choose the ways, which looks best to me at the moment, not the ones which tells my etrex me to take. :-)
But sometimes I do really long rides (>140km), and then I don't want to waste my condition on some hilly routes, if I can reach the destination on a flat alternative, maybe alongside a river.
I expect, for the 'short range' routing there will be not much effect, as there are to less alternatives to choose from. But on the 'long range' routing it may be the difference between a route over hilly region or alongside a river.
As I have said in my first mail, this is only a idea, how it could be work. I have not written a single line code for this, and as the summer is comming, I think I will go more cycling than sitting in front of my computer. :-)
Greetings Johann
_______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Thank you for your comments, it corrects some of my thoughts.
And where do you intend to get your height information from???? Outside of mountaineous regions SRTM is fit for use, in the mountains where it matters it is useless. Even Jonathan de Ferrantis 1" files are not really good (often 20-50m off). I haven't digged that deep at the moment. I thought, SRTM would be a good start. It haven't known, that it is unusable in the mountain regions. :-(
Rather penalise by using the inclination key. Good idea, could be considered. I like the idea, but I don't think it will work on Garmin handhelds.
Exactly therefore I would try it by lengthen the roads. This is what garmin handhelds do. Calculate a route by its lengths.
If you really want to lengthen the roads, do you think this is possible CPU wise? 1. You would have to attach to every polyline highway=* a height profile - which will take a very long time, 2. you will have to lengthen it (how do you want to do that? Insert curves into straight lines? - that will not look good. You can't make the curves to abrubt, otherwise the PNA thinks it has to turn (imagine going a straight line and the routing popping up --> turn left... I would not modify the ways, but simply change the routing tables. As far as i understand the img format, there is the NOD section, which contains the lines to draw on screen. This data should not be changed. And there is a NET section, which contains the routing data. This data contains is a length for each segment between two crossings. I would change this length by a factor depending on the height and incline data.
Better put your efforts into decrypting the Garmin DEM so that we can rebuilt it. Then after the route is calculated just have a look at the profile and correct it at places where there is too much incline (You could instead export it to another program and add height information to it but inside Mapsource would be more comfortable). However having other systems (I think there is even one webpage based on OSM which does exactly what you want) that do work, why not use them and omit to try to implement it onto your PNA?
For me the DEM is useless, as my unit cant display it. But maybe i will buy a new one, if mkgmap learns DEM...
Also steepness plays a part. A steady rise will be nicer for going up than 100m at 30% and then 500m flat - while another street 600m long with steady rise would be penalised the same (but much easier to cycle up). I agree that you don't need to know whether it goes up or down, but you need the incline. Now taking that into account will make calculating the penalty even more CPU heavy (not only the difference, but also correlating the incline). Is it better to push up 100m then go level or to go up 130m at easy incline and then 30m back down?
Yeah, true. I see, it needs more thinking about before starting this.
Johann Gail wrote:
Hello,
this is an idea which I think about some months, but have not had the time to do some programming. Maybe anyone else has the same thoughts, so I describe my idea here.
3. Is there an existing java library, which calculates me the height of each coordinate from an world model (maybe based on the SRTM data)?
There is a Google Summer Of Code 2009 project proposed for doing item 3 for OSM. Currently there is a shortage of Mentors, so if you want to see this implemented you might want to consider volunteering and mentor that student. Contact ian.dees@gmail.com for details on how to get started. (I've already volunteered, but to mentor for a different OSM project). Andy -- Andy PGP Key ID: 0xDC1B5864
Johann Gail wrote:
So my idea is, to virutally lengthen the roads by the height distance. This is, if a road has 1km and goes straight then it gets an entry of 1 km in the routing data.. If another road has a length of 1km and a height difference of 10m, then it gets a length entry of 1.1km.
Have you thought about changing the road_speed instead of the length? I.e. a road going up/downhill would get a lower road_speed than a flat one and when calculating a fastest route the Garmin should prefer the flat one.
I thought about that one too, but wouldn't that need a complete rewrite of the style system? You could solve it by reading in all streets, checking them for inclination, and then upon the inclination/height difference between every intersection provide a incline key, that you can then call upon in the style-file. I still wonder though about the amount of cpu power needed to get that data - knowing that my pc calculated about 12 hours (Pentium M 2.26GHz, by that time 2GB RAM, harddisk with 60MB/s average write, 65 read) on converting SRTM1" into Garmin contourlines with 10m seperation - for Austria only. Ralf Kleineisel wrote:
Johann Gail wrote:
So my idea is, to virutally lengthen the roads by the height distance. This is, if a road has 1km and goes straight then it gets an entry of 1 km in the routing data.. If another road has a length of 1km and a height difference of 10m, then it gets a length entry of 1.1km.
Have you thought about changing the road_speed instead of the length? I.e. a road going up/downhill would get a lower road_speed than a flat one and when calculating a fastest route the Garmin should prefer the flat one. _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Felix Hartmann wrote:
I thought about that one too, but wouldn't that need a complete rewrite of the style system?
You need a way of adding the inclination information to the roads anyway. Perhaps some sort of preprocessor for the OSM data? This could add a special inclination tag to every street and the style file could use this to fill in the corresponding road_speed later. I don't know if the map format allows road_speed information independently from the road type. i.e. if it is possible to have more than one "highway=tertiary 0x05" with different road_speeds.
I still wonder though about the amount of cpu power needed to get that data - knowing that my pc calculated about 12 hours (Pentium M 2.26GHz, by that time 2GB RAM, harddisk with 60MB/s average write, 65 read) on converting SRTM1" into Garmin contourlines with 10m seperation - for Austria only.
I expect it to be far less cpu intensive than calculating contour lines. Calculating contour lines is another algorithm. In my case I had simply to calculate the height for each node (which would be interpolating from SRTM Raster data) and calculate then the inclination or height difference on the street. On long streets, which crosses several raster squares, it would be needed to calculate the exact crossing points and calculate the height there. As the raster resolution is afaik ~100m, this would give not too much points. Also the temporarily generated data will be not too much, as it adds one value to each node and each way. This will be as a rule of thumb ~2MB per tile.
Have you thought about changing the road_speed instead of the length? I.e. a road going up/downhill would get a lower road_speed than a flat one and when calculating a fastest route the Garmin should prefer the flat one.
Yes, I have tought of it, but I expect it not to work for bycycle routing. I haven't do any tests with it, so my assumption could be wrong. But the road speed classes are defined for car routing 10kmh, 30kmh, 50kmh... 130 kmh which are obviously not proper for cycle routing. Maybe this classes are used with other speed values.
I just happened across this link which may be relevant. You are probably already aware of it, of course, but I don't think it's yet been mentioned in this thread: <URL: http://wiki.openstreetmap.org/wiki/Route_altitude_profiles_SRTM > It's not exactly the same thing, but there are probably some common elements...
participants (6)
-
Andrew Ayre -
Felix Hartmann -
Johann Gail -
Mark Burton -
Ralf Kleineisel -
Toby Speight