[mkgmap-dev] Splitter

Sun Jul 27 05:57:48 BST 2014

Hi Lambertus,

I can reproduce the problem. It seems that my approach 
to use an approximation procedure which changes the max-nodes
value doesn't work here. I saw similar problems with large values
for num-tiles, so I probably have to write a dedicated algo for this.

Gerd

Lambertus wrote
> Below is some output from Splitter. It knows it must return at least two 
> tiles but still settles with one.
> 
> Commandline:
> java -Xmx2048M -jar ~/garmin/utils/splitter/splitter.jar --output=o5m 
> --keep-complete=true --mapid=63241911 --num-tiles=2 
> --write-kml=63240007.kml --no-trim=true 63240007.o5m
> 
> The relevant Splitter output:
> Splitter version 412 compiled 2014-06-21T13:47:04+0100
> boundary-tags=use-exclude-list
> cache=
> description=
> geonames-file=/home/lambertus/garmin/utils/cities15000.zip
> keep-complete=true
> mapid=63241911
> max-areas=512
> max-nodes=1600000
> max-threads=4 (auto)
> mixed=false
> no-trim=true
> num-tiles=2
> output=o5m
> output-dir=
> overlap=auto
> polygon-desc-file=
> polygon-file=
> precomp-sea=
> problem-file=
> problem-report=
> resolution=13
> search-limit=200000
> split-file=
> status-freq=120
> stop-after=dist
> write-kml=63240007.kml
> Elapsed time: 0s   Memory: Current 120MB (3MB used, 117MB free) Max 1820MB
> Time started: Mon Jul 07 23:07:41 CEST 2014
> Map is being split for resolution 13:
>   - area boundaries are aligned to 0x800 map units (0.0439453125 degrees)
>   - areas are multiples of 0x800 map units wide and high
> Processing 63240007.o5m
> Bounding box -121.37695310000001 21.269531200000003 -117.4658203
> 33.9257812
> in 1 file
> Time: Mon Jul 07 23:07:42 CEST 2014
> Exact map coverage is (21.26953125,-121.376953125) to 
> (33.92578125,-117.4658203125)
> Rounded map coverage is (21.26953125,-121.376953125) to 
> (33.92578125,-117.4658203125)
> Splitting nodes into 2 areas
> Trying a max-nodes value of 557503 to split 1115006 nodes into 2 areas
> Best solution until now: 6 tile(s). The smallest node count is 52036 (9 
> %), the worst aspect ratio is near 3.94, elapsed search time: 0 s
> Best solution until now: 5 tile(s). The smallest node count is 71333 (12 
> %), the worst aspect ratio is near 3.83, elapsed search time: 0 s
> No good solution found, duplicated search-limit to 400000
> No good solution found, duplicated search-limit to 800000
> No good solution found, duplicated search-limit to 1600000
> No good solution found, duplicated search-limit to 3200000
> No good solution found, duplicated search-limit to 6400000
> Still no good solution found, trying alternate algorithm
> Trying to optimize parts of the best solution...
> Solution is not nice. Can't find a better solution with search-limit 
> 6400000: 5 tile(s). The smallest node count is 71333 (12 %), the worst 
> aspect ratio is near 3.83
> Final solution: 5 tile(s). The smallest node count is 71333 (12 %), the 
> worst aspect ratio is near 3.83
> Area 63241911 covers (27.9931640625,-120.673828125) to 
> (33.3984375,-117.4658203125) and contains 71333 nodes (12 %)
> Area 63241912 covers (33.3984375,-120.673828125) to 
> (33.92578125,-118.2568359375) and contains 147444 nodes (26 %)
> Area 63241913 covers (33.3984375,-118.2568359375) to 
> (33.92578125,-117.9931640625) and contains 175164 nodes (31 %)
> Area 63241914 covers (33.3984375,-117.9931640625) to 
> (33.7060546875,-117.4658203125) and contains 308932 nodes (55 %)
> Area 63241915 covers (33.7060546875,-117.9931640625) to 
> (33.92578125,-117.4658203125) and contains 412133 nodes (73 %)
> Trying a max-nodes value of 1393758 to split 1115006 nodes into 2 areas
> Highest node count in a single grid element is 83,854
> Solving partition (27.9931640625,-120.673828125) to 
> (33.92578125,-117.4658203125) with 1,115,006 nodes
> Trying to find nice split for (27.9931640625,-120.673828125) to 
> (33.92578125,-117.4658203125) with 1,115,006 nodes
> searching for split with min-nodes 69687, learned 0 good partial solutions
> Best solution until now: 1 tile(s). The smallest node count is 1115006 
> (79 %), the worst aspect ratio is near 2.09, elapsed search time: 0 s
> This can't be improved.
> Solution is nice. Can't find a better solution with search-limit 200000: 
> 1 tile(s). The smallest node count is 1115006 (79 %), the worst aspect 
> ratio is near 2.09
> Final solution: 1 tile(s). The smallest node count is 1115006 (79 %), 
> the worst aspect ratio is near 2.09
> This seems to be nice.
> Area 63241916 covers (27.9931640625,-120.673828125) to 
> (33.92578125,-117.4658203125) and contains 1115006 nodes (79 %)
> Trying a max-nodes value of 975630 to split 1115006 nodes into 2 areas
> Highest node count in a single grid element is 83,854
> Solving partition (27.9931640625,-120.673828125) to 
> (33.92578125,-117.4658203125) with 1,115,006 nodes
> Trying to find nice split for (27.9931640625,-120.673828125) to 
> (33.92578125,-117.4658203125) with 1,115,006 nodes
> searching for split with min-nodes 48781, learned 0 good partial solutions
> Best solution until now: 5 tile(s). The smallest node count is 52036 (5 
> %), the worst aspect ratio is near 3.94, elapsed search time: 0 s
> searching for split with min-nodes 325210, learned 0 good partial
> solutions
> searching for split with min-nodes 188623, learned 0 good partial
> solutions
> searching for split with min-nodes 120329, learned 0 good partial
> solutions
> searching for split with min-nodes 86182, learned 0 good partial solutions
> searching for split with min-nodes 69109, learned 0 good partial solutions
> Best solution until now: 4 tile(s). The smallest node count is 71333 (7 
> %), the worst aspect ratio is near 3.83, elapsed search time: 0 s
> searching for split with min-nodes 325210, learned 0 good partial
> solutions
> searching for split with min-nodes 198271, learned 0 good partial
> solutions
> searching for split with min-nodes 134802, learned 0 good partial
> solutions
> searching for split with min-nodes 103067, learned 0 good partial
> solutions
> searching for split with min-nodes 87200, learned 0 good partial solutions
> searching for split with min-nodes 79266, learned 0 good partial solutions
> searching for split with min-nodes 75299, learned 0 good partial solutions
> searching for split with min-nodes 73316, learned 0 good partial solutions
> searching for split with min-nodes 72324, learned 0 good partial solutions
> searching for split with min-nodes 71828, learned 0 good partial solutions
> searching for split with min-nodes 71580, learned 0 good partial solutions
> searching for split with min-nodes 71456, learned 0 good partial solutions
> searching for split with min-nodes 71334, learned 0 good partial solutions
> No good solution found, duplicated search-limit to 400000
> searching for split with min-nodes 71334, learned 0 good partial solutions
> No good solution found, duplicated search-limit to 800000
> searching for split with min-nodes 71334, learned 0 good partial solutions
> No good solution found, duplicated search-limit to 1600000
> searching for split with min-nodes 71334, learned 0 good partial solutions
> No good solution found, duplicated search-limit to 3200000
> searching for split with min-nodes 71334, learned 0 good partial solutions
> No good solution found, duplicated search-limit to 6400000
> searching for split with min-nodes 71334, learned 0 good partial solutions
> Still no good solution found, trying alternate algorithm
> searching for split with min-nodes 71334, learned 0 good partial solutions
> Trying to optimize parts of the best solution...
> searching for split with min-nodes 71334, learned 0 good partial solutions
> Solution is not nice. Can't find a better solution with search-limit 
> 6400000: 4 tile(s). The smallest node count is 71333 (7 %), the worst 
> aspect ratio is near 3.83
> Final solution: 4 tile(s). The smallest node count is 71333 (7 %), the 
> worst aspect ratio is near 3.83
> Area 63241917 covers (27.9931640625,-120.673828125) to 
> (33.3984375,-117.4658203125) and contains 71333 nodes (7 %)
> Area 63241918 covers (33.3984375,-120.673828125) to 
> (33.92578125,-118.2568359375) and contains 147444 nodes (15 %)
> Area 63241919 covers (33.3984375,-118.2568359375) to 
> (33.92578125,-117.9931640625) and contains 175164 nodes (17 %)
> Area 63241920 covers (33.3984375,-117.9931640625) to 
> (33.92578125,-117.4658203125) and contains 721065 nodes (73 %)
> Trying a max-nodes value of 1184694 to split 1115006 nodes into 2 areas
> Highest node count in a single grid element is 83,854
> Solving partition (27.9931640625,-120.673828125) to 
> (33.92578125,-117.4658203125) with 1,115,006 nodes
> Trying to find nice split for (27.9931640625,-120.673828125) to 
> (33.92578125,-117.4658203125) with 1,115,006 nodes
> searching for split with min-nodes 59234, learned 0 good partial solutions
> Best solution until now: 1 tile(s). The smallest node count is 1115006 
> (94 %), the worst aspect ratio is near 2.09, elapsed search time: 0 s
> This can't be improved.
> Solution is very nice. No need to search for a better solution: 1 
> tile(s). The smallest node count is 1115006 (94 %), the worst aspect 
> ratio is near 2.09
> Final solution: 1 tile(s). The smallest node count is 1115006 (94 %), 
> the worst aspect ratio is near 2.09
> This seems to be nice.
> Area 63241921 covers (27.9931640625,-120.673828125) to 
> (33.92578125,-117.4658203125) and contains 1115006 nodes (94 %)
> Creating the initial areas took 706 ms
> Writing KML file to ./63240007.kml
> 1 areas:
> Area 63241911: 1304576,-5623808 to 1581056,-5474304 covers 
> (0x13e800,0xffaa3000) to (0x182000,0xffac7800) US-Long Beach
> Generating problem list for 1 distinct areas
> Processing 1 areas in a single pass
> Pseudo-Writers:
> Pseudo area -2 covers (33.92578125,-180.0) to (90.0,180.0)
> Pseudo area -3 covers (-90.0,-180.0) to (27.9931640625,180.0)
> Pseudo area -4 covers (27.9931640625,-180.0) to
> (33.92578125,-120.673828125)
> Pseudo area -5 covers (27.9931640625,-117.4658203125) to
> (33.92578125,180.0)
> cached 6 combinations of areas that form rectangles.
> WriterGridTree [512][512] for grid area (-90.0,-180.0) to (90.0,180.0) 
> requires max. 3 checks for each node (0 sub grid(s))
> Grid(s) created in 156 ms
> Starting problem-list-generator pass(es) for partition 1
> 
> 
> On 07/03/2014 08:41 PM, Lambertus wrote:
>> There is a ~20MB o5m file that needs to be split. But Splitter returns:
>>
>> "Cannot find a good split with exactly 2 areas"
>>
>> I hope a (the) dev can have a look at this? Thanks!
>>
>> The tile is here: 
>> http://osm.pleiades.uni-wuppertal.de/garmin/20140703/63240007.o5m
>>
>> See for more info and a link to the o5m file:
>> http://forum.openstreetmap.org/viewtopic.php?pid=434024#p434024
>> _______________________________________________
>> mkgmap-dev mailing list
>> 

> mkgmap-dev at .org

>> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
> 
> 
> _______________________________________________
> mkgmap-dev mailing list

> mkgmap-dev at .org

> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

--
View this message in context: http://gis.19327.n5.nabble.com/Splitter-tp5810219p5812802.html
Sent from the Mkgmap Development mailing list archive at Nabble.com.