[mkgmap-dev] Increasing the performance of whole-planet splits.

Fri Jun 11 10:17:03 BST 2010

Hello Scott,

> No, the tag storage. Most nodes don't have tags.

Ah ok fair enough. Still the same problem source, caused by the lack of object 
recycling.

> AFAICT, their quadtree lets you import objects that have a
> bounding-box, which gets stored at the deepest node wholly containing
> the bounding box. This would be enough.

So multiple objects are allowed on each node then I guess? Regardless, a 
density map or r-tree approach would be preferable anyway. A density map 
because you can jump straight to the set of candidate areas without a traversal, 
or r-tree because the tree's answer would be exact without any further tests 
required. The limitation I see with a density map approach is that parts 
of the planet that have the highest node density would by definition contain 
the smallest split areas. This means the density map would need to be high 
enough resolution that we didn't have to test against too many candidate 
split areas in these dense parts (especially since these would be the most 
common tests). To reduce the memory requirements, sets of candidate areas 
would probably need to be pooled and reused across multiple points on the 
density map.

I hope that makes sense, I'm finding it hard to my thoughts into words due 
to a lack of precise terminology!

> If you do, could I offer a suggestion? Define interfaces for every
> concept it uses, including coordinates and bounding boxes. That way it
> can be used in other OSM software.

Sure, though the implementation I had in mind is nowhere near a full featured 
one. No dynamic inserts/updates/deletes, no rebalancing etc which would greatly 
restrict its general purpose use. Not to say that couldn't be added later 
if someone wanted to put the effort in but I don't see myself doing it unless 
it turns out to be needed in the splitter.

> About a month ago, I lamented that
> josm's quadtreeimplementation can be refactored it tosupport anything
> that has a getBBox() and isUsable() functions, butusing it requires
> importing josm'snotion of bounding boxes and coordinates which brings
> in dependencies on java.awt.geom.Rectangle2D,
> andorg.openstreetmap.josm.Main (via LatLon).:

Definitely something to bear in mind. Shouldn't be a problem, I usually try 
to avoid such dependencies anyway.

Cheers,
Chris