[mkgmap-dev] [Patch v5] LocationHook with new Quadtree

Sat Jan 21 21:14:10 GMT 2012

Hi WanMil,

oh, yes, I forgot to mention that I'll create one quadtree for each distinct raster tile. The load routine knows the exact bbox, so it just has to alloc the right child and fill the node. For LocationHook, one additional simple data structure is needed (e.g. a grid or master-quadtree) to identify the quadtree that has to be searched. 

Ciao,
Gerd

> Date: Sat, 21 Jan 2012 22:00:58 +0100
> From: wmgcnfg at web.de
> To: mkgmap-dev at lists.mkgmap.org.uk
> Subject: Re: [mkgmap-dev] [Patch v5] LocationHook with new Quadtree
> 
> Hi Gerd,
> 
> sounds good although I don't understand how that should work. I think I 
> am missing one part of the idea.
> 
> My problem is that the bounds are prepared with a distinct raster 
> (50000) but the quadtree is created with the bbox of the tile. So how do 
> you know during preparation that an area will be located in child[0] 
> (which is for example the northeast part of the bbox)?
> 
> Example:
> Bounds 1 with bbox (0/0,100/100) and the path 0 (north east)
> Tile bbox 1 (0/0,1000/1000) => path 0 is ok
> Tile bbox 2 (-900/-900, 100/100) => path 0 is nok - I would expect path 
> 3 (south west)
> 
> What am I missing?
> 
> WanMil
> 
> > Hi WanMil,
> >
> > I think I have found a good solution which still fits into the current bnd
> > format. It allows to rebuild the quadree without any merge() or split(), the
> > file size is not much bigger, and preparer creates the new content much
> > quicker than trunk. The trick is to save the "path" in the quadtree for each
> > saved boundary. So, I'll save e.g. a boundary with tag
> > mkgmap:boundaryid=r12345_032_2 , and that means the area is a part of
> > relation r12345, and it has to be saved in child[0]->child[3]->child[2], the
> > final _2 means that the bbox of this quadtree node contains another part of
> > r12345.
> > Most of the coding is done, I just have to decide where to put the methods.
> >
> > ciao,
> > Gerd
> >
> >
> >
> > WanMil wrote
> >>
> >> Hi Gerd,
> >>
> >> in an abstract way that's also a dictionary. Like I wrote I would first
> >> continue to implement the functionality and improve it afterwards if
> >> required. Keep it simple :-)
> >>
> >> WanMil
> >>
> >>> Hi WanMil,
> >>>
> >>> OK, so I try to keep all available info available.
> >>> I thought about saving the original boundary information with an empty
> >>> area section,
> >>> and for the boundaries that were merged in quadtree add a tag similar to
> >>> lies_in, e.g.
> >>> intersects_with=2:r19884;4:r20039;6:r998818
> >>> Will try that tomorrow...
> >>>
> >>> ciao,
> >>> Gerd
> >>>
> >>>
> >>>
> >>>   >  Date: Thu, 19 Jan 2012 21:51:20 +0100
> >>>   >  From: wmgcnfg@
> >>>   >  To: mkgmap-dev at .org
> >>>   >  Subject: Re: [mkgmap-dev] [Patch v5] LocationHook with new Quadtree
> >>>   >
> >>>   >  >  Hi WanMil,
> >>>   >  >
> >>>   >  >  I have coded a first version of the preparer with quadtree. It works
> >>> so
> >>>   >  >  far, the bnd files are not
> >>>   >  >  much bigger and the format is still the old one (boundaryLister can
> >>> read
> >>>   >  >  them), the creation is a
> >>>   >  >  little bit faster compared to trunk.
> >>>   >
> >>>   >  Great!
> >>>   >
> >>>   >  >
> >>>   >  >  I think I understand now your question regarding the merging the
> >>> tags.
> >>>   >  >  In the trunk implementation we save all kinds of tags for the
> >>> boundary,
> >>>   >  >  although only a few are
> >>>   >  >  needed by LocationHook. Now, when BoundaryQuadTree.Node.merge() has
> >>>   >  >  executed, I have
> >>>   >  >  some areas that are intersections of two or more boundaries. It is
> >>> clear
> >>>   >  >  that we have to save the
> >>>   >  >  location relevant tags, but what about the other? Can we simply
> >>> ignore
> >>>   >  >  them? I guess no, because
> >>>   >  >  we loose information like name:en, name:fr if they exist.
> >>>   >
> >>>   >  Yes, that's a problem. The name that is used for the boundaries is
> >>> taken
> >>>   >  from the name-tag-list option. I think this should not be dropped -
> >>>   >  otherwise we loose the option to create a map with french or spanish
> >>>   >  country and boundary names. But the tags used in the name-tag-list
> >>>   >  option are not limited to "name:*" tags. So we cannot create a rule
> >>>   >  which tags could be dropped during preparation.
> >>>   >
> >>>   >  It would be possible to create a dictionary with tag names at the
> >>>   >  beginning of each bnd file. But I think it's better to implement the
> >>>   >  whole functionality first with the current bnd file format. Once that
> >>> is
> >>>   >  done we might check if it improves the performance to optimize the bnd
> >>>   >  format. But I doubt that it makes a big difference because most of the
> >>>   >  bnd files are not very big. 99% of the bnd files of the world are
> >>>   >  smaller than 1 MB.
> >>>   >
> >>>   >  WanMil
> >>>   >
> >>>   >  >
> >>>   >  >  Any ideas?
> >>>   >  >
> >>>   >  >  Ciao,
> >>>   >  >  Gerd
> >>>   >  >
> >>>   >  >
> >>>   >  _______________________________________________
> >>>   >  mkgmap-dev mailing list
> >>>   >  mkgmap-dev at .org
> >>>   >  http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> >>>
> >>>
> >>> _______________________________________________
> >>> mkgmap-dev mailing list
> >>> mkgmap-dev at .org
> >>> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> >>
> >> _______________________________________________
> >> mkgmap-dev mailing list
> >> mkgmap-dev at .org
> >> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> >>
> >
> >
> > --
> > View this message in context: http://gis.638310.n2.nabble.com/Patch-v5-LocationHook-with-new-Quadtree-tp7199763p7211809.html
> > Sent from the Mkgmap Development mailing list archive at Nabble.com.
> > _______________________________________________
> > 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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20120121/be676c5f/attachment.html 