> 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 quadtree
implementation 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