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

Thu Jan 19 10:27:21 GMT 2012

Hi WanMil,

> Date: Wed, 18 Jan 2012 22:43:46 +0100
> From: wmgcnfg at web.de
> To: mkgmap-dev at lists.mkgmap.org.uk
> Subject: Re: [mkgmap-dev] [Patch v5] LocationHook with new Quadtree
> 
> I have done a few checks and the results were all as expected.

Fine. I also accept all your changes.

> 
> Regarding the changes to the BoundaryPreparer:
> Do you plan to pimp the bnd File format?

I don't know yet and I think I'll need your help with that.
I see many options, with or without changing the bnd format.
My current favorite is to save each small boundary with the related tags, identified by 
the mkgmap:boundaryid tag plus the bbox of the quadtree node. A merge step should 
not be neccessary then, but I am afraid about the amount of data if we don't change the 
bnd format.

> Merging the polygons of the different bounds is quite easy. But how do 
> you plan to merge the tags? Do you plan to use a Tag object for each 
> admin_level or do you use special tag prefixes (e.g. 
> mkgmap:admin_level2:name) to mark the different boundary levels?
> 
> I would aggree to use more than one Tag object for each merged Boundary 
> (which also means that the bnd format must be changed slightly).

I think that using mkgmap:admin_level2:name for each would be too space consuming.
If we change the bnd format, one option would be to save the tagMask value first, 
followed by the corresponding tag values. The header of each bnd file would contain the content 
of mkgmapTagsArray so that one can interpret the data even if we change that array later.
If the amount of data is too big, we might create a list of all used location tag values 
(e.g. "Hamburg","Niedersachsen","81323",...) and then we can refer to the position in the 
list later. Up to now I don't think this is needed, but let's see.

Today I plan to write the method that travels through the quadtree, when this is done I'll know 
more. 

Gerd

> 
> WanMil
> 
> > Hi WanMil,
> >
> > I have no special reason for using the nano second timer. I tried it because
> > I noticed that the mili second timer is very inaccurate. I got the
> > impression that nano seconds are more precise, but of course the only usable
> > value is a mean value of long running tasks.
> >
> > ciao,
> > Gerd
> >
> >
> > WanMil wrote
> >>
> >> Hi Gerd,
> >>
> >> thanks for your further patch.
> >> I have a question about it: I see that you measure timings with nano
> >> second timer. I am quite sure that such accuracy is not given in such
> >> time measurements and often lead to wrong results. Do you really require
> >> that accuracy? In such a case I am sure that you can stop coding because
> >> there would be nothing more to improve so that the total runtime
> >> decreases. It would be just a matter of fortune.
> >>
> >> I think the only reasonable indicator is to measure the sum of the
> >> overall LocationHook timing for several tiles (>20). If that decreases
> >> significantly there is an improvement.
> >>
> >> WanMil
> >>
> >>
> >>
> >>> Hi WanMil,
> >>>
> >>> attached is the new version of the patch, now based on r2171.
> >>> I've invested a lot of time testing the result of LocationHook, I think
> >>> it
> >>> is always as good or better than trunk.
> >>> I will now try to add the quadtree to the preparer.
> >>>
> >>> Changes:
> >>> - build.xml with includeantruntime="false" to calm down ant
> >>> - added a few debugging aids and printout of complete runtime
> >>> - performance improvements in add() and merge() methods
> >>> - if a search in the nodes of the quadtree doesn't find the area,
> >>> additional
> >>> searches are performed for points
> >>>     in the neighbourhood
> >>> - for ways, the mid point is searched first. If the search returns null,
> >>> all
> >>> points are searched from the first one until a result is found. With my
> >>> test
> >>> data, quadtree never returned null, so this last loop is probably only
> >>> needed when boundary data is very incomplete.
> >>>
> >>> http://gis.638310.n2.nabble.com/file/n7199763/locationHook_speedup_v5.patch
> >>> locationHook_speedup_v5.patch
> >>>
> >>> ciao,
> >>> Gerd
> >>>
> >>> --
> >>> View this message in context:
> >>> http://gis.638310.n2.nabble.com/Patch-v5-LocationHook-with-new-Quadtree-tp7199763p7199763.html
> >>> Sent from the Mkgmap Development mailing list archive at Nabble.com.
> >>> _______________________________________________
> >>> 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-tp7199763p7201442.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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20120119/5ea25c2f/attachment.html 