> Date: Thu, 12 Jan 2012 22:52:18 +0100
> From: wmgcnfg@web.de
> To: mkgmap-dev@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 .