> Date: Mon, 16 Jan 2012 22:28:04 +0100
> From: wmgcnfg@web.de
> To: mkgmap-dev@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@lists.mkgmap.org.uk
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev