[mkgmap-dev] Bug in LocationHook?

Sat Jan 7 20:32:40 GMT 2012

> Hi,
>
>
> WanMil wrote
>>
>> that sounds strange. I think recreating the quadtree would only be
>> benficial if recreating takes less time than removing elements. I wonder
>> if that's the case?
>>
>
> I think the current quadtree implementation has one problem: As long as it
> still contains a few elements, a get(...) takes more or less the same time.
> I guess that's because it still calls a lot of intersect() calculations to
> return a result.
> I am still searching for an error which seems to slow down the program too
> much, but my patch does this:
> - It keeps the list elemList
> - If currLevel is changed, it checks if the previous level caused any
> changes to the elements in the quadTree. If not, the whole elemList is
> tested, all elements that are fully worked out are removed.
> If the remaining list is much smaller, the quadtree is replaced.

Sounds reasonable. There might be another solution within the quadtree:
At the moments subtrees are not reduced. At an early stage of 
implementation I did have implemented this but it did not have an 
advantage.
Now the quadtree uses other datastructures which might be easier to 
reduce. So a node which is not a leaf can be reduced after a successful 
remove operation if all childs are leafs and the sum of points in the 
leafs are lower than the maxsize. That should be not too complicted to 
implement and does not require any special handling in the LocationHook.

I will give it a try within the next days.

WanMil

>
> Ciao,
> Gerd
>
>
> --
> View this message in context: http://gis.638310.n2.nabble.com/Bug-in-LocationHook-tp7157897p7161772.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