[mkgmap-dev] Increasing the performance of whole-planet splits.From Chris Miller chris_overseas at hotmail.com on 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
- Previous message: [mkgmap-dev] Increasing the performance of whole-planet splits.
- Next message: [mkgmap-dev] Increasing the performance of whole-planet splits.
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
More information about the mkgmap-dev mailing list