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

Thu Jan 12 21:52:18 GMT 2012

> 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?

>
>  >
>  > * LocationHook.mkgmapTagsArray starts with an empty string element. I
>  > don't like that.
>  >
>  > * 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?

WanMil

>
> Ciao,
> Gerd
>
>
> _______________________________________________
> mkgmap-dev mailing list
> mkgmap-dev at lists.mkgmap.org.uk
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev