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

Mon Jan 16 21:28:04 GMT 2012

>  >
>  > > 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!

>
>  >
>  > >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?

>
>  >
>  > >
>  > > 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