<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<style type="text/css" style="display:none;"><!-- P {margin-top:0;margin-bottom:0;} --></style>
</head>
<body dir="ltr">
<div id="divtagdefaultwrapper" style="font-size:12pt; color:#000000; background-color:#FFFFFF; font-family:Calibri,Arial,Helvetica,sans-serif">
<p><br>
</p>
<meta content="text/html; charset=UTF-8">
<div dir="ltr">
<div id="x_divtagdefaultwrapper" style="font-size:12pt; color:#000000; background-color:#FFFFFF; font-family:Calibri,Arial,Helvetica,sans-serif">
<p>Let's try with a real world example:</p>
<p><a id="LPlnk607062" href="https://www.openstreetmap.org/way/245112355" class="x_OWAAutoLink">https://www.openstreetmap.org/way/245112355</a></p>
<p><a id="LPlnk607062" href="https://www.openstreetmap.org/way/245112355" class="x_OWAAutoLink"><br>
</a></p>
<p>This highway has 6 points, it starts in the north, the x-delta values (in resolution 24) are
<br>
</p>
<p>4, -19, -5, 0, 3</p>
<p>The largest absolute value is 19 which requires 5 bits: 10011.</p>
<p>Since both positive and negative values exist, we have to encode the sign for each single delta value, so we have to use 6 bits (the leftmost gives the sign)</p>
<p>So, the first iteration gives:</p>
<p>6 bit words : 4 = 000100 , -19 = 110011, -5 = 111011, 0 = 000000, 3 = 000011 --> 30 bits</p>
<p>Now, the optimization process starts trying to use the "trick" with 5 bits. WIth the trick,</p>
<p>the value 19 doesn't fit into 5 bits, so the trick is used (it stands for the binary value 1111) and the result for -19 is 10000 11100 (15 + 4 made negative)</p>
<p>All other values fit into 5 bits, so the 2nd iteration gives:<br>
</p>
<p><span>5<span> bit words</span>: 4 = 00100 , -19 = <span>10000 11100</span>, -5 = 11011, 0 = 00000, 3 = 00011 --> 30 bits</span></p>
<p><span></span>The next step is to try with only 4 bits. Again, only the value -19 needs the trick, this time we get - 19 = 1000
<span>1000 </span>1011 (7 +7 + 5 made negative)<br>
</p>
<p></p>
<p><span><span>4 bit words</span> : 4 = 0100 , -19 = <span>1000 1000 1011</span>, -5 = 1011, 0 = 0000, 3 = 0011 --> 24 bits</span></p>
<p><span></span></p>
<div>The next step is to try with only 3 bits. This time, more values need the trick (4 , -5 and -19). For -19 we get
<span><span><span>100 100 100 100 100 100 111</span></span></span> (3 + 3 + 3 + 3 + 3+ 3 + 1 made negative)<br>
The result:<br>
<p><span><span>3 bit words</span> : 4 = 100 001 , -19 = <span>100 100 100 100 100 100 111</span>, -5 = 100 110, 0 = 000, 3 = 011 --> 39 bits</span></p>
<p><span><br>
</span></p>
<p><span>So, we see that the trick is used too often now and the resulting bit stream is much longer than the one before.
<br>
</span></p>
<p><span><br>
</span></p>
<p><span>So, using the trick with 4 bit words saves 6 bits for the x values. <br>
</span></p>
<p><span><br>
</span></p>
<p><span>ciao,<br>
</span></p>
<p><span>Gerd<br>
</span></p>
</div>
P.S. To be complete:<br>
The y-deltas are all negative:<br>
-3, -7,- 3,- 5, -4<br>
This allows to encode only the absolute values which all fit into 3 bits, the trick doesn't help here.<br>
<p></p>
<span></span><br>
<p></p>
</div>
<hr tabindex="-1" style="display:inline-block; width:98%">
<div id="x_divRplyFwdMsg" dir="ltr"><font style="font-size:11pt" color="#000000" face="Calibri, sans-serif"><b>Von:</b> mkgmap-dev <mkgmap-dev-bounces@lists.mkgmap.org.uk> im Auftrag von nwillink <osm@pinns.co.uk><br>
<b>Gesendet:</b> Sonntag, 17. Juli 2016 16:59:19<br>
<b>An:</b> mkgmap-dev@lists.mkgmap.org.uk<br>
<b>Betreff:</b> Re: [mkgmap-dev] [Patch v1] improve LinePreparer to reduce img size</font>
<div> </div>
</div>
</div>
<font size="2"><span style="font-size:10pt">
<div class="PlainText">Many thanks for that Gerd<br>
<br>
I hope this makes it a bit clearer? <br>
<br>
The adjective 'crystal' does not immediately spring to mind but I understand<br>
what<br>
you are getting at.<br>
<br>
Presumably the patch now checks every line for the need to apply the trick.<br>
<br>
<br>
<br>
<br>
--<br>
View this message in context: <a href="http://gis.19327.n5.nabble.com/Patch-v1-improve-LinePreparer-to-reduce-img-size-tp5878545p5878569.html">
http://gis.19327.n5.nabble.com/Patch-v1-improve-LinePreparer-to-reduce-img-size-tp5878545p5878569.html</a><br>
Sent from the Mkgmap Development mailing list archive at Nabble.com.<br>
_______________________________________________<br>
mkgmap-dev mailing list<br>
mkgmap-dev@lists.mkgmap.org.uk<br>
<a href="http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev">http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev</a><br>
</div>
</span></font></div>
</body>
</html>