[mkgmap-dev] [Patch v1] improve splitter

Thu May 22 19:03:48 BST 2014

Hi all,

I've finally found a way to test a lot more possible solutions
in splitter in a reasonable time.
As a result, splitting a single country like Germany is now done 
with a full search, means, all posible splits are tested and the
best is chosen. 
For large files (e.g. Europe), the program can't search all
possible solutions, but it still finds better ones than r389.

This takes a bit more time than before, but
is likely to find really good solutions. If needed, I can implement 
new options to allow stopping the search if e.g. a solution is found
that has at least 85% of max-nodes in each tile.

A few numbers: 
Split Germany with max-nodes=1200000
r 389: Solution is nice. Can't find a better solution: 164 tile(s) and a rating of 2756. The smallest node count is 903153, the worst aspect ratio is near 3.99
patched: Solution is nice. Can't find a better solution: 150 tile(s). The smallest node count is 1081130 (90 %), the worst aspect ratio is near 3.83

Split Germany with max-nodes=1000000
r389: Solution is nice. Can't find a better solution: 192 tile(s) and a rating of 3014. The smallest node count is 742452, the worst aspect ratio is near 3.9
patched: Solution is nice. Can't find a better solution: 181 tile(s). The smallest node count is 894244 (89 %), the worst aspect ratio is near 3.93

Please try with your workload and let me know the results.
If you are not happy with the new result, please send the densities_out.txt and 
the splitter.log.

A compiled binary is available here:
http://files.mkgmap.org.uk/download/208/splitter.jar

Gerd

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20140522/ab9e8f69/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: deep-search-v1.patch
Type: application/octet-stream
Size: 24047 bytes
Desc: not available
URL: <http://www.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20140522/ab9e8f69/attachment-0001.obj>