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

Fri Jun 11 02:27:31 BST 2010

> > The reason for this was the costs of initializing were showing up in
> > the profile.
>
> Do you mean the cost of initializing the Element instances? If so then yes,
> that's something that I'd caught previously in profiling too, hence why
> they
> were being reused and reset (prior to r109 that is :).
>
>
No, the tag storage. Most nodes don't have tags.

> > josm already includes a quadtree implementation. I wish it could be
> > disentangled and re-used across the different OSM applications. It'd
> > be a perfect solution here.
>
> Not quite perfect I think... a quadtree doesn't allow overlapping
> rectangles
> whereas an r-tree does, which would allow us to deal with the overlap much
> more efficiently.
>
>
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.

> > Perfection isn't necessary.
> > How about a 64x64 array. Divide the world into 4096 regions. Each
> > region contains a list of all areas --- including their overlap ---
> > that intersect it. Then, for each node, you only need to iterate the
> > OSMWriters in that region. Getting the round-offs right would be
> > tricky, but it should be good enough filter out almost all
> > non-matching areas.
>
> Agreed, what you describe would still be a good improvement. This is
> basically
> how the DensityMap works already so that could probably/possibly be tweaked
> and reused.

That was exactly what I thought too.

> I still prefer the raw performance (and challenge!) of the r-tree
> approach but realistically it'll be some time before I get around to
> implementing
> that, so would be more than happy to go with the above in the meantime.
>
>
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. About a month ago, I lamented that josm's
quadtreeimplementation can be refactored it to support anything that
has a getBBox()
and isUsable() functions, but using it requires importing josm's notion of
bounding boxes and coordinates which brings in dependencies on
java.awt.geom.Rectangle2D, and org.openstreetmap.josm.Main (via LatLon).:

>  > Thanks for a useful program. Glad I could help make it better.
>
> Don't thank me, thank Steve for starting this project in the first place!
> I'm much like you, just got involved because I had an itch to scratch, and
> it looked like an interesting problem :)
>
>
Well Steve, thank you for the good program!

Scott
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20100610/3f23d3e6/attachment.html 