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 .