[mkgmap-dev] (almost) duplicated node issue

Mon May 25 22:40:02 BST 2009

Wow... things get tough...

I've three things to say in a single mail:

First:
I think the encoding is just a 24 bits rounding of the coordinates. You should know at the first run all the nodes that collapses in the same IMG point. But I understand when you say that is complicated to find all the collapsed nodes in a million nodes map. Well, after encoding you should order the nodes per latitude and then order the nodes with the same latitude per longitude. Then all collapsed nodes are in a row. (quicksort is able to sort a vector "in place" without memory wasting: in C I remember I ordered a vector of 1 million elements in few seconds).

Second:
But maybe the problem is somewere else, or there is a simpler solution then forcing a collapse of nodes:

If the IMG specification accepts 2 (or more) independent nodes with the same coordinates (after encoding), maybe it is the routing info that should be encoded in some "smart" way (to be discovered...) that avoids routing engine hangs, infinite loops or errors.

Or it could be just a "simple" mkgmap bug: the routing info of the two close nodes does not relates correctly to the two nodes individually. It looks strange to me the fact that the problem in one point creates routing errors rather far in the map. Like a mis-alignemt of routing info vectors vs. node vectors.

Third:
I made this further experiment you can reproduce:
(1) compiled the osm file I've attached some mail ago: Routing error
(2) I moved one node of the 2 almost duplicated 10 meters away, compiled the osm file again: NO ROUTING ERROR

since the 2 compiled IMG do contain the same nodes, it should be easy for people who know IMG encoding and routing info encoding to discover the difference between the two IMG and understand what happened (a info vector shift, a missing info, a wrong info). Of course if you have a java debugger environment you can check variables before the IMG is even created (I think it's easier)

Hope this help.

Ciao, Marco.

--- Lun 25/5/09, gypakk at gmx.eu <gypakk at gmx.eu> ha scritto:

> Da: gypakk at gmx.eu <gypakk at gmx.eu>
> Oggetto: Re: [mkgmap-dev] (almost) duplicated node issue
> A: "Development list for mkgmap" <mkgmap-dev at lists.mkgmap.org.uk>
> Data: Lunedì 25 maggio 2009, 22:34
> Just a few thoughts...
> 
> 1. Why not giving a special mark to such nodes which have
> been generated by a clipping process? Maybe there is own tag
> for this? Then you would know that merging is not
> appropriate.
> 
> 2. And... please be careful when merging nodes which are
> parts of ways with different layers. These could represent
> separate floors of a public lift, e.g.
> 
> 3. Is there special a tag for marking those nodes which
> must not be merged although they have the same coordinates?
> This tag could be used to prevent automatic merging.
> 
> 
> 
> -------- Original-Nachricht --------
> > Datum: Mon, 25 May 2009 21:12:07 +0100
> > Von: Mark Burton <markb at ordern.com>
> > An: mkgmap-dev at lists.mkgmap.org.uk
> > Betreff: Re: [mkgmap-dev] (almost) duplicated node
> issue
> 
> > 
> > Hi Marco,
> > 
> > > I want to say: duplicated nodes and almost
> duplicated nodes are map
> > errors (expecially if they describe an highway). We do
> not know wich was the
> > right intention of the mapper (make routing
> possible/impossible).
> > > 
> > > I think that the best we can do when mkgmap finds
> 2 nodes that encode in
> > the same IMG point (so in both cases: duplicated nodes
> or
> > almost-duplicated nodes) is to collapse the 2 nodes in
> one node exacly as JOSM validator
> > would do if they were duplicated.
> > > 
> > > Does it sound good?
> > > 
> > > Just my proposal...
> > 
> > I should think that it would be reasonably easy to
> merge close nodes
> > using a first pass before any ways are processed.
> > 
> > However, tricky issues remain. Like, how do you cope
> with the situation
> > of a node being generated by the clipping process and
> that node is
> > within the critical distance of an existing node on
> the same way?
> > 
> > Cheers,
> > 
> > Mark
> > _______________________________________________
> > mkgmap-dev mailing list
> > mkgmap-dev at lists.mkgmap.org.uk
> > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> _______________________________________________
> mkgmap-dev mailing list
> mkgmap-dev at lists.mkgmap.org.uk
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> 