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

Thu Jan 12 22:13:15 GMT 2012

> Date: Thu, 12 Jan 2012 22:52:18 +0100
> From: wmgcnfg at web.de
> To: mkgmap-dev at lists.mkgmap.org.uk
> Subject: Re: [mkgmap-dev] [Patch v3] LocationHook with new Quadtree
> 
> > Hi WanMil,
> >
> > thanks for the quick response.
> >
> >  > some ideas and questions:
> >  >
> >  > * BoundaryQuadTree.Node.add always performs a costly intersect of the
> >  > area, also if the area is completely within the bbox. Maybe it's better
> >  > first to check if the bbox contains the area (or area.getBounds()).
> > Good point. I'll try that.
> >
> >  >
> >  > * I don't understand the following part in Node.add:
> >  > ---
> >  > // optimization: don't add equal areas, only add the tags
> >  > // we test only against the last element because that is likely
> >  > // to match
> >  > if (numNodes > 0 && a.equals(nodes.get(numNodes-1))){
> >  > addMissingTags(nodes.get(numNodes-1).tags, bTags);
> >  > return;
> >  > }
> >  > ---
> >  > a is an area and nodes.get returns a NodeElem so equals will always be
> >  > false.
> >  > I think you want to compare to nodes.get(..).area but I do not
> >  > understand that either. Why should two areas be equal?
> >
> > argh! This error was introduced while I cleaned the code :-(
> > Of course I want to compare the areas. We add all boundaries to the
> > tree, even those with level=2.
> > Since the boundary list is sorted so that they appear last, it is very
> > likely that the area completely
> > covers the bbox of the tree. In this case the area will be the bbox.
> 
> Is that really a performance improvement?
> admin_level=2 boundaries are splitted anyhow during creation of the 
> tree. An area that is equal to a rectangle can perform a very easy and 
> quick contains test. So checking for equality probably will be more 
> costly than leaving it as it is?

Hmm, it was an improvement at some stage before I optimized other parts, now it seems 
to decrease performance quite a lot. 
Remove it for now.

> 
> >
> >  >
> >  > * LocationHook.mkgmapTagsArray starts with an empty string element. I
> >  > don't like that.

Yes, looks strange, but without it the level value would not match the position 
in the array. I'll add a comment for this, okay?

I also want to avoid calling getTag with an empty key, so I think we need
for (int i=1;i < ...)

> >  >
> >  > * for (int i = 12; i >= 1; --i){
> >  > if (elem.getTag(mkgmapTagsArray[i] ) != null)
> >  > res |= (1 << i);
> >  > }
> >  >
> >  > =>
> >  >
> >  > for (int i = 0; i mkgmapTagsArray.length; i++) {
> >  > if (elem.getTag(mkgmapTagsArray[i] ) != null)
> >  > res |= (1 << i);
> >  > }
> >  >
> >  > Counting down is quite unusual and should only be done if there is a
> >  > real reason for it.
> >
> > You are right, there is no longer a reason for it. I'll change that. I
> > used this loop together
> > with a bitmask and a call to Integer.highestOneBit()
> >
> >  >
> >  > * I don't understand why you need a merge() method. Could you explain
> >  > what you are doing in this method and why it's required?
> > The get method() of the tree returns the data for the first area that
> > contains the coord.
> > This area should contain all tags of the area itself plus those from
> > areas intersecting it.
> > Maybe this is not correct?
> 
> Sounds wrong. If Area a1 is intersected by a2 only in 10% of its area 
> then an element located in the 90% that does not intersect would be 
> tagged with a1 and a2?
> 
The merge() first creates a new nodeElem with the intersection, it merges the tags into this 
and subtracts the intersection from the others, so only the 10% part gets more tags. 
Thinking again about this I might not need both subtract() calls since I move the intersection part 
before the others .

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20120112/19d63c31/attachment.html 