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

Sat Jan 21 21:52:19 GMT 2012

> Date: Sat, 21 Jan 2012 22:31:53 +0100
> From: wmgcnfg at web.de
> To: mkgmap-dev at lists.mkgmap.org.uk
> Subject: Re: [mkgmap-dev] [Patch v5] LocationHook with new Quadtree
> 
> 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?

In one quadtree node I can have different parts of the same relation, each intersecting with 
different other boundaries and thus having different "location tags". Maybe it is not needed 
to be able to separate them in the program, but I found it easier to understand when looking 
at the BoundaryLister result.

> 
> 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.
Yes, each saved boundary will not intersect with others The information about the 
location tags is saved similar to the mkgmap:lies_in tag, I just use 
mkgmap:intersects_with for that so that. 

> 
> How did you solve the problem with merging the tags from different bounds?
I plan to save all boundaries with the original tags plus the added mkgmap:intersects_with 
tag. If a part of a boundary is saved somewhere in the tree, I save only the area part(s) that are 
in the tree. If a boundary overlaps the complete quadtree bbox, it will only appear in the  
mkgmap:intersects_with tag, thus I'll have to save it with the original area info created by 
the BoundarySaver.splitArea() method.

As I said, I still have to code some details, but I don't see any big problem now.

Gerd

> 
> 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
> 
> _______________________________________________
> 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/2c009724/attachment.html 