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

Sat Jan 21 21:31:53 GMT 2012

Ok, that makes sense.
What do you mean with "final _2 means that the bbox of this quadtree 
node contains another part of r12345."? Why do you need that info?

I expect your nodes are completely merged in the bounds file? Do you 
still keep all boundaryids for reference? This was *very* useful for 
debugging purposes.

How did you solve the problem with merging the tags from different bounds?

WanMil

> 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
>
>
> _______________________________________________
> mkgmap-dev mailing list
> mkgmap-dev at lists.mkgmap.org.uk
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev