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

Mon Jan 16 21:54:13 GMT 2012

Hi WanMil,

> Date: Mon, 16 Jan 2012 22:28:04 +0100
> From: wmgcnfg at web.de
> To: mkgmap-dev at lists.mkgmap.org.uk
> Subject: Re: [mkgmap-dev] [Patch v3] LocationHook with new Quadtree
> 
> 
> >  >
> >  > > 2) Calculate it in BoundaryPreparer and save it in the .bnd files (with
> >  > > a new or extended format). In this case we can avoid higher calculation
> >  > > time if that means reducing redundancy.
> >  > > With precompiled quadtrees the LocationHook just has to create a small
> >  > > master-quadtree and load required parts into it.
> >  > >
> >  > > The quadtree in my patch probably contains a lot of redundant
> >  > > information because tiles with admin-level=2 or =4 will cover big parts
> >  > > of the tree, and the information is (almost always) already
> >  > > contained in the smaller areas because I use the information from the
> >  > > lies_in tags.
> >  >
> >  > Mmh, I though the merge step will create non overlapping areas and each
> >  > area contains *all* of its information. So there should be no large
> >  > admin_level=2 area left but lots small areas all containing the
> >  > admin_level=2,3,4,5,6,7,8,9,10,11 information.
> >
> > The current implementation uses the infos of the lies_in tag and stops
> > merging
> > when larger areas are not adding information. So, the larger areas are kept
> > untouched (and typically unused). They are just eating up some kb heap
> > memory.
> 
> Ok, I haven't gone into deep in the merge() method. But I think you are 
> going the right way!

Ok, fine.

> 
> >
> >  >
> >  > >I did not try it, but I expect that the merge() process
> >  > > result should be the same if we don't use
> >  > > the lies_in information.
> >  >
> >  > If not something is wrong?!
> >
> > I think so, and yes, the results are very different. So, I first have to
> > analyse why this
> > doesn't work as expected.
> >
> >  >
> >  > > If we move the quadtree to the preparer, we can omit the calculation of
> >  > > the lies_in tags (I think they are not needed elsewhere), but we should
> >  > > try to avoid saving redundant information.
> >  >
> >  > The lies_in information is only 80% of the information required for the
> >  > new quadtree. So it might help but is not sufficient to remove the merge
> >  > step.
> > Hmm, I don't fully understand what you mean. I thought about this:
> > My idea is to replace the algorithm in
> > BoundaryPreparer.workoutBoundaryRelations() by a
> > call of BoundaryQuadTree and to save the quadtree.
> 
> Maybe we want the same but we are talking in a different way about that. 
> Let me try in other words:
> 
> The preparer creates *non overlapping* areas containing all boundary 
> information. So each point lies only in one (or none) precompiled area 
> (ignoring the fact that there is a problem when a point lies exactly on 
> the edge of an area). The area can be used to tag the point (which also 
> mean a way using one point) with all available boundary information.
> 
> In the end this would be the same result as your intended merge step (if 
> we ignore the quadtree structure). This precompiled information is 
> stored to the bnd files and loaded by mkgmaps LocationHook. The 
> LocationHook creates the BoundaryQuadTree from this information and 
> because of the precompilation no more merge step is required.
> 
> Do you aggree?

Yes, that sounds good to me. If preparer makes sure that no areas do overlap, 
than we can omit the merge step. 

Ciao,
Gerd

> 
> >
> >  >
> >  > >
> >  > > If we can save the quadtree in a format that can be loaded faster than
> >  > > the time that is now needed to load the .bnd files plus calculating the
> >  > > quadtree, I'd vote for optimizing it for the preparer.
> >  >
> >  > The preparer would have to do the merge step:
> >  > From the given boundaries create not overlapping areas with all
> >  > location information.
> >  > I would not try to store additional quadtree information. You can try
> >  > but I don't expect any measurable improvements by that.
> > Okay, that sound's like a good alternative with the advantage that we
> > can keep
> > the format of the bnd files.
> >
> >  >
> >  > All in all: Please keep the format of the bnd files as simple as
> >  > possible and think about using it for other purposes. e.g. the current
> >  > format could easily be used for coastline processing - one can
> >  > precompile the coastlines and mgkmap could load the sea areas from the
> >  > precompiled sea file. This would be great to have (a big!! performance
> >  > and quality improvement). But someone needs to implement that.
> > I did not look at coastline processing until now, but if that requires
> > optimization
> > than I will do after fixing the remaining problems.
> >
> 
> Yes, it's not a very big deal when you know the system of the 
> precompiled bounds. But it would be a great improvement (also for people 
> with fewer GBs of memory).
> 
> WanMil
> _______________________________________________
> 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/20120116/559bbc71/attachment.html 