[mkgmap-dev] Increasing the performance of whole-planet splits.From Scott Crosby scrosby06 at gmail.com on Fri Jun 11 17:56:38 BST 2010
On Fri, Jun 11, 2010 at 4:17 AM, Chris Miller <chris_overseas at hotmail.com>wrote: > 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). A 256x256 map would have 65536 cells about 120km on a side. Looking at the overview map of a max-nodes=1000000 split in qlandkarte, which shows tile boundaries,.I'd guess the worst case would be 10-15 tiles in a cell. That would prune away at least 97.5% of the bounds-checks. With the planet file, at this nodecount and cell size, an R-tree traversal would likely have more boundschecks than that. I could see an r-tree being a win if tilesizes got a lot smaller, say people started to run max-nodes=50000 splits, or spitted files with insane node densities, such as contour lines. 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 wouldn't worry too much about memory. Absolute worst case is each cell has all 255 areas, which would be 4 bytes * 255 areas IntList * (256*256 cells) =64mb. Use a ByteList and it's 16mb. Bitvector and it's 2mb. More realistically, I'd expect it to be 1/10th of the worst case. Scott -------------- next part -------------- An HTML attachment was scrubbed... URL: http://lists.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20100611/85660e27/attachment.html
- 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