Hi Gerd, I'm trying to get similar map with mkgmap and cgpsmapper, which isn't easy, since processing is different. I have compiled some examples of maps for fenix and tested them in a watch. I haven't noticed differences between both versions. In both cases redraw took about 5-6 seconds. Now I'm trying to prepare a process to recompile img created with mkgmap. This is a bit complicated, since GPSMapEdit decompile each layer separately. I'm going to use only layer 0 and restore other levels basing on style definition. It will take some time till I will be able to post examples. -- Best regards, Andrzej

Hi Andrzej, thanks for the infos and the data. When you see the 50 % faster operations whith the 29483018.img, is that in a rather low populated area ? Gerd

Date: Wed, 12 Nov 2014 23:19:13 +0100 From: popej@poczta.onet.pl To: mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] Optimizing MapSplitter

Hi Gerd,

I have prepared a tile in a way you have suggested. See files here: http://files.mkgmap.org.uk/download/224/test.7z

Archive include following maps: 29483019.img - map compiled by mkgmap with mkgm-test.bat 29483018.img - map recompiled by cGPSmapper with TreSize=511 29483017.img - map recompiled by cGPSmapper with default TreSize

I have included OSM data and mp source too. You can create img for device using included mk_device.bat.

My observations are following:

All maps are work quite good in device, it is not easy to tell which is the fastest.

I can measure differences in redraw time between both version of cgpsmapper maps, the one with TreSize=511 can be up to 50% faster in some operations (measured in nuvi 1440).

Map compiled with mkgmap is fast, as good as faster version of cgpsmapper.

Since mkgmap creates fast maps, I'm not sure now, if subdivision size is so important. Maybe not, or maybe there is still some room for improvement in mkgmap?

-- Best regards, Andrzej _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Hi, I think I'll try to change this: 1) Put large objects (large bbox, maybe only few points as with 0x4b background polygon) into there own sub divs and don't add small objects to those sub divs 2) Create smaller sub divisions in dense areas I don't know yet how to do that, so I'll sleep about about again ;-) Gerd

Date: Thu, 13 Nov 2014 13:20:42 +0100 From: popej@poczta.onet.pl To: mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] Optimizing MapSplitter

Hi Gerd,

I test maps at my current location, which is near the center of Gdańsk, so it is rather dense map here. This 50% difference was in redraw time from nuvi menu "Dispaly Map" to fully rendered map. It was about 4 seconds for mkgmap and faster cgpsmapper and about 6 seconds for slower version of cgpsmapper compilation.

Some more statistics: 29483017.img level 4: resolution 17, subdivisions 1 level 3: resolution 18, subdivisions 7 level 2: resolution 20, subdivisions 24 level 1: resolution 22, subdivisions 173 level 0: resolution 24, subdivisions 423

29483018.img level 4: resolution 17, subdivisions 1 level 3: resolution 18, subdivisions 7 level 2: resolution 20, subdivisions 36 level 1: resolution 22, subdivisions 429 level 0: resolution 24, subdivisions 3979

29483019.img level 4: resolution 17, subdivisions 1 level 3: resolution 18, subdivisions 4 level 2: resolution 20, subdivisions 35 level 1: resolution 22, subdivisions 221 level 0: resolution 24, subdivisions 367

-- Best regards, Andrzej _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Hi Steve, hi Andrzej, please check attached patch. It doesn't implement any big change, it just avoids to create sub divisions which are larger than needed and doesn't write empty sub divs. What do you think? Gerd

Date: Fri, 14 Nov 2014 12:05:08 +0000 From: steve@parabola.me.uk To: mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] Optimizing MapSplitter

Hi

...

I think I'll try to change this: 1) Put large objects (large bbox, maybe only few points as with 0x4b background polygon) into there own sub divs and don't add small objects to those sub divs 2) Create smaller sub divisions in dense areas

I've been thinking of this way 1. Start with everything in its own subdivision. 2. For each subdivision: Find other subdivisions that completely contain it. ...but ignore subdivisions that are "too big". Combine the subdivision into the smallest of those found that still have room. 3. Repeat "enough" times.

- "too big": a desktop zoomed to just the level covers less than 1000000 square units. My etrex 30 covers about 40000 square units if I measured it correctly. So I would guess that divs can be freely combined up to those kinds of sizes.

But for larger containing divs, you would probably want to make sure that all elements are at least 50% of the size of the division.

- "enough": I've no idea what that would mean or even if this would work at all!

...

I don't know yet how to do that, so I'll sleep about about again ;-)

Yes that is the problem!

..Steve _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Hi Andrzej, the 1st patch removed too much, attached is a 2nd version. It also contains a few rows to create smaller sub divisions for dense areas. You may experiment with the value in wantedSize. It is an estimate for the number of bytes in one sub div. Gerd mapsplit-mini-v2.patch <http://gis.19327.n5.nabble.com/file/n5824396/mapsplit-mini-v2.patch> popej wrote

Hi Gerd,

I have compiled the same map with your patch, file is here: http://files.mkgmap.org.uk/download/225/29483020.7z

Map is a bit smaller and really has less subdivisions, see comparison: fist compilation 29483019.img level 4: resolution 17, subdivisions 1 level 3: resolution 18, subdivisions 4 level 2: resolution 20, subdivisions 35 level 1: resolution 22, subdivisions 221 level 0: resolution 24, subdivisions 367

patched 29483020.img level 4: resolution 17, subdivisions 1 level 3: resolution 18, subdivisions 4 level 2: resolution 20, subdivisions 33 level 1: resolution 22, subdivisions 202 level 0: resolution 24, subdivisions 340

I can measure a small increase in zoom speed in my nuvi, like 5-10%, but this could be measurement error.

-- Best regards, Andrzej _______________________________________________ mkgmap-dev mailing list

mkgmap-dev@.org

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

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

Hi Andrzej, yes, I did not test with your data yesterday and did not notice an old problem with high precision coordinates. Attached is a new patch that implements both changes which I suggested here: http://gis.19327.n5.nabble.com/Optimizing-MapSplitter-tp5823702p5824224.html I am not sure about the criteria. The line final int LARGE_OBJECT_DIM = 1024; gives a measurement for large objects in map units. Each large object is placed in its own sub div. The line int wantedSize = MAX_RGN_SIZE / 10; // smaller values result in more sub divs determines the approx. number of bytes in one sub div. A value near 0 means many very small sub divs, a value near MAX_RGN_SIZE is what the trunk version uses. Maybe we have to create parameters for them. Gerd

Date: Fri, 14 Nov 2014 22:54:38 +0100 From: popej@poczta.onet.pl To: mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] Optimizing MapSplitter

Hi Gerd,

your second patch doesn't work for me. When compiling I get multiple warnings like this: SEVERE (MapArea): 29483021.osm.pbf: Point with type 0x2d02 at http://www.openstreetmap.org/?mlat=54.594173&mlon=18.815332&zoom=17 is outside of the map area centred on http://www.openstreetmap.org/?mlat=54.509804&mlon=18.684912&zoom=17 width = 12155 height = 8502 resolution = 15

Img is much bigger, like 5MB instead of 3.8MB and I can't decompile it with GPSMapEdit. BaseCamp doesn't display it. I assume img is damaged.

-- Best regards, Andrzej

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

Hi Andrzej, thanks for testing. I also think that the possible improvements are rather small. I'll try a few more changes, e.g. splitting large objects earlier, but I don't expect any big improvements. A typical case where it would help is a long diagonal line. The bbox for it is very big, and a split in the middle would produce two much smaller bboxes. Splitting an rectangle like that for the background earlier will probably not help at all. Gerd popej wrote

Hi Gerd,

patch v3 is working. I have done some speed test on nuvi but conclusions aren't clear. My feeling is that your original settings is a bit slower than standard mkgmap. I have tried some values and settled to:

LARGE_OBJECT_DIM = 8192; int wantedSize = MAX_RGN_SIZE / 4;

This seems to be a bit faster than standard mkgmap, maybe about 10%, sometimes more. But redraw times aren't always repeatable and my tests are limited to single nuvi model. I would rather say, that there is no significant improvements.

-- Best regards, Andrzej _______________________________________________ mkgmap-dev mailing list

mkgmap-dev@.org

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

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

Hi Gerd I tried out the v3 of the patch. It looks good, just looking at the pattern in inkscape. There is a shift towards smaller divs, though the average is still quite large (in area).

I don't think that the current algo is completely wrong. I think it is better to start with the complete data and divide it into smaller parts as that algo keeps the information of the location of elements, while your approach is likely to compare many bboxes which are (too) far away from each other.

Yes, implementation speed might require some more complexity - but it seems that it should produce a division split where all of them are no bigger than required without further splitting the elements. If that is the case, and it still makes no difference in speed, then maybe we are pretty much as good as we are going to get. ..Steve

On 12/11/14 22:19, Andrzej Popowski wrote:

I have prepared a tile in a way you have suggested. See files here: http://files.mkgmap.org.uk/download/224/test.7z

Archive include following maps: 29483019.img - map compiled by mkgmap with mkgm-test.bat 29483018.img - map recompiled by cGPSmapper with TreSize=511 29483017.img - map recompiled by cGPSmapper with default TreSize

As part of the div display program I keep track of the sizes of the subdivisions and count them in buckets of their log10() value. 29483017.img cgpsmapper default tre size ------------ Total elements: 142725 Number of divs: 423 Average elements per div 337 0: 0 1: 0 2: 0 3: 0 4: 1 5: 50 6: 121 7: 250 8: 0 9: 1 This means that there is 1 division that is between 10,000 and 99,999 units square, 50 that are between 100,000 and 999,999 units square etc. So there is a high number of elements per division and most divisions are greater than 1,000,000 units square. Indeed more than half are greater than 10,000,000 units square. 29483018.img cgpsmapper tre size 511 ------------- Total elements: 161337 Number of divs: 3979 Average elements per div 40 0: 0 1: 1 2: 7 3: 12 4: 177 5: 3625 6: 154 7: 0 8: 0 9: 1 There are a lot more divisions and most of them are less than 1,000,000 units square. 29483019.img mkgmap ------------ Total elements: 142579 Number of divs: 367 Average elements per div 388 0: 0 1: 0 2: 0 3: 0 4: 0 5: 63 6: 215 7: 76 8: 13 9: 0 The mkgmap map has a low number of subdivisions and more than half are less than 10,000,000 units square. It therefore falls somewhat between the two cgpsmapper maps. It would be interesting if an even smaller tresize produced a faster map. ..Steve

Hi Steve, great. I did some experiments with different values for MAX_DIVISION_SIZE and found no change in the redraw time in my Oregon 450t. (no stopwatch, just the "felt time" ) Maybe my home area simply doesn't have many overlaps. So, what I am looking for is a tool that helps to find areas which are heavily overlapped, something like a heatmap. Anyway, for the beginning I should be happy with any tool that helps to find those places. Gerd

Date: Sun, 9 Nov 2014 23:29:03 +0000 From: steve@parabola.me.uk To: mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] Optimizing MapSplitter

Hi Gerd

...

Now I wonder what threshold values to use and if there is an existing tool that allows to display the overlaps.

Any ideas?

I've used http://garmin-img.cvs.sourceforge.net/viewvc/garmin-img/ImgViewer/ in the past although not had much luck making it work today.

I have just written a program to create an svg file with the subdivisions so it can be displayed in inkscape or similar.

I'll post it tomorrow.

..Steve _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Hi Steve, looks promising. If I got it right, the redraw time is influenced by a) how many sub divisions are overlapping a given bbox and b) how many objects are in these sub divisions and c) how complex the objects are (means, how much time it takes to render them) The optimization goal for a given bbox would be to minimize the number of (complex) objects which are outside of the bbox, as they have to be rendered and then ignored. So, maybe we can calculate a ratio between "number of objects to render" and "number of objects in the bbox" and try to optimize (minimize) that. As we don't have a given bbox, we may create a grid and measure and report the ratio of each grid element. In the past it turned out to be rather difficult to split roads at this stage, so I'd like to leave them out and split only shapes and normal lines. A possible alternative to splitting roads could be to place large road objects into their own sub division, so that they don't contain other objects. I think I'll create a new branch for that stuff. Gerd Date: Mon, 10 Nov 2014 08:46:10 +0000 From: steve@parabola.me.uk To: mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] Optimizing MapSplitter Hi Gerd

So, what I am looking for is a tool that helps to find areas which are heavily overlapped, something like a heatmap.

When displayed it looks like this: http://files.mkgmap.org.uk/download/223/Selection_040.png I need to add a couple of getters and a fix to mkgmap (attached) then I will check it all into display. ..Steve _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Hi Steve, Steve Ratcliffe wrote

As you've probably seen I've added the program to the display svn as test.svg.subdiv.Main. There is an argument '--level N' to display a different zoom level. Default is 0 (most detailed).

I've found that our OSM maps seem to have a lot more elements than other maps so it is difficult to compare. In general the way we create subdivisions means that many of them are quite large and they contain many elements. There are no small divisions.

Yes, I tried the tool on an OSM map and one from Garmin but the svg is so big and complex that it doesn't help me at this stage. Steve Ratcliffe wrote

...

If I got it right, the redraw time is influenced by a) how many sub divisions are overlapping a given bbox and b) how many objects are in these sub divisions and c) how complex the objects are (means, how much time it takes to render them)

It is also possible that the way that the divisions on different levels link together may have an effect, as it may be able to restrict the number of divisions it has to consider.

Possible, I don't yet understand how this is used in the device as objects may (dis-)appear at a certain level. Anyhow, I am pretty sure that it doesn't take much time to find the areas which intersect a given rectangle. My first approach to solve the problem was to cut polygons and non-routable lines when a sub div is split, but that doesn't seem to help much (maybe the roads are the reason). Or maybe I did something wrong or looked at an area which doesn't show the problem. Now I wonder if we should collect objects with large bboxes in their own sub divs. A small sub div could be useful in heavily populated areas. I think I first have to code a test routine. Gerd -- View this message in context: http://gis.19327.n5.nabble.com/Optimizing-MapSplitter-tp5823702p5824117.html Sent from the Mkgmap Development mailing list archive at Nabble.com.

On 13/11/14 10:58, Gerd Petermann wrote:

I played a little bit with display tool r435. I was not able to display the label in inkSkape. Is there a trick?

Yes, you need to make it visible in the layers dialog (Shift-Ctrl-L). There are two layers, subdivisions and labels. Click the eye next the the labels layer to see it. When the subdivisions are small the labels get in the way which is why I turned them off by default. There is also a layer drop down in the bottom status bar. You can use that as well.

I noticed that my Garmin maps have a rather small avg. number of elements compared to those produced by mkgmap. Up to now I found no simple rule reg. the area size of a sub div and the contained elements.

Yes they also appear to have a lot more smaller divisions in the mix. A selected distrubution from the topo map: 0: 192 1: 2121 2: 2629 3: 5249 4: 4108 5: 817 6: 122 7: 12 8: 0 9: 0 Most divisions are smaller than 100,000 units square and there doesn't really seem to be a lower limit. The first 192 must be less than 4x4 units. This is perhaps an extreme example, but in general the peak seems to be in the 10000-100000 range. ..Steve