Routing

classic Classic list List threaded Threaded
17 messages Options
Reply | Threaded
Open this post in threaded view
|

Routing

Steve Ratcliffe
Hi

I've been looking into routing and I have updated NodDisplay
so that it mostly works on any file.
I've not discovered much that wasn't known before, apart from
a compact way of storing directions that is probably suitable
for short roads. There is a destination road-class field in
the node flags that we do not seem to set, so we should fix that.

I am in the process of updating the nod.txt file with everything I've
learned so far.

There are also two new programs.

1. test.check.NodCheck reads in a NOD file and cross checks
    various things. So it can tell you if the angle in NOD is similar
    to the actual angles between two nodes.  Files give lots of errors,
    but it doesn't mean that they are wrong, just things to look into.

2. test.svg.Main Converts the routing graph to an SVG file that
    can be displayed in inkscape (and perhaps other SVG viewers).
    The idea is to be able to visualise what is going on. Only a
    portion of the file is processed, since the output is very
    large.

They are only of use if you want to look into the routing code. The
output will make no sense at all if you are not familiar with it,
and possibly even if you are ;)

..Steve
_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: Routing

Gerd Petermann
Hi Steve,

the new NodDisplay tool reports a lot of errors for files
that were created with latest mkgmap .
I see lost sync messages as well as things like
" error INVALID node, low=0, tabpos=83f, max=30bf"

Similar problems with my Garmin img file.

Gerd

> Date: Tue, 14 Jan 2014 14:23:51 +0000

> From: [hidden email]
> To: [hidden email]
> Subject: [mkgmap-dev] Routing
>
> Hi
>
> I've been looking into routing and I have updated NodDisplay
> so that it mostly works on any file.
> I've not discovered much that wasn't known before, apart from
> a compact way of storing directions that is probably suitable
> for short roads. There is a destination road-class field in
> the node flags that we do not seem to set, so we should fix that.
>
> I am in the process of updating the nod.txt file with everything I've
> learned so far.
>
> There are also two new programs.
>
> 1. test.check.NodCheck reads in a NOD file and cross checks
> various things. So it can tell you if the angle in NOD is similar
> to the actual angles between two nodes. Files give lots of errors,
> but it doesn't mean that they are wrong, just things to look into.
>
> 2. test.svg.Main Converts the routing graph to an SVG file that
> can be displayed in inkscape (and perhaps other SVG viewers).
> The idea is to be able to visualise what is going on. Only a
> portion of the file is processed, since the output is very
> large.
>
> They are only of use if you want to look into the routing code. The
> output will make no sense at all if you are not familiar with it,
> and possibly even if you are ;)
>
> ..Steve
> _______________________________________________
> mkgmap-dev mailing list
> [hidden email]
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: Routing

Steve Ratcliffe

Hi Gerd,
> the new NodDisplay tool reports a lot of errors for files
> that were created with latest mkgmap .
> I see lost sync messages as well as things like
> " error INVALID node, low=0, tabpos=83f, max=30bf"

Thanks for reporting.

If you also see 'unknown alt6 0x4 flag' earlier in the same
node that is to be expected as I haven't looked at that
yet.
I am also not sure about arcs with 'curve' set, there may
still be problems with some of those.

I didn't think we used the 0x4 flag, so that could be
due to non working curve in the previous arc, but if we do then it
will be easy to fix.

I'll look at that next.  I must admit I have now found other files
where these issues are much more prevalent than the files I was
testing with!

..Steve
_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: Routing

Gerd Petermann
Hi Steve,

yes, I see 'unknown alt6 0x4 flag' a few lines before the
error message.

Gerd
 

> Date: Tue, 14 Jan 2014 15:38:11 +0000

> From: [hidden email]
> To: [hidden email]
> Subject: Re: [mkgmap-dev] Routing
>
>
> Hi Gerd,
> > the new NodDisplay tool reports a lot of errors for files
> > that were created with latest mkgmap .
> > I see lost sync messages as well as things like
> > " error INVALID node, low=0, tabpos=83f, max=30bf"
>
> Thanks for reporting.
>
> If you also see 'unknown alt6 0x4 flag' earlier in the same
> node that is to be expected as I haven't looked at that
> yet.
> I am also not sure about arcs with 'curve' set, there may
> still be problems with some of those.
>
> I didn't think we used the 0x4 flag, so that could be
> due to non working curve in the previous arc, but if we do then it
> will be easy to fix.
>
> I'll look at that next. I must admit I have now found other files
> where these issues are much more prevalent than the files I was
> testing with!
>
> ..Steve
> _______________________________________________
> mkgmap-dev mailing list
> [hidden email]
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: Routing

Steve Ratcliffe
On 14/01/14 15:48, Gerd Petermann wrote:
> yes, I see 'unknown alt6 0x4 flag' a few lines before the
> error message.

Ah, road-class can go from 0-4 and so does go into 3 bits like the
code previously had it. I had got convinced that there was just 4
different values...

So bit 0x04 is part of road class and there is no unknown bit apart
from 0x80.

The code is now fixed, and will work better on tiles that have lots
of motorways!

..Steve
_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: Routing

Steve Ratcliffe
In reply to this post by Gerd Petermann

Hi

I've made a few more fixes and I now don't get any
error where it mis-reads the file and gets out of sync.

So let me know if you find any now.

..Steve
_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: Routing

Gerd Petermann
Hi Steve,

yes, NodDisplay from r338 doesn't show any error messages for
img files created with mkgmap.
It still shows lots of them for my Garmin img file.
I think one of the reasons is this ugly zero byte that follows the
table C. As you mentioned in the commit, this is not correct and
I think my Garmin map contains data that is misinterpreted
when this zero byte is skipped.

Attached is a small excerpt of my output file containing the
header and the first lines of NOD1.

Gerd

> Date: Tue, 14 Jan 2014 21:17:09 +0000

> From: [hidden email]
> To: [hidden email]
> Subject: Re: [mkgmap-dev] Routing
>
>
> Hi
>
> I've made a few more fixes and I now don't get any
> error where it mis-reads the file and gets out of sync.
>
> So let me know if you find any now.
>
> ..Steve
> _______________________________________________
> mkgmap-dev mailing list
> [hidden email]
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

nod_part.zip (2K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Routing

Steve Ratcliffe
Hi Gerd

> Attached is a small excerpt of my output file containing the
> header and the first lines of NOD1.

That file seems to be in a completely different format, too many zeros
at the beginning. You would have to use NOD2 to get the node addresses
and then work out why there was a gap at the beginning or whatever else
is going on.
NodCheck kind of does this, but only after the table structure is
worked out so I don't think it would work as it is.  However if NOD2 is
OK there is no reason why you should not rely on it to get the table
addresses.

..Steve

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: Routing

Gerd Petermann
Hi Steve,

okay, thanks. I think that means that my file doesn't help much to learn
what format we should write. I am not even
sure if it is really routable, it's just my only one
that contains a NOD file.
It is called "GARMIN Worldwide Autoroute", and it probably
contains only major roads.

Gerd

> Date: Wed, 15 Jan 2014 09:38:45 +0000

> From: [hidden email]
> To: [hidden email]
> Subject: Re: [mkgmap-dev] Routing
>
> Hi Gerd
>
> > Attached is a small excerpt of my output file containing the
> > header and the first lines of NOD1.
>
> That file seems to be in a completely different format, too many zeros
> at the beginning. You would have to use NOD2 to get the node addresses
> and then work out why there was a gap at the beginning or whatever else
> is going on.
> NodCheck kind of does this, but only after the table structure is
> worked out so I don't think it would work as it is. However if NOD2 is
> OK there is no reason why you should not rely on it to get the table
> addresses.
>
> ..Steve
>
> _______________________________________________
> mkgmap-dev mailing list
> [hidden email]
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: Routing

Steve Ratcliffe
Hi Gerd

Ahh, I had a look at a basemap, and it has similar problems.

It seems there is only one node with no arcs in a section, verified
from NOD 2. So you are right that the skip on zero is incorrect for
this file, since the 'low' byte really should be zero. But there is
also another case where a zero is skipped. Removing both allows me to
read the first few sections. It breaks later on, so that first skip is
probably needed sometimes.

Anyway I'm more confident that it could be read now, but I don't have
time to look at it today.

..Steve
_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: Routing

Gerd Petermann
Hi Steve,

crossing my fingers!

Gerd
Steve Ratcliffe wrote
Hi Gerd

Ahh, I had a look at a basemap, and it has similar problems.

It seems there is only one node with no arcs in a section, verified
from NOD 2. So you are right that the skip on zero is incorrect for
this file, since the 'low' byte really should be zero. But there is
also another case where a zero is skipped. Removing both allows me to
read the first few sections. It breaks later on, so that first skip is
probably needed sometimes.

Anyway I'm more confident that it could be read now, but I don't have
time to look at it today.

..Steve
_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: Routing

popej
In reply to this post by Gerd Petermann
Hi Gerd,

 > I think that means that my file doesn't help much to learn
 > what format we should write. I am not even
 > sure if it is really routable, it's just my only one
 > that contains a NOD file.

There are many free samples of Garmin maps, that you can use for tests.
For example:
http://www.garmin-download.de/web/tuerkei/gmapsupp.img
http://www.garmin-download.de/transalpin/gmapsupp.zip
http://www.garmin-download.de/deutschland-v3/gmapsupp.zip
http://www.garmin-download.de/topo-2010/topo2010-test.zip

All these sample are routable and non-NT.

--
Best regards,
Andrzej


_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: Routing

Gerd Petermann
Hi Andrzej,

thanks for the hint, but aren't they all in NT-format or not routable?

Gerd

> Date: Wed, 15 Jan 2014 15:10:50 +0100

> From: [hidden email]
> To: [hidden email]
> Subject: Re: [mkgmap-dev] Routing
>
> Hi Gerd,
>
> > I think that means that my file doesn't help much to learn
> > what format we should write. I am not even
> > sure if it is really routable, it's just my only one
> > that contains a NOD file.
>
> There are many free samples of Garmin maps, that you can use for tests.
> For example:
> http://www.garmin-download.de/web/tuerkei/gmapsupp.img
> http://www.garmin-download.de/transalpin/gmapsupp.zip
> http://www.garmin-download.de/deutschland-v3/gmapsupp.zip
> http://www.garmin-download.de/topo-2010/topo2010-test.zip
>
> All these sample are routable and non-NT.
>
> --
> Best regards,
> Andrzej
>
>
> _______________________________________________
> mkgmap-dev mailing list
> [hidden email]
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: Routing

Gerd Petermann
ahh, did not see your remark in the last line. I'll try them.

Gerd

GerdP wrote
Hi Andrzej,

thanks for the hint, but aren't they all in NT-format or not routable?

Gerd

> Date: Wed, 15 Jan 2014 15:10:50 +0100
> From: [hidden email]
> To: [hidden email]
> Subject: Re: [mkgmap-dev] Routing
>
> Hi Gerd,
>
>  > I think that means that my file doesn't help much to learn
>  > what format we should write. I am not even
>  > sure if it is really routable, it's just my only one
>  > that contains a NOD file.
>
> There are many free samples of Garmin maps, that you can use for tests.
> For example:
> http://www.garmin-download.de/web/tuerkei/gmapsupp.img
> http://www.garmin-download.de/transalpin/gmapsupp.zip
> http://www.garmin-download.de/deutschland-v3/gmapsupp.zip
> http://www.garmin-download.de/topo-2010/topo2010-test.zip
>
> All these sample are routable and non-NT.
>
> --
> Best regards,
> Andrzej
>
>
> _______________________________________________
> mkgmap-dev mailing list
> [hidden email]
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
     
_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: Routing

Gerd Petermann
In reply to this post by Gerd Petermann
Hi Steve,

please note that nod.txt still claims that road class mask is 0x03.
I assume that you still work on it?

Gerd

> Date: Wed, 15 Jan 2014 04:55:19 -0800

> From: [hidden email]
> To: [hidden email]
> Subject: Re: [mkgmap-dev] Routing
>
> Hi Steve,
>
> crossing my fingers!
>
> Gerd
>
> Steve Ratcliffe wrote
> > Hi Gerd
> >
> > Ahh, I had a look at a basemap, and it has similar problems.
> >
> > It seems there is only one node with no arcs in a section, verified
> > from NOD 2. So you are right that the skip on zero is incorrect for
> > this file, since the 'low' byte really should be zero. But there is
> > also another case where a zero is skipped. Removing both allows me to
> > read the first few sections. It breaks later on, so that first skip is
> > probably needed sometimes.
> >
> > Anyway I'm more confident that it could be read now, but I don't have
> > time to look at it today.
> >
> > ..Steve
> > _______________________________________________
> > mkgmap-dev mailing list
>
> > mkgmap-dev@.org
>
> > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>
>
>
>
>
> --
> View this message in context: http://gis.19327.n5.nabble.com/Routing-tp5793031p5793213.html
> Sent from the Mkgmap Development mailing list archive at Nabble.com.
> _______________________________________________
> mkgmap-dev mailing list
> [hidden email]
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: Routing

Steve Ratcliffe
On 16/01/14 12:51, Gerd Petermann wrote:
> please note that nod.txt still claims that road class mask is 0x03.
> I assume that you still work on it?

Thanks. I've fixed it and added made a few other changes.

There is still a bit more to add.
_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: Routing

Gerd Petermann
Hi Steve,

thanks. I've corrected one small error with r341.

Gerd

> Date: Thu, 16 Jan 2014 19:50:24 +0000

> From: [hidden email]
> To: [hidden email]
> Subject: Re: [mkgmap-dev] Routing
>
> On 16/01/14 12:51, Gerd Petermann wrote:
> > please note that nod.txt still claims that road class mask is 0x03.
> > I assume that you still work on it?
>
> Thanks. I've fixed it and added made a few other changes.
>
> There is still a bit more to add.
> _______________________________________________
> mkgmap-dev mailing list
> [hidden email]
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev