tag:blogger.com,1999:blog-31538815288401430692024-03-27T16:37:08.126+10:00Grant TrebbinA blog about technology, electronics, maths, physics, computers by brisbane tech enthusiast Grant TrebbinGrant Trebbinhttp://www.blogger.com/profile/13253301568478517009noreply@blogger.comBlogger200125tag:blogger.com,1999:blog-3153881528840143069.post-24492286355838680162019-10-02T22:10:00.002+10:002019-10-02T22:10:53.255+10:00Generate an STL 3D model with a surface described by an equation<div style="text-align: justify;">
I recently needed to <a href="https://www.grant-trebbin.com/2019/09/reducing-evaporation-rates-with-rippled.html">generate a 3D model for printing based on an equation</a> and couldn't find software to do the job. In the end the easiest thing to do was to write a quick Python script called "stl-surface.py" to do the job.</div>
<br />
<div style="text-align: justify;">
At first the task seemed daunting, but generating the STL file is rather easy with the use of the numpy-stl library. The equation for the surface is calculated over a structured square/rectangular grid and each little cell of the grid is split in two to form triangles. You use many many of these small triangular faces to construct the model. All you have to do is to generate the coordinates for the 3 vertices that make up each triangle and numpy-stl does the rest. The bottom and sides are flat which makes things rather easy, and the top is defined by the equation.</div>
<br />
<div style="text-align: justify;">
When constructing the model it's important to list the coordinates of each face in a counter clockwise direction when looking at the model from the outside. This allows numpy-stl to later calculate things like volume of the model and centre of gravity and also test if the surface is closed (although they use a slightly buggy way to test this).</div>
<br />
<div style="text-align: justify;">
I've shown a few examples of the generated models below.</div>
<br />
10 - 2*(1 - math.cos(2 * x * math.pi / 20)) * (1 - math.cos(2 * y * math.pi / 20))<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-Ycxe1TXh9Q4/XZSJsdfTK2I/AAAAAAAA12w/DdJ4RHicsKErz6vHEUfjvpvWAXE4tFs2wCLcBGAsYHQ/s1600/Dimple.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" data-original-height="602" data-original-width="862" height="444" src="https://1.bp.blogspot.com/-Ycxe1TXh9Q4/XZSJsdfTK2I/AAAAAAAA12w/DdJ4RHicsKErz6vHEUfjvpvWAXE4tFs2wCLcBGAsYHQ/s640/Dimple.png" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Dimpled 3D model</td></tr>
</tbody></table>
10 + 2 * math.cos(math.sqrt((x - 50)**2 + (y - 50)**2)/2)<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-L34kj8dUxaM/XZSJxNW5qbI/AAAAAAAA120/Cc47yWotGIIb96m6zaWllxmCUIlfURlEACLcBGAsYHQ/s1600/ripple.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" data-original-height="553" data-original-width="1016" height="348" src="https://1.bp.blogspot.com/-L34kj8dUxaM/XZSJxNW5qbI/AAAAAAAA120/Cc47yWotGIIb96m6zaWllxmCUIlfURlEACLcBGAsYHQ/s640/ripple.png" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Rippled 3D model</td></tr>
</tbody></table>
<br />
Here you can see how the triangles are assembled to construct the model.<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-7bwsfoDnwG4/XZSJ2nr3u3I/AAAAAAAA124/9vOrrgjZdQs__2A-ItmbLKL-SpKIcz3MgCLcBGAsYHQ/s1600/ripple2.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" data-original-height="690" data-original-width="1046" height="422" src="https://1.bp.blogspot.com/-7bwsfoDnwG4/XZSJ2nr3u3I/AAAAAAAA124/9vOrrgjZdQs__2A-ItmbLKL-SpKIcz3MgCLcBGAsYHQ/s640/ripple2.png" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">The triangular faces that make up the model</td></tr>
</tbody></table>
<br />
The triangles that form the edges of the model<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-XNQc6yUl2LQ/XZSJ_cg_ZTI/AAAAAAAA13A/-XOZ1U3rbfESrIiarmX_TmL3Vvn1FDV7QCLcBGAsYHQ/s1600/ripple3.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" data-original-height="180" data-original-width="1220" height="94" src="https://1.bp.blogspot.com/-XNQc6yUl2LQ/XZSJ_cg_ZTI/AAAAAAAA13A/-XOZ1U3rbfESrIiarmX_TmL3Vvn1FDV7QCLcBGAsYHQ/s640/ripple3.png" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Edge of the model</td></tr>
</tbody></table>
<br />
From the top you can see the grid points where the surface function is evaluated.<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-Hwx2gwkyUOU/XZSKEGmbA7I/AAAAAAAA13I/uROveAnLmlAZJyrHNk4Cz-4pneVwDcxuwCLcBGAsYHQ/s1600/ripple4.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" data-original-height="482" data-original-width="487" height="632" src="https://1.bp.blogspot.com/-Hwx2gwkyUOU/XZSKEGmbA7I/AAAAAAAA13I/uROveAnLmlAZJyrHNk4Cz-4pneVwDcxuwCLcBGAsYHQ/s640/ripple4.png" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Top of the model</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
I hope this code can help someone else. I may not be the easiest thing to use and if you need help getting started get in touch.</div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><span style="margin-left: auto; margin-right: auto;"><a href="https://gist.github.com/GrantTrebbin/5382bc3c815a933dbd22d3a1881fa334"><img border="0" data-original-height="410" data-original-width="1000" height="163" src="https://1.bp.blogspot.com/--n0qh5nBZ-E/XZSKR_brwgI/AAAAAAAA13Q/Dc9TQXUZUIEfg0YjfeY79D2uSv6nIL3UACLcBGAsYHQ/s400/GitHub_Logo.png" width="400" /></a></span></td></tr>
<tr><td class="tr-caption" style="text-align: center;"><a href="https://gist.github.com/GrantTrebbin/5382bc3c815a933dbd22d3a1881fa334">Get the code!</a></td></tr>
</tbody></table>
<br />
<br />Grant Trebbinhttp://www.blogger.com/profile/13253301568478517009noreply@blogger.com2Brisbane QLD, Australia-27.4697707 153.02512350000006-28.3721187 151.73423000000005 -26.5674227 154.31601700000007tag:blogger.com,1999:blog-3153881528840143069.post-57920083339758594452019-09-15T23:55:00.000+10:002019-09-15T23:55:20.648+10:00Self Normalising Price Markdowns For Short Life Products<div style="text-align: justify;">
When selling products that have a relatively short shelf life, it becomes necessary to reduce the price on items as they approach their use by date so they sell and aren't thrown out. This is done for several reasons.</div>
<br />
<ul>
<li>Sending plastic packaging and food that's safe to eat to landfill is a waste of resources, and in 2019 we can do a lot better than that</li>
<li>If a business can reduce its waste, they can save money on garbage collection</li>
<li>It's an acknowledgement to customers that the product isn't as flexible as one with a longer use by date</li>
<li>It adds a little excitement for customers if they can buy a product that they normally wouldn't buy because it's normally too expensive</li>
</ul>
<br />
<div style="text-align: justify;">
In my experience, supermarkets perform markdowns in an incremental way to make sure that stock isn't wasted, and to get as much money for the product that is possible. This was usually accomplished by reducing the price by 20% on the 2nd last day of sale, 30% on the morning of the last day of sale, 40% at lunch time on the last day of sale and then going 50%, 60%, 70%, 80%, and 90% until the close of the store. In essence, it's a <a href="https://en.wikipedia.org/wiki/Dutch_auction">Dutch auction</a>. This works well but has problems. People buy the most popular items first leaving an assortment of unappealing products towards the end. As fixed percentages are used across the board, it means you might be reducing some items more than you need to and some less than you need to. It's also reasonably labour intensive.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
If you track markdowns and plot a graph of the most common ones you end up with a graph like the one below, which I'll use to demonstrate a point.</div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-EhrR6WeOzJw/XX4oHZcZ6WI/AAAAAAAA1rE/WLzSUeJpJnIdxupP_5AArV0y9VM4_2kzQCLcBGAsYHQ/s1600/Graph0.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="markdown percentage graph" border="0" data-original-height="496" data-original-width="570" height="555" src="https://1.bp.blogspot.com/-EhrR6WeOzJw/XX4oHZcZ6WI/AAAAAAAA1rE/WLzSUeJpJnIdxupP_5AArV0y9VM4_2kzQCLcBGAsYHQ/s640/Graph0.png" title="markdown percentage graph" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Markdowns shouldn't waste time or money</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
In the graph above you can see that average markdown is around 50%. Traditionally you'd start with a 20% markdown, but the graph shows that in this case almost no one will buy the product at that discount. This is the "Waste of Time" section of the graph. Most likely you'll have to come back and do another markdown on the product. Conversely if you go straight to an 80% markdown you've wasted money because you mostly likely could have sold the product for more. The "Waste of Money" section. Ideally most of the markdowns should be in the 30% to 70% range, the "Sweet Spot". But how do you calculate the markdown percentages?</div>
<br />
<div style="text-align: justify;">
I'm going to demonstrate a method that doesn't necessarily generate optimum markdown percentages, but does generate percentages so that popular and unpopular products sell at roughly the same rate with a reasonable chance of selling on the first markdown.</div>
<br />
<div style="text-align: justify;">
Let's start with some Lamb Hearts, and to keep things simple, from most to least recent the markdown percentages are as follows, 98%, 66%, and 6%. This process uses a method called <a href="https://en.wikipedia.org/wiki/Kernel_density_estimation">Kernel Density Estimation</a> to generate a smooth curve of markdown probabilities. This means that at each of those percentages above you place a predefined shape, in this case a Gaussian distribution.</div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-InTJkXrVJ4w/XX4oOYHkGPI/AAAAAAAA1rI/JTHRjoeRPWglz3n3kQZnefaL3em8KIrZgCLcBGAsYHQ/s1600/Graph1.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="markdown percentage graph" border="0" data-original-height="496" data-original-width="570" height="556" src="https://1.bp.blogspot.com/-InTJkXrVJ4w/XX4oOYHkGPI/AAAAAAAA1rI/JTHRjoeRPWglz3n3kQZnefaL3em8KIrZgCLcBGAsYHQ/s640/Graph1.png" title="markdown percentage graph" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Initial placement of kernels</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
You can see the distributions listed above. You may notice that because the grey and blue curves are truncated at the sides of the graph the area under them is less. This means that they'll have less of an influence on the result. This can be corrected with a simple scaling process though.</div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-cObGbmBFqd4/XX4oUSE_LSI/AAAAAAAA1rM/UAAQImqVMWMkdQe92mHwJc6cHpLd2cKrQCLcBGAsYHQ/s1600/Graph2.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="markdown percentage graph" border="0" data-original-height="496" data-original-width="570" height="556" src="https://1.bp.blogspot.com/-cObGbmBFqd4/XX4oUSE_LSI/AAAAAAAA1rM/UAAQImqVMWMkdQe92mHwJc6cHpLd2cKrQCLcBGAsYHQ/s640/Graph2.png" title="markdown percentage graph" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Compensation for truncated kernels</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
The areas under the graphs above are now all the same, but is this what we want? Most recent markdowns should have a greater impact on the process than ones that were performed long ago. To correct this, each peak is weighted by 3 for the most recent, 2 for the next most recent, and 1 for the oldest markdown.</div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-KMB9_7afwto/XX4oa44c4NI/AAAAAAAA1rQ/jHOsRzY27I4_Byu1gf0HoqHVj69f4G-tgCLcBGAsYHQ/s1600/Graph3.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="markdown percentage graph" border="0" data-original-height="496" data-original-width="570" height="556" src="https://1.bp.blogspot.com/-KMB9_7afwto/XX4oa44c4NI/AAAAAAAA1rQ/jHOsRzY27I4_Byu1gf0HoqHVj69f4G-tgCLcBGAsYHQ/s640/Graph3.png" title="markdown percentage graph" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Weighting the kernels for recency</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
Adding each of these graphs gives the final markdown distribution in yellow.</div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-vUBrU7wOqJk/XX4ohjqpm5I/AAAAAAAA1rY/7pyCjOiq6CMRsTwgeRkc_33TXDjROQPQACLcBGAsYHQ/s1600/Graph4.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="markdown percentage graph" border="0" data-original-height="496" data-original-width="570" height="556" src="https://1.bp.blogspot.com/-vUBrU7wOqJk/XX4ohjqpm5I/AAAAAAAA1rY/7pyCjOiq6CMRsTwgeRkc_33TXDjROQPQACLcBGAsYHQ/s640/Graph4.png" title="markdown percentage graph" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Summation of the kernels</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
Now we perform a process called integration to get the light blue line. For those of you unfamiliar integration it basically records the area under a graph. For example at the 20 point on the bottom axis the blue line records the area under the yellow line up until that point.</div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-BWWESsAa8go/XX4ooBUkHZI/AAAAAAAA1rg/9we14WXQcswqxIM7x6h6cxAGB7new2TDwCLcBGAsYHQ/s1600/Graph5.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="markdown percentage graph" border="0" data-original-height="496" data-original-width="570" height="556" src="https://1.bp.blogspot.com/-BWWESsAa8go/XX4ooBUkHZI/AAAAAAAA1rg/9we14WXQcswqxIM7x6h6cxAGB7new2TDwCLcBGAsYHQ/s640/Graph5.png" title="markdown percentage graph" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Integration of the distribution to produce the final curve</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
The next step is to introduce the concept of a markdown level which ranges from 0 to 10. 0 corresponds to a 0% markdown and 10 corresponds to a 100% markdown, but in between, things are very different. As a demonstration we'll calculate the markdown percentages for markdown levels 2, 5, and 8. The process is quite simple. Find the levels on the left hand side of the graph and project them across to the blue curve and then down to the bottom of the graph. This gives percentages of 53, 80 and then 94.</div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-BeAUwQCyceg/XX4ot3bcjbI/AAAAAAAA1rk/SiqVWcxjM5IxoQ8GCqMTiYcA7E_bCq2PACLcBGAsYHQ/s1600/Graph6.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="markdown percentage graph" border="0" data-original-height="496" data-original-width="570" height="556" src="https://1.bp.blogspot.com/-BeAUwQCyceg/XX4ot3bcjbI/AAAAAAAA1rk/SiqVWcxjM5IxoQ8GCqMTiYcA7E_bCq2PACLcBGAsYHQ/s640/Graph6.png" title="markdown percentage graph" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Calculating markdowns percentages from the graph</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
For another demonstration let's try something popular like chicken breast that has recent markdowns of 30%, 10%, and 20%. This leads to percentages of 10, 22, and 33.</div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-GuUE74FzbGg/XX4oylqXgCI/AAAAAAAA1rs/ceJ8CZFxCrgBbKBWaV2SHCxmdTn3yawtwCLcBGAsYHQ/s1600/Graph7.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="markdown percentage graph" border="0" data-original-height="496" data-original-width="570" height="556" src="https://1.bp.blogspot.com/-GuUE74FzbGg/XX4oylqXgCI/AAAAAAAA1rs/ceJ8CZFxCrgBbKBWaV2SHCxmdTn3yawtwCLcBGAsYHQ/s640/Graph7.png" title="markdown percentage graph" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;"><span style="font-size: 12.8px;">Calculating markdowns percentages from the graph</span></td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
Like I said above, this isn't designed to generate an optimum markdown, it's designed to create a markdown specific to each product so that they'll sell at similar rates. In the demonstration above the situation may warrant a level 2 markdown. This means that a product that's hard to sell like lamb hearts gets a 53% markdown, while a popular item like chicken breast only gets a 10% markdown.</div>
<br />
<div style="text-align: justify;">
So a strategy may be to use a level 2 markdown on the second last day of sale, and then taper throughout the trading day from level 3 to 10 on the last day.</div>
<br />
<div style="text-align: justify;">
The demonstrations above have been quite simple and don't give a full picture of how powerful this method can be. Let's put together a complicated situation with fake data to test it.</div>
<br />
<div style="text-align: justify;">
A new flavour of sausages is introduced and we are unsure how they'll perform. They initially use an assumed prior that isn't mentioned above, but it quickly becomes obvious that they are a good seller and don't require large markdowns, with the first level 2 markdown being in the region of 15%. After 500 recorded markdowns a new similar cheaper line is introduced and the sales of the original line suffer. Before long the system calculates that the first markdown at level 2 needs to be about 55%</div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-4Ggo8z7s_Dw/XX4pAFkyRdI/AAAAAAAA1r0/jd_2r1_d1LwASlR4ql2brI4md-Hh54LPACLcBGAsYHQ/s1600/aniopt.gif" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="markdown percentage graph" border="0" data-original-height="480" data-original-width="640" height="480" src="https://1.bp.blogspot.com/-4Ggo8z7s_Dw/XX4pAFkyRdI/AAAAAAAA1r0/jd_2r1_d1LwASlR4ql2brI4md-Hh54LPACLcBGAsYHQ/s640/aniopt.gif" title="markdown percentage graph" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Animation of the markdown calculation process</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
The animation above is generated from 500 random markdowns with an average of 20% and then 500 random markdowns with an average of 80%. The calculations take into account the last 100 markdown and are weighted from 1 to 100.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
There are a couple important points to consider. Firstly the process uses a lot of statistical methods and equations but isn't really grounded in theory. It uses the properties of the methods to create a stable system that fits the requirements that are specified. The next thing to remember is that this process will follow the markdowns. If you start the markdown process at level 8 without even trying something less than a level 5. The system will generate larger and larger markdowns. A stabilising term can be added to prevent this.</div>
<br />
<div style="text-align: justify;">
It's not a perfect method but it's a lot better than some of the optimised markdown systems I've seen. I actually trialed this process a while ago(I have no deep access to the computers and had to do it manually) in my store and it's fascinating to see it converge on higher and lower markdowns based on the saleability of the product.</div>
Grant Trebbinhttp://www.blogger.com/profile/13253301568478517009noreply@blogger.com0Brisbane QLD, Australia-27.4697707 153.02512350000006-28.3721187 151.73423000000005 -26.5674227 154.31601700000007tag:blogger.com,1999:blog-3153881528840143069.post-1484595879302926572019-09-14T22:28:00.002+10:002019-09-14T22:28:53.801+10:00Reducing Evaporation Rates With Rippled Surfaces<div style="text-align: justify;">
A theory that I want to test out is that adding a ripple to a surface makes it easier to clean in certain situations. I work in retail, and sometimes the cleaning of non food safety related issues are delayed due to more important tasks. In particular I'm talking about drips. You might see these on metal trays under bottles of milk in the fridge, or on plastic sheets under the shelves in the meat department. In both cases drips are meant to be caught on a surface that is easy to remove and clean. The problem is that if you leave a spill too long it dries and become hard to remove and requires vigorous cleaning which may damage the surface and waste time.</div>
<br />
<div style="text-align: justify;">
To avoid this, you want to slow the rate of evaporation. This can be done by decreasing the surface area by increasing the depth. A rippled surface is perfect for this. You essentially make little cups to hold the spill. Another requirement that would be nice to include is no tight internal corners. Anything that is designed to be cleaned shouldn't contain a concave surface that you can't get a finger into. Anyone that knows me well understands that I think in equations, and the one below matches our criteria perfectly.</div>
<br />
$$$z=10 - 8 \left(\dfrac{1-\cos(2\pi x / 20)}{2}\right)\left(\dfrac{1-\cos(2\pi y / 20)}{2}\right)$$$<br />
<br />
<div style="text-align: justify;">
Let's talk about what this equation means. The two large sections in the brackets are periodic terms that create ripples in the x and y directions. The 20 means that this ripple will repeat every 20mm. By subtracting the cos term from one and then dividing that result by 2, the term in the bracket will range from 0 to 1. Multiplying the two brackets together will also give a result between 0 and 1. By multiplying this by 8 we now have a function that ranges from 0 to 8. The 10 describes the maximum of the equation. By subtracting the rest of the equation from 10 we now have a surface that ranges from 2 to 10 above zero. The important things to remember are, 20 specifies how wide the ripples are, and 8 describes how deep they are.</div>
<br />
<div style="text-align: justify;">
Sometimes though it helps to have the real thing in your hand to test so I created a 3d model to send away for 3d printing. There doesn't seem to be anything out there to create a 3d model from an equation so I had to write some software to do that. I'll post that when I tidy it up and comment it properly.</div>
<br />
<div style="text-align: justify;">
I'm not made of money so the model is only 100mm x 100mm x 10mm (a volume of 100mL) with 20mm wide ripples that are 8mm deep. By a stroke of luck, I happened to write the software is a way that easily calculates the volume of the model. In this case the model is 80 mL. As the bounding box of the model is 100 mL this means the volume of the 25 little cups is 20mL. Each one holding 0.8 mL.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-WhlteTSr-yU/XXzB8bFF_1I/AAAAAAAA1qg/GsgQwJeBA3gxZlAk6hRCdab0vc9vDYPHgCLcBGAsYHQ/s1600/Tray.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="3D model of a rippled surface" border="0" data-original-height="567" data-original-width="900" height="401" src="https://1.bp.blogspot.com/-WhlteTSr-yU/XXzB8bFF_1I/AAAAAAAA1qg/GsgQwJeBA3gxZlAk6hRCdab0vc9vDYPHgCLcBGAsYHQ/s640/Tray.png" title="3D model of a rippled surface" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Rippled Drip Tray</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
I don't have the print yet, but it has been done and photos sent to me. In theory this surface should hold 20 mL of liquid and covers an area of 100 square centimeters, so as a test I poured 20 mL of water on a flat surface and it spread to cover 180 square centimeters. So already the ripple pattern has reduced the surface area by 45%</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-B6tWvT6SM_I/XXzCBFjWaVI/AAAAAAAA1qk/WtKlygzyusk9eQ-0d6x4RB9jJCGTtUX2gCLcBGAsYHQ/s1600/Tray1_1200x1200.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="3D printed model of a rippled surface" border="0" data-original-height="675" data-original-width="1200" height="360" src="https://1.bp.blogspot.com/-B6tWvT6SM_I/XXzCBFjWaVI/AAAAAAAA1qk/WtKlygzyusk9eQ-0d6x4RB9jJCGTtUX2gCLcBGAsYHQ/s640/Tray1_1200x1200.jpg" title="3D printed model of a rippled surface" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">3D Printed Drip Tray Top</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
That may not sound like much, but the ripples can be made deeper. If they were 3x times deeper (24mm) the surface would hold 60mL. Once they get too deep though, you would need to make the ripples wider to make cleaning easier. Changing the width of the ripples doesn't effect the volume that the surface would hold though.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-vPhAiwPWz4I/XXzCI5J8luI/AAAAAAAA1qo/nIIhlOPYQAQo3yh2GJeixFauVIuBbI7vQCLcBGAsYHQ/s1600/Tray2_1200x1200.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="3D printed model of a rippled surface" border="0" data-original-height="675" data-original-width="1200" height="360" src="https://1.bp.blogspot.com/-vPhAiwPWz4I/XXzCI5J8luI/AAAAAAAA1qo/nIIhlOPYQAQo3yh2GJeixFauVIuBbI7vQCLcBGAsYHQ/s640/Tray2_1200x1200.jpg" title="3D printed model of a rippled surface" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">3D Printed Drip Tray Top</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
In this demonstration I've shown the surface as a solid block with depressions. In reality you'd use something like a polypropylene sheet moulded to this shape. It would give an object shaped similar to an egg carton.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-KaKXb0FLHHw/XXzCPMR5MtI/AAAAAAAA1qs/rRHVFv4nH3IeBTv9ZxGqZ-u2fn0xa9SfQCLcBGAsYHQ/s1600/Tray3_1200x1200.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="3D printed model of a flat surface" border="0" data-original-height="675" data-original-width="1200" height="360" src="https://1.bp.blogspot.com/-KaKXb0FLHHw/XXzCPMR5MtI/AAAAAAAA1qs/rRHVFv4nH3IeBTv9ZxGqZ-u2fn0xa9SfQCLcBGAsYHQ/s640/Tray3_1200x1200.jpg" title="3D printed model of a flat surface" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">3D Printed Drip Tray Base</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
Anyway, this is just a thought that I wanted to explore. Maybe it'll work out, maybe it won't. Either way the process was enjoyable.</div>
Grant Trebbinhttp://www.blogger.com/profile/13253301568478517009noreply@blogger.com0Brisbane QLD, Australia-27.4697707 153.02512350000006-28.3721187 151.73423000000005 -26.5674227 154.31601700000007tag:blogger.com,1999:blog-3153881528840143069.post-69723773018728370792017-10-15T23:22:00.000+10:002017-10-15T23:26:45.662+10:00ABC Logo Lissajous Curve<div style="text-align: justify;">
Over the last couple of days I've seen a few people mention how similar the ABC Australian logo is to the new Disney Movies Anywhere service. I don't know much about the legal side of things, but I thought an explanation of why the ABC logo looks the way it does might be interesting.</div>
<br />
<div style="text-align: justify;">
The shape of logo is called a <a href="https://en.wikipedia.org/wiki/Lissajous_curve">Lissajous figure or curve</a>. The shape is generated by a parametric equation where the x and y coordinates are sinusoidal. The frequency and phase relationship between the two equations for x and y determine the shape. In the case of the ABC logo, the frequency of the y coordinate is 3 times that of the x coordinate and there is a 90 degree phase shift (I'll clarify this later) applied the y equation.</div>
<br />
<div style="text-align: center;">
$$$x=cos(t)$$$ and $$$y=cos(3t+\pi/2)$$$</div>
<br />
<div style="text-align: justify;">
To make things clearer I've put together an animation. As the vertical bar sweeps across the screen it will intersect the x and y equations. The y coordinate is projected across and the x coordinate is projected across and up. The Lissajous figure is drawn where the project lines intersect.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://2.bp.blogspot.com/-B4KuNdwHzN8/WeMhXh-UJNI/AAAAAAAArzU/SeWKYVXZDFgaSUVZOeD6Mu8v-GGSAlWhACLcBGAs/s1600/Liss1s.gif" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" data-original-height="540" data-original-width="960" height="360" src="https://2.bp.blogspot.com/-B4KuNdwHzN8/WeMhXh-UJNI/AAAAAAAArzU/SeWKYVXZDFgaSUVZOeD6Mu8v-GGSAlWhACLcBGAs/s640/Liss1s.gif" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Tracing a 3:1 Lissajous Curve x=cos(t) y=cos(3t + $$$\pi$$$/2)</td></tr>
</tbody></table>
<div style="text-align: justify;">
The phase shift is also very important to the shape. In the animation below you can see how the it changes as the phase shift is cycled across all possible values from 0 to $$$2\pi$$$.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-hAK3b-AgCDw/WeMhr7lskEI/AAAAAAAArzY/wwMVjamNqP4qZs7QCNZt6f17dvuDQFUIACLcBGAs/s1600/Liss2s.gif" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" data-original-height="540" data-original-width="960" height="360" src="https://4.bp.blogspot.com/-hAK3b-AgCDw/WeMhr7lskEI/AAAAAAAArzY/wwMVjamNqP4qZs7QCNZt6f17dvuDQFUIACLcBGAs/s640/Liss2s.gif" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Changing the phase relationship of a Lissajous Curve x=cos(t) y =cos(3t + $$$\delta$$$)</td></tr>
</tbody></table>
<div style="text-align: justify;">
These curves aren't just a mathematical curiosity, they have a real world application. They used to be a very important tool for broadcast engineers. If two signals are feed into an oscilloscope (a tool that plots electrical waveforms) while it's in x-y mode, the Lissajous curve on the screen will reveal things about the signals.</div>
<br />
<div style="text-align: justify;">
The first thing to notice is that the number of horizontal and vertical lobes indicates the ratio of the frequencies. If the ratio of frequencies is rational (can be expressed as the ratio of two integers) the curve will be stationary. If not, it will slowly rotate like the second animation. If the two signal are meant to be locked together so that one is exactly 3 times the other like in the example above but the curve rotates, you know there's a problem. The rotation rate of the curve tells the engineer the deviation from the desired frequency. There are simple lookup tables like the one below that show what the curves should look like for a given phase shift and frequency ratio.</div>
<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://2.bp.blogspot.com/-eF42zfl9NqM/WeNNdNB4r2I/AAAAAAAArz0/8NRPQI0RqUclgyJYtcwF5stOSG5XPYHqwCLcBGAs/s1600/mecana484.gif" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" data-original-height="487" data-original-width="515" height="603" src="https://2.bp.blogspot.com/-eF42zfl9NqM/WeNNdNB4r2I/AAAAAAAArz0/8NRPQI0RqUclgyJYtcwF5stOSG5XPYHqwCLcBGAs/s640/mecana484.gif" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Frequency Ratios and Phase Differences</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
Earlier I said I'd elaborate on phase shift. The main thing to note is that you are working with two different frequencies. 1 degree of phase shift on one signal will take a different amount of time to 1 degree of phase shift on the other. So it's important to not just note that there is a phase shift of 30 degrees, you have to specify what waveform you are referring to. That's why a lot of the table results may be different from what you measure. In a mathematical sense, it also makes a difference if you are talking about sine or cosine signal as one is a phase shifted version of the other.</div>
<br />
<div style="text-align: justify;">
Just to clear up another thing as well. The second animation is generated by plotting a waveform frame and then changing the phase an repeating this process. This is what makes it rotate. By chance though, this is exactly what you would see if the frequencies weren't locked together. A time varying phase is no different to making a small deviation to the frequency.</div>
Grant Trebbinhttp://www.blogger.com/profile/13253301568478517009noreply@blogger.com0Brisbane QLD, Australia-27.4697707 153.02512350000006-28.3721187 151.73423000000005 -26.5674227 154.31601700000007tag:blogger.com,1999:blog-3153881528840143069.post-66977053530398440722017-08-16T20:50:00.001+10:002017-08-16T20:50:57.260+10:00Suburban Fulfilment Centre<div style="text-align: justify;">
A few weeks ago I was thinking about online grocery fulfilment and different ways of getting stock to customers faster. I had some ideas about the form factor of the facilities involved and thought I'd write about what I'm calling the Suburban Fulfilment Centre (SFC).</div>
<br />
<div style="text-align: justify;">
There are many important factors that add up to make a good online shopping experience, but when you strip away everything else, customers want a service that is fast, has a large range of products, and has reasonable fees. An important way to accomplish this is to do something that I call "tightening the loop". The time between a customer buying something and the stock being replenished and available for reorder needs to be as small as possible. It's important to have stock for customers to buy, but if you don't have a stock quickly flowing in to replace it you've failed.<br />
<br />
Unlike regular parcel delivery, grocery shipments have some constraints that makes the process more challenging. Parts of the order need to be refrigerated, and some parts have a short shelf life. You can't just put a bottle of milk and some bananas in a box with some bubble wrap and ship it across the country in a cost effective manner. These constraints mean you need to have a supply of stock close to the final destination. If you're astute, you may have noticed that I just described a grocery store. Let's play with that idea.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
What's really needed is a supermarket that's able to supply a much larger range, but keeping the online shopping model at the forefront of the planning. Around my local area a lot of 5 storey apartments are being built and I started to wonder if these could fill the roll. If an fulfilment centre with the exact same external appearance was built with a ground level drive-through, the only noticeable difference would be traffic to and from the centre. It would blend into the surrounding area and supplant current facilities that don't fit into the surrounds. To explore the idea, I selected a local set of apartments to study and run some numbers on.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-Jhr40XC4iiQ/WZPLT_CmhrI/AAAAAAAAphA/0OPgfXme6AUyACHgqAyupciPRrkjXb7VACLcBGAs/s1600/SFC_1.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Apartment Building" border="0" data-original-height="938" data-original-width="1463" height="410" src="https://3.bp.blogspot.com/-Jhr40XC4iiQ/WZPLT_CmhrI/AAAAAAAAphA/0OPgfXme6AUyACHgqAyupciPRrkjXb7VACLcBGAs/s640/SFC_1.jpg" title="Apartment Building" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Apartment Building</td></tr>
</tbody></table>
To further illustrate the idea, I've included some screenshots from StreetView of a storage company in Brisbane with a McDonald's wedged underneath it. The drive-though runs under the building and is similar to what I pictured for an ideal pick up location.<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-vSMr8ET09Zk/WZPLeJuCQEI/AAAAAAAAphE/A8SDBIadCyIJ74O7MYPkMYb31jQ8c69HwCLcBGAs/s1600/SFC_2.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Drive Through" border="0" data-original-height="853" data-original-width="1600" height="339" src="https://1.bp.blogspot.com/-vSMr8ET09Zk/WZPLeJuCQEI/AAAAAAAAphE/A8SDBIadCyIJ74O7MYPkMYb31jQ8c69HwCLcBGAs/s640/SFC_2.jpg" title="Drive Through" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Ground Level Drive Through</td></tr>
</tbody></table>
<div style="text-align: justify;">
Although I've been talking about a drive through for customers picking up orders, it would also serve as a loading dock for receiving stock and dispatching orders that get delivered directly to customers. Obviously there needs to be separation of different kinds of traffic for safety reasons, but there would be multiple drive-through lanes and when needed, one could be shut down and isolated for a delivery or dispatch.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-XzA_6UIeE-4/WZPLlBQ5HNI/AAAAAAAAphI/2LbEsfOa7MMhWuJOnhm0SgU40ENy9E69QCLcBGAs/s1600/SFC_3.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Drive Through" border="0" data-original-height="852" data-original-width="1600" height="340" src="https://4.bp.blogspot.com/-XzA_6UIeE-4/WZPLlBQ5HNI/AAAAAAAAphI/2LbEsfOa7MMhWuJOnhm0SgU40ENy9E69QCLcBGAs/s640/SFC_3.jpg" title="Drive Through" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Ground Level Drive Through</td></tr>
</tbody></table>
<div style="text-align: justify;">
So how much space do we have to play with? The apartment shown above has a gross floor area of 419 m<span style="background-color: white; color: #222222; font-family: "arial" , sans-serif; font-size: 16px;">².</span><br />
<span style="background-color: white; color: #222222; font-family: "arial" , sans-serif; font-size: 16px;"><br /></span></div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-DaLRbyEQdys/WZPL1_P3apI/AAAAAAAAphM/zqRkNWncQb8EtIE2Lwjyq42_r18G7aycQCLcBGAs/s1600/SFC_4.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Floor Plan" border="0" data-original-height="928" data-original-width="1558" height="380" src="https://3.bp.blogspot.com/-DaLRbyEQdys/WZPL1_P3apI/AAAAAAAAphM/zqRkNWncQb8EtIE2Lwjyq42_r18G7aycQCLcBGAs/s640/SFC_4.png" title="Floor Plan" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Apartment Floor Plan</td></tr>
</tbody></table>
The height of the levels 1 to 4 is 11.2 meters. This gives us a volume of 4700 m³. But what does that actually mean? How much range can we fit in that volume?<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-RjcVWke9l4k/WZPL_DTf4_I/AAAAAAAAphQ/dh16YxYHifkrVXw4P_d1VmMvNs1qqZrGgCLcBGAs/s1600/SFC_5.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Apartment Elevation" border="0" data-original-height="800" data-original-width="1035" height="494" src="https://3.bp.blogspot.com/-RjcVWke9l4k/WZPL_DTf4_I/AAAAAAAAphQ/dh16YxYHifkrVXw4P_d1VmMvNs1qqZrGgCLcBGAs/s640/SFC_5.png" title="Apartment Elevation" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Apartment Height</td></tr>
</tbody></table>
<div style="text-align: justify;">
Let's look at the floor plan of a supermarket and do some visualisation exercises. It should be immediately obvious that there is a lot of unused floor space, what's not seen is that of the space that is utilised a lot of it is empty space. Next time you go shopping look at the displays and imagine what would happen if all the shelving suddenly vanished. How big would the pile of stock on the floor be? Typically shelves are utilised fully side to side, but vertically they might be only 70% full, and front to back they might be only 70% full on average. Therefore it's not outrageous to suggest that volumetrically, the shelves are only half full.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-p0ocQoldEQo/WZPMLq5w57I/AAAAAAAAphU/w3kZXzYiWU4M5qCcP-FwJZwTS27h1AN-gCLcBGAs/s1600/SFC_6.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Floor Plan" border="0" data-original-height="933" data-original-width="1442" height="414" src="https://4.bp.blogspot.com/-p0ocQoldEQo/WZPMLq5w57I/AAAAAAAAphU/w3kZXzYiWU4M5qCcP-FwJZwTS27h1AN-gCLcBGAs/s640/SFC_6.jpg" title="Floor Plan" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Supermarket Floor Plan</td></tr>
</tbody></table>
<div style="text-align: justify;">
How much does a supermarket hold though. Let's do some Fermi approximation.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
10 aisles × 2 meters high × 1 meter wide × 15 meters long × half full = 150 m³</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
Let's say that the grocery department holds two thirds of all the stock in a store. This means that in total a store holds 225 m³ of product.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
Just as a sanity check, that's equivalent to the volume of 92 × 1.8 m high Australian pallets. From my experience that sounds about right to fill a store from empty.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
Another important number to remember is that an average supermarket stocks about 15 thousand different items. This would mean that each item on average occupies about 15 L of space. That may seem wrong but some items need much more and some need a lot less, and remember this is the raw volume of the stock, not shelf space.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
Let's look at how much space a purpose built fulfilment facility uses. The image below is of a supermarket dark store without customers. This makes it easier to fulfil online orders by staff manually picking individual orders. As you can see though, not much of the facility is actually occupied. It's a giant waste of space. I can understand why they've done it though. It's a cheap and easy way to get started with online fulfilment without going all in automating the process. I'm still surprised that going all in is questioned. Amazon did it and look at how well it worked out for them.</div>
<div style="text-align: justify;">
<br /></div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-6R8Mcs_WB94/WZQMXZ2DD0I/AAAAAAAAph0/hY_DBMri2wcj1Kj3M2S3znt80mk5oh-nQCLcBGAs/s1600/ie-sydney2-1.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Warehouse" border="0" data-original-height="599" data-original-width="1104" height="346" src="https://3.bp.blogspot.com/-6R8Mcs_WB94/WZQMXZ2DD0I/AAAAAAAAph0/hY_DBMri2wcj1Kj3M2S3znt80mk5oh-nQCLcBGAs/s640/ie-sydney2-1.jpg" title="Warehouse" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Current Dark Store Layout</td></tr>
</tbody></table>
<div style="text-align: justify;">
I keep talking about wasted space but what's the alternative? The system in the animation below is an automated tote storage and retrieval system by Dematic. There's wasted space in this example but the design can be optimised to use a lot more space of a building. It transfers the stock to a picking station where an operator assembles orders. This configuration is referred to as a goods to person solution, which means operators don't have to walk to assemble orders. It also reduces bending, reaching, and lifting.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
The other important advantage of this is that each tote is traceable and for perishable food, its use by date is also known and action can be taken to clear the stock before it's wasted.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><span style="margin-left: auto; margin-right: auto;"><a href="https://youtu.be/DQq_S4RoSKM"><img alt="Tote storage system" border="0" data-original-height="180" data-original-width="320" height="360" src="https://1.bp.blogspot.com/-I6dyvmRvMv4/WZPMiaZK-3I/AAAAAAAAphY/-j20ihx30fUCQkjOAzsJ6-agvSC-l5ZmACLcBGAs/s640/Dematic_Multishuttle_1.gif" title="Tote storage system" width="640" /></a></span></td></tr>
<tr><td class="tr-caption" style="text-align: center;"><a href="https://youtu.be/DQq_S4RoSKM">Dematic Multi-Shuttle System</a></td></tr>
</tbody></table>
<div style="text-align: justify;">
Some items are so small that they may only fill part of a tote, in these cases a divider is used. In some cases items are too large to fit and will need to be stored in a bulk handling area. Over time a manufacturer may also alter their products to be tote friendly as it may offer a cost saving.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><span style="margin-left: auto; margin-right: auto;"><a href="https://youtu.be/hD1kZuAv9A4"><img alt="Tote storage system" border="0" data-original-height="180" data-original-width="320" height="360" src="https://3.bp.blogspot.com/-b6uNhNS6NK0/WZPMtVsmHFI/AAAAAAAAphc/NHWxk5Tr5HwYX7ctf8c3F6uazaXo9gU6wCLcBGAs/s640/Dematic_Multishuttle_2.gif" title="Tote storage system" width="640" /></a></span></td></tr>
<tr><td class="tr-caption" style="text-align: center;"><a href="https://youtu.be/hD1kZuAv9A4">Dematic Multi-Shuttle System</a></td></tr>
</tbody></table>
<div style="text-align: justify;">
Let's circle back to the concept of the suburban fulfilment centre with a 4700 m³ volume. Let's say only one third of it is used for a stock management system like the one by Dematic above, and of that third only one half of it is full. That's a raw stock volume of 783 m³. If each item takes up 15 L of space that means the building can hold about 52 thousand items. There's a lot of assumptions in my calculations and the number could be much higher or lower but I think it's worth investigating further. Especially when you take into consideration that extra items above what would normally be stocked in a supermarket would most likely take less space due to lower demand.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
Each SFC doesn't need to hold the full range a service offers either. It may only need to hold 30 thousand core items and 20 thousand supplemental items. There may be multiple facilities reasonably close to each other that may hold different supplemental items and a few times a day small vans move stock between them.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
The SFC would also be used to supply nearby retail spaces of the company with low demand items. that are a bit esoteric. Ask yourself if a supermarket really needs that many packets of black dye on the shelf or are they only there because that's how many come in a box. It's a waste of space and it's money sitting on the shelf.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
Another consideration is the capacity of the drive through. If two lanes are open for 14 hours a day and a pick up take 2 minutes, that's 840 customers per day at capacity. If they each take a 200 L trolley load that's 168 m³ of stock per day which the facility can easily hold.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
I do actually have a serious reason for thinking about this problem. The less interaction staff have with stock the better. At the moment it's common practice for stock to arrive in store on a pallet like the one seen below. Think about that for a moment, at the warehouse people manually assemble these pallets and at the store people manually disassemble them. The only outcome of this process is people with injuries from a lifetime of manual labour. Finding meaningful replacement work for these people is important but I believe that a company has a moral obligation to minimise injuries where possible.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-z71oI3jmGEs/WZQMK2FdzXI/AAAAAAAAphw/fVUuSsmYI2g4WUe_34nIAfcHMZSMkeOgQCLcBGAs/s1600/typical-pallet-of-grocery-items-an-everyday-task.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Pallet" border="0" data-original-height="1000" data-original-width="565" height="640" src="https://3.bp.blogspot.com/-z71oI3jmGEs/WZQMK2FdzXI/AAAAAAAAphw/fVUuSsmYI2g4WUe_34nIAfcHMZSMkeOgQCLcBGAs/s640/typical-pallet-of-grocery-items-an-everyday-task.jpg" title="Pallet" width="360" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Pallet of stock</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
Finally to give you an idea of what the inside of what one of these facilities look like, the animation below is of a warehouse that does basically the same thing, only with pallets. Nothing I'm talking about is new, it's just a scaled down version of what's currently happening.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><span style="margin-left: auto; margin-right: auto;"><a href="https://youtu.be/qDUng9HoAK4"><img alt="Warehouse" border="0" data-original-height="180" data-original-width="320" height="360" src="https://2.bp.blogspot.com/-CQU2k3GAqYM/WZPM6Pj8UVI/AAAAAAAAphg/Sojl0ztJNBko97BeiZ0-EdUeqts9gURpgCLcBGAs/s640/Jungheinrich.gif" title="Warehouse" width="640" /></a></span></td></tr>
<tr><td class="tr-caption" style="text-align: center;"><a href="https://youtu.be/qDUng9HoAK4">44m High, 12000 pallet, Jungheinrich High Rack Warehouse</a></td></tr>
</tbody></table>
<div style="text-align: justify;">
I should point out that all ideas are my own and not those of my employer. I've also purposefully used images publicly available online instead of using my own.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
<a href="https://drive.google.com/drive/folders/0B5Hb04O3hlQSTVVtX192bTFBaGc?usp=sharing">Supplemental documentation</a></div>
Grant Trebbinhttp://www.blogger.com/profile/13253301568478517009noreply@blogger.com0Brisbane QLD, Australia-27.4697707 153.02512350000006-28.3721187 151.73423000000005 -26.5674227 154.31601700000007tag:blogger.com,1999:blog-3153881528840143069.post-81355351198159641272017-08-05T22:30:00.000+10:002017-08-05T22:30:37.338+10:00Riveting Plywood to Metal<div style="text-align: justify;">
Today I'll give you a quick rundown of my experiment riveting aluminium to plywood.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-GFa-oYlIDP8/WYWafl1GV7I/AAAAAAAApcs/Tmo5TV83_WcNCEZJ_U9cqc25_QdjZ_koACLcBGAs/s1600/AluminiumRivet2.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Rivet" border="0" data-original-height="565" data-original-width="1084" height="332" src="https://1.bp.blogspot.com/-GFa-oYlIDP8/WYWafl1GV7I/AAAAAAAApcs/Tmo5TV83_WcNCEZJ_U9cqc25_QdjZ_koACLcBGAs/s640/AluminiumRivet2.jpg" title="Rivet" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">2.8 mm Plywood Riveted to 1.4 mm Aluminium</td></tr>
</tbody></table>
<div style="text-align: justify;">
If you've read my blog before you may know I like boxes and storage solutions. I made some <a href="http://www.grant-trebbin.com/2016/09/custom-storage-box-prototypes.html">prototype storage boxes</a> last year out of 19 mm pine and plywood, and since then they have been used quiet a lot. The main problem I have with them is they are heavy, use more material than is really needed, and are complicated to make. I wanted to simplify things and for inspiration I turned to an ammunition case that I have from 1958. It's made from ply and is riveted together with metal edges. All the components themselves are not specifically strong, but when assembled the case is rather sturdy.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-6GZ_93q1kUo/WYWxttn6g3I/AAAAAAAApdU/cWbIGXFI6iMtLbdz9CPLrSMqBdX3wa14ACLcBGAs/s1600/untitled.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Ammunition Box" border="0" data-original-height="466" data-original-width="627" height="474" src="https://4.bp.blogspot.com/-6GZ_93q1kUo/WYWxttn6g3I/AAAAAAAApdU/cWbIGXFI6iMtLbdz9CPLrSMqBdX3wa14ACLcBGAs/s640/untitled.jpg" title="Ammunition Box" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Ammunition Box</td></tr>
</tbody></table>
<div style="text-align: justify;">
I happened to find some brass rivets on AliExpress that are used for material, you may be wearing some now. Have a look at your jeans. The type I purchased are called double capped, meaning they have flat rivets on both sides. They consist of a cap and post that are pressed together.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://2.bp.blogspot.com/-lBF0bm23lqw/WYWaqtxOSrI/AAAAAAAApcw/GlNx5B8aw-E2JZ2iebGd1IVTvVxyCldNACLcBGAs/s1600/BrassRivet3.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Rivet" border="0" data-original-height="162" data-original-width="250" src="https://2.bp.blogspot.com/-lBF0bm23lqw/WYWaqtxOSrI/AAAAAAAApcw/GlNx5B8aw-E2JZ2iebGd1IVTvVxyCldNACLcBGAs/s1600/BrassRivet3.jpg" title="Rivet" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Brass Rivet Cap</td></tr>
</tbody></table>
<div style="text-align: justify;">
I ordered these because they were listed as 10 mm long. I thought that this would mean I could join materials up to 10 mm (leaving room for compression of course). Unfortunately I was mistaken. The length of the post is 10 mm but this only leaves 8.5 mm space for materials, and after compression of the rivets only about 5-6 mm are feasible.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-EjO2i2fIaow/WYWbFEnq2BI/AAAAAAAApc0/XKNzDbkTpfoxg5JPPzAw4iUodS0mraVNACLcBGAs/s1600/BrassRivet4.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Rivet" border="0" data-original-height="218" data-original-width="206" src="https://1.bp.blogspot.com/-EjO2i2fIaow/WYWbFEnq2BI/AAAAAAAApc0/XKNzDbkTpfoxg5JPPzAw4iUodS0mraVNACLcBGAs/s1600/BrassRivet4.jpg" title="Rivet" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Brass Rivet Post</td></tr>
</tbody></table>
.<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-mhedlKiBZqo/WYWbSI1NpnI/AAAAAAAApc4/OcUE_PrIEuYbrHL1EMXOZLXAGibOPp_NACLcBGAs/s1600/BrassRivet1.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Rivet" border="0" data-original-height="189" data-original-width="242" src="https://1.bp.blogspot.com/-mhedlKiBZqo/WYWbSI1NpnI/AAAAAAAApc4/OcUE_PrIEuYbrHL1EMXOZLXAGibOPp_NACLcBGAs/s1600/BrassRivet1.jpg" title="Rivet" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Rivet Test Compression</td></tr>
</tbody></table>
<div style="text-align: justify;">
For my test I planned to join some 6 mm ply to a piece of aluminium angle, but because the rivets are smaller than I planned I used 3 mm plywood. Two 3 mm holes were drilled into the aluminium and the posts were inserted. A hole slightly larger (about 3.75 mm) was drilled in the ply, the caps inserted and the the rivets clipped together. For the final compression step no fancy tools were used. They were placed in a vice and I squashed the hell out of them.</div>
<br />
<div style="text-align: justify;">
The results speak for themselves. I think they look awesome and they will not budge.</div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-An-FnYmT2as/WYWbhxsBO8I/AAAAAAAApc8/xXGmOS9cSTE8sgI9zlHnIZvPVB6Xic5wACLcBGAs/s1600/AluminiumRivet1.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Rivet" border="0" data-original-height="420" data-original-width="1256" height="214" src="https://3.bp.blogspot.com/-An-FnYmT2as/WYWbhxsBO8I/AAAAAAAApc8/xXGmOS9cSTE8sgI9zlHnIZvPVB6Xic5wACLcBGAs/s640/AluminiumRivet1.jpg" title="Rivet" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Aluminium Side</td></tr>
</tbody></table>
<div style="text-align: justify;">
The dark wood and brass look nice together gives the strength I need. I think I'm on to something.</div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-fFtFUDSU8XQ/WYWbn4hW-gI/AAAAAAAApdA/uDrxL0z-keA8JFX9XkWF-URNtVMXBixdQCLcBGAs/s1600/PlywoodRivet.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Rivet" border="0" data-original-height="429" data-original-width="1085" height="252" src="https://1.bp.blogspot.com/-fFtFUDSU8XQ/WYWbn4hW-gI/AAAAAAAApdA/uDrxL0z-keA8JFX9XkWF-URNtVMXBixdQCLcBGAs/s640/PlywoodRivet.jpg" title="Rivet" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Plywood Side</td></tr>
</tbody></table>
I'm not actually building a box in this post. This is just a test, and besides I don't think the size of box I want to make will work with 3 mm ply. I need slightly bigger rivets. So now we wait the standard 2 or 3 weeks for a shipment from China. :-(<br />
<br />
<div style="text-align: justify;">
There are plenty of designs for storage boxes that may be better than mine, but what I'm aiming for is a good strength to weight ratio box that can be easily assembled by people at home without exotic materials and tools. The idea is that if you want a box you go and buy some ply and metal and use rivets you've purchased.</div>
Grant Trebbinhttp://www.blogger.com/profile/13253301568478517009noreply@blogger.com0Brisbane QLD, Australia-27.4697707 153.02512350000006-28.3721187 151.73423000000005 -26.5674227 154.31601700000007tag:blogger.com,1999:blog-3153881528840143069.post-15496297232291029712017-06-16T21:27:00.000+10:002017-06-16T21:27:18.247+10:00Merge A Data Set With A Template File To Generate Output Files<div style="text-align: justify;">
For something I'm working on I need to be able to create a large number of files by filling in fields in a template file with entries from a data set. You'd think that would be easy with Linux but I couldn't find a way to do it. (This will be where people tell me a thousand different ways to do it) I didn't think what I wanted was complicated so I wrote SimpleMerge to take care of it. It is a basic Python script that takes data from a tab delimited data file and fills in data fields in a template file.</div>
<br />
<div style="text-align: justify;">
The first row of the data file are the field identifiers to find and replace and the other rows are just data. This file can be easily generated from a spreadsheet program. The template file contains the structure of the file you intend to create, just with field identifiers in the place of real data.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
I haven't done extensive testing on the program but it seems to work fine. It handles UTF-8 file encoding and maintains the line endings of the template file for both UNIX and Windows systems. The following command generates the two files <span style="font-family: Courier New, Courier, monospace;">File1.txt</span> and <span style="font-family: Courier New, Courier, monospace;">File2.txt</span> as seen in the block diagram below.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: center;">
<span style="font-family: Courier New, Courier, monospace;">SimpleMerge.py template.txt Data.txt</span></div>
<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://2.bp.blogspot.com/-_ug5k4-cS00/WUO2hPpkkgI/AAAAAAAAnqA/-ecx2OilcLQl0HpP_0EHTkwynB9Fj6ftwCLcBGAs/s1600/Presentation1.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Block Diagram" border="0" data-original-height="296" data-original-width="970" height="194" src="https://2.bp.blogspot.com/-_ug5k4-cS00/WUO2hPpkkgI/AAAAAAAAnqA/-ecx2OilcLQl0HpP_0EHTkwynB9Fj6ftwCLcBGAs/s640/Presentation1.png" title="Block Diagram" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Simple Merge Block Diagram</td></tr>
</tbody></table>
You can use this method on any file really, even SVG files. Hint hint wink wink. You can go from this template file.....<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-povl-oCok04/WUO_TIuNIGI/AAAAAAAAnqU/pTUg2C8U-VE_nIoFbjuwb1jF4HF8a8RTgCLcBGAs/s1600/drawing.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Periodic Table Symbols" border="0" data-original-height="709" data-original-width="709" height="320" src="https://3.bp.blogspot.com/-povl-oCok04/WUO_TIuNIGI/AAAAAAAAnqU/pTUg2C8U-VE_nIoFbjuwb1jF4HF8a8RTgCLcBGAs/s320/drawing.png" title="Periodic Table Symbols" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">SVG Template</td></tr>
</tbody></table>
<br />
to this in a matter of minutes. Just by replacing colour and three text fields.<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-cBs2xClozB0/WUO_XZqIi-I/AAAAAAAAnqY/BBmj227xaK84PdTjNImYKl9pAkEOMtznACLcBGAs/s1600/Elements.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Periodic Table Symbols" border="0" data-original-height="1417" data-original-width="1417" height="320" src="https://3.bp.blogspot.com/-cBs2xClozB0/WUO_XZqIi-I/AAAAAAAAnqY/BBmj227xaK84PdTjNImYKl9pAkEOMtznACLcBGAs/s320/Elements.png" title="Periodic Table Symbols" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Generated Images</td></tr>
</tbody></table>
<br />
I make no guarantee as to how well this works. So my advice is to back things up before using it. Have fun.<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><span style="margin-left: auto; margin-right: auto;"><a href="https://github.com/GrantTrebbin/SimpleMerge"><img border="0" data-original-height="410" data-original-width="1000" height="131" src="https://3.bp.blogspot.com/-zq_0Hv_AfWk/WUO2qFcA9VI/AAAAAAAAnqE/h23X-6LEj8ElU1iyJ3LreX2v2oVagdu_gCLcBGAs/s320/GitHub_Logo.png" width="320" /></a></span></td></tr>
<tr><td class="tr-caption" style="text-align: center;"><a href="https://github.com/GrantTrebbin/SimpleMerge">Get The Code!</a></td></tr>
</tbody></table>
.Grant Trebbinhttp://www.blogger.com/profile/13253301568478517009noreply@blogger.com0Brisbane QLD, Australia-27.4697707 153.02512350000006-28.3721187 151.73423000000005 -26.5674227 154.31601700000007tag:blogger.com,1999:blog-3153881528840143069.post-57858055206265544862017-06-03T16:47:00.000+10:002017-06-04T21:43:23.963+10:00Generating Stippled Images with Stiptacular<div style="text-align: justify;">
A few weeks ago I posted about how to <a href="http://www.grant-trebbin.com/2017/05/generating-seed-points-for-voronoi.html">generate stippled images from regular input images</a>. The code was garbage at the time so I've improved it and posted it for people to use or learn from. I only just remembered why I started this project. I found the <a href="http://wiki.evilmadscientist.com/StippleGen">StippleGen program from EvilMadScientist</a> (EMS) but it was written in the processing development environment which I didn't have much luck with. I thought it'd be great to have a Python version out there as well and along the way added my own tweaks.</div>
<br />
<ul>
<li>Better initial distribution of seed points via a PseudoHilbert Curve</li>
<li>Dithering to make points distribute more evenly</li>
<li>A term that sets how much points are attracted to darker areas</li>
</ul>
<br />
<div style="text-align: justify;">
Since I'm using trying to replicate the work of EMS It thought I'd use their test image of Grace Kelly. Their interface is beautiful and has a few bells and whistles that mine doesn't because I figured that I could do any pre-processing in something like GIMP.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://2.bp.blogspot.com/-q0sTgg9F24E/WTI46aCZmrI/AAAAAAAAngw/8dW07qzqg9gial0xxwtQjn_UAkICxyZcgCLcB/s1600/graceKelly.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Grace Kelly" border="0" data-original-height="834" data-original-width="943" height="283" src="https://2.bp.blogspot.com/-q0sTgg9F24E/WTI46aCZmrI/AAAAAAAAngw/8dW07qzqg9gial0xxwtQjn_UAkICxyZcgCLcB/s320/graceKelly.jpg" title="Grace Kelly" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Grace Kelly test image 943x834</td></tr>
</tbody></table>
<div style="text-align: justify;">
For an initial test I'll use 2000 points with 5 rounds of dithering and 5 rounds without dithering. The simplest way to think of the adjustment parameter is like a contrast setting. In this case it is three. This will cube the value of each pixel and re-scale all the data to a 0-255 range.</div>
<br />
<span style="font-family: "courier new" , "courier" , monospace;">number_of_points = 2000</span><br />
<span style="font-family: "courier new" , "courier" , monospace;">dot_radius = 2.5</span><br />
<span style="font-family: "courier new" , "courier" , monospace;">non_dithering_iterations = 5</span><br />
<span style="font-family: "courier new" , "courier" , monospace;">dithering_iterations = 5</span><br />
<span style="font-family: "courier new" , "courier" , monospace;">adjustment_parameter = 3</span><br />
<br />
Processing the image with the above settings took about 90 seconds and produces the following SVG file.<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-CMNRRdblzpM/WTI5L4fpyDI/AAAAAAAAng8/b4WWIj1v1RonPCI36BqxvRew1l8CECclQCLcB/s1600/stippled_50pc.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Grace Kelly" border="0" data-original-height="1415" data-original-width="1600" height="566" src="https://4.bp.blogspot.com/-CMNRRdblzpM/WTI5L4fpyDI/AAAAAAAAng8/b4WWIj1v1RonPCI36BqxvRew1l8CECclQCLcB/s640/stippled_50pc.png" title="Grace Kelly" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Large Grace Kelly test image - 2000 points</td></tr>
</tbody></table>
<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<div style="text-align: justify;">
To demonstrate another quirk I noticed, take a look at the smaller image below. It contains the same number of dots as the image above. As a matter of fact, it's the exact same image just scaled down. However the dots start to look more like a face. So scale is important. If I were to do an 8 foot print of this for a wall in my house it wouldn't look that good because I couldn't get far enough away from it for the image to emerge. I would need to use more points.</div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-9IRdMPe0C6Q/WTI5B5FxeQI/AAAAAAAAng4/o8TOZEdG2Sg43t7LuSLx08HBHPepeXRgwCLcB/s1600/stippled_05pc.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Grace Kelly" border="0" data-original-height="210" data-original-width="236" src="https://3.bp.blogspot.com/-9IRdMPe0C6Q/WTI5B5FxeQI/AAAAAAAAng4/o8TOZEdG2Sg43t7LuSLx08HBHPepeXRgwCLcB/s1600/stippled_05pc.png" title="Grace Kelly" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Small Grace Kelly test image - 2000 points</td></tr>
</tbody></table>
<div style="text-align: justify;">
The image below uses 30000 points and takes about 25 minutes to generate. Writing this in something like C would help a lot.. Calculating the centroids of the Voronoi regions can be done in parallel to speed things up as well.</div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-LvVjOL21-54/WTJVyDUYd1I/AAAAAAAAnhM/cuGQcx_owDIH22dKOFDxYhzkvyd1Zn-XgCLcB/s1600/stippled_30000.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Grace Kelly" border="0" data-original-height="834" data-original-width="943" height="283" src="https://4.bp.blogspot.com/-LvVjOL21-54/WTJVyDUYd1I/AAAAAAAAnhM/cuGQcx_owDIH22dKOFDxYhzkvyd1Zn-XgCLcB/s320/stippled_30000.png" title="Grace Kelly" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Grace Kelly test image - 30000 points</td></tr>
</tbody></table>
<div style="text-align: justify;">
You may notice that some of the darker regions look a little strange. This is caused by points aligning, as can be seen in the close up below. This can be solved by reducing the number of points, dropping the adjustment parameter so the area isn't so crowded, performing more dithering steps, or just enlarging the source image before processing.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-rlmv2FPpUlQ/WTJV4ejnQWI/AAAAAAAAnhQ/LCdi7fkM_zEZoSeVzWFdAF_JVQlhS4WpwCLcB/s1600/stippled_error.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Stipple Error" border="0" data-original-height="587" data-original-width="584" height="320" src="https://3.bp.blogspot.com/-rlmv2FPpUlQ/WTJV4ejnQWI/AAAAAAAAnhQ/LCdi7fkM_zEZoSeVzWFdAF_JVQlhS4WpwCLcB/s320/stippled_error.png" title="Stipple Error" width="318" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Alignment artefacts</td></tr>
</tbody></table>
.<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><span style="margin-left: auto; margin-right: auto;"><a href="https://github.com/GrantTrebbin/Stiptacular"><img border="0" data-original-height="410" data-original-width="1000" height="131" src="https://1.bp.blogspot.com/-lADcZQNawHg/WTJYHfA4A3I/AAAAAAAAnhY/8cMo6CKZ7xA8wLP3bSs7Y0nv-4yJjJ2lwCLcB/s320/GitHub_Logo.png" width="320" /></a></span></td></tr>
<tr><td class="tr-caption" style="text-align: center;"><a href="https://github.com/GrantTrebbin/Stiptacular">Get the Code!</a></td></tr>
</tbody></table>
You'll also need to install the <a href="https://github.com/GrantTrebbin/PseudoHilbert/releases/tag/v1.0">PseudoHilbert Curve Module</a> for Stiptacular to work. It's a dependency that I'd like to eventually remove, but for now it's needed.<br />
<br />
The posts below are my train of thought while developing this script. It may help if you get a bit lost.<br />
<br />
<a href="http://www.grant-trebbin.com/2017/02/voronoi-stippling.html">Voronoi Stippling</a><br />
<a href="http://www.grant-trebbin.com/2017/02/entry-and-exit-points-for-space-filling.html">Entry and Exit Points for Space Filling Paths on a Grid</a><br />
<a href="http://www.grant-trebbin.com/2017/02/hilbert-curve-generation-with-lookup.html">Hilbert Curve Generation With Lookup Tables</a><br />
<a href="http://www.grant-trebbin.com/2017/03/converting-binary-to-gray-code-with-xor.html">Converting Binary to Gray Code with XOR</a><br />
<a href="http://www.grant-trebbin.com/2017/03/calculating-hilbert-curve-coordinates.html">Calculating Hilbert Curve Coordinates</a><br />
<a href="http://www.grant-trebbin.com/2017/03/pseudo-hilbert-curve-for-arbitrary.html">Pseudo Hilbert Curve for Arbitrary Rectangular Regions - Part 1</a><br />
<a href="http://www.grant-trebbin.com/2017/04/pseudo-hilbert-curve-for-arbitrary.html">Pseudo Hilbert Curve for Arbitrary Rectangular Regions - Part 2</a><br />
<a href="http://www.grant-trebbin.com/2017/04/efficient-centroid-calculation-for.html">Efficient Centroid Calculation for Discrete Areas</a><br />
<a href="http://www.grant-trebbin.com/2017/05/generating-seed-points-for-voronoi.html">Generating Seed Points For Voronoi Stippling</a><br />
<a href="http://www.grant-trebbin.com/2017/06/generating-stippled-images-with.html">Generating Stippled Images with Stiptacular</a><br />
<br />
Here's a picture of a Atlantis during the STS-132 shuttle launch made of 30000 points. To infinity and beyond!<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-e-XiEyHoYOY/WTJVF97MB6I/AAAAAAAAnhI/rlAjFKc6UDMbIqDKno0LAtpfmkaJ1A7LQCLcB/s1600/stippled_05pc.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="STS-132" border="0" data-original-height="685" data-original-width="856" height="512" src="https://3.bp.blogspot.com/-e-XiEyHoYOY/WTJVF97MB6I/AAAAAAAAnhI/rlAjFKc6UDMbIqDKno0LAtpfmkaJ1A7LQCLcB/s640/stippled_05pc.png" title="STS-132" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">STS-132</td></tr>
</tbody></table>
I wish I had the time to do an even deeper dive on this type of problem.Grant Trebbinhttp://www.blogger.com/profile/13253301568478517009noreply@blogger.com0Brisbane QLD, Australia-27.4697707 153.02512350000006-28.3721187 151.73423000000005 -26.5674227 154.31601700000007tag:blogger.com,1999:blog-3153881528840143069.post-4019763985051731652017-05-20T20:25:00.000+10:002017-05-20T20:25:20.940+10:00Linux Text To Speech with Saved Audio<div style="text-align: justify;">
In my last blog post I described a procedure to <a href="http://www.grant-trebbin.com/2017/05/testing-all-pins-on-lock-box-with.html">find a forgotton PIN for 10 digit mechanical lock boxes</a> where you enter a specific sequence of button presses to efficiently test all the combinations. The generated sequence was supplied in the form of a text file, and although this works, it's a little cumbersome moving your eyes between the buttons and paper all the time. It occurred to me that this would be a lot easier if the numbers were read to me. I then imagined how easy it would be if I had a pair of headphones and the instruction in an audio file on my phone. This seemed like the perfect application for a text to speech application and Linux.</div>
<br />
<div style="text-align: justify;">
After a little bit of research I decided to use the eSpeak speech synthesizer. It has many options for different voices for different languages and countries and allows quite a bit of customisation of the the way the text is read.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
The command below that converts the text in "lockbox.txt" to audio in "lockbox.wav" uses the english voice (-ven), pronounces capital letters in a certain way (-k20), leaves a certain gap between words (-g4), reads back at a certain words per minutes (-s90), and has a certain pitch (-p29). It's that easy!</div>
<br />
<span style="color: #38761d; font-family: "courier new" , "courier" , monospace;">espeak -ven -k20 -g4 -s90 -p20 -f lockbox.txt -w lockbox.wav</span><br />
<br />
<div style="text-align: justify;">
Before processing the file I made some slight alterations to it by replacing some of the commands in the lock box opening sequence. Originally the commands were zero thought nine, open, and clear. I replaced open with test as it was only one syllable and easier to hear. It's also important to leave spaces between numbers otherwise it will read 11 as "eleven" instead of "one one".</div>
<br />
<div style="text-align: justify;">
Here is the <a href="https://drive.google.com/file/d/0B5Hb04O3hlQSVEd5c1F6Q0pzRUk/view?usp=sharing">instructional WAV file converted to an MP3</a>. It goes for 30 minutes or so and with a little bit of practice you should be able to follow along at that speed. If you can't, that's fine, just slow the speed down in your music player. If you screw up just go back 15 or twenty seconds to catch up.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
For the YouTube fans out there, here is another version. It might possibly be the most boring and monotonous video on YouTube. That's my speciality though :-)<br />
<br /></div>
<center>
<iframe allowfullscreen="" frameborder="0" height="315" src="https://www.youtube.com/embed/lWvLe-xa_hA" width="560"></iframe></center>
<br />
<div style="text-align: justify;">
To be serious though I'd like to try eSpeak on a Raspberry Pi. I think it'd be great to read out status updates and events. Compared to some of the other synthesized voices I've heard it's actually pretty good.</div>
Grant Trebbinhttp://www.blogger.com/profile/13253301568478517009noreply@blogger.com0Brisbane QLD, Australia-27.4697707 153.02512350000006-28.3721187 151.73423000000005 -26.5674227 154.31601700000007tag:blogger.com,1999:blog-3153881528840143069.post-38968398637917903702017-05-19T22:22:00.000+10:002017-05-29T20:31:55.312+10:00Testing All The PINs On A Lock Box With A Forgotten Code<div style="text-align: justify;">
A long time ago I did a blog post on <a href="http://www.grant-trebbin.com/2012/04/mathematics-of-security-combinations.html">PIN coded lock boxes</a> that you put on your house to hold a spare set of keys. Their main function is to give easy access for emergency services in case they need keys to get in if an elderly relative has a fall and can't get up. The point of my post was to demonstrate that although they have 10 buttons, look secure, and you can choose how many digits are in the PIN, they only really have 1024 PIN combinations. This is because the numbers can only be used once in each PIN.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-HlvIluB2a-I/WR7KmYvAvfI/AAAAAAAAnGA/c1wyz0zkr-k1GgcLYbKzgjCWrt4FRnZWwCLcB/s1600/LockBox.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Lock" border="0" height="320" src="https://3.bp.blogspot.com/-HlvIluB2a-I/WR7KmYvAvfI/AAAAAAAAnGA/c1wyz0zkr-k1GgcLYbKzgjCWrt4FRnZWwCLcB/s320/LockBox.jpg" title="Lock" width="192" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">PIN coded key lock box</td></tr>
</tbody></table>
<div style="text-align: justify;">
The math is explained in my initial blog post but the results are below. I opined it would take about 4 hours to try all the combinations, and in this case it would require pressing the open button 1024 times, the clear button 1024 times, and pressing digits (0*1 + 1*10 + 2*45 + 3*120 + 4*210 + 5*252 + 6*210 + 7*120 + 8*45 + 9*10 + 10*1) = 5120 times. In total there are 7168 button presses. That works out at about one button press every 2 seconds.</div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://2.bp.blogspot.com/-lyFEdtyxnls/WR7Ksj2hQCI/AAAAAAAAnGE/F1_JxGZkhNAzfkOVVJL-Set_aa05DYBGACLcB/s1600/CombinationTable.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Table" border="0" src="https://2.bp.blogspot.com/-lyFEdtyxnls/WR7Ksj2hQCI/AAAAAAAAnGE/F1_JxGZkhNAzfkOVVJL-Set_aa05DYBGACLcB/s1600/CombinationTable.png" title="Table" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Number of PINs vs PIN length</td></tr>
</tbody></table>
<div style="text-align: justify;">
At some point in the 5 years since I first wrote about these locks (the time flies doesn't it) it occurred to me that I was being inefficient. Testing if the box opens doesn't clear the current code. So I can test multiple PINs at once by just chaining them together. It's similar to the <a href="https://en.wikipedia.org/wiki/De_Bruijn_sequence">De Bruijn sequence</a>, a mathematical tool that can be used to brute force another type of PIN. In this case however you have to reset the lock after a few buttons are pressed. To illustrate the process I'm trying to explain, imagine that the clear button has been pressed and I then enter the numbers 0 through 9, testing if the lock will open in between numbers. I've actually just tested the codes (Null) (0) (01) (012) (0123) (01234) (012345) (0123456) (01234567) (012345678) (0123456789). I've tested 11 codes with one press of the clear button, 11 presses of the open button, and just 10 digit presses. The whole process won't be this efficient but it'll be better than nothing.</div>
<br />
<div style="text-align: justify;">
But where do we start? In a perfect world, you may see by looking at the chart below and table above, that the best we can do is 1 sequence testing PINs of length 0-10, followed by 9 sequences testing PINs of length 1-9, 35 sequences testing PINs of length 2-8, 75 sequences testing PINs of length 3-7, 90 sequences testing PINs of length 4-6, and 42 sequences testing PINs of length 5.</div>
<br />
<div style="text-align: justify;">
This will still result in 1024 presses of the test button, only 252 presses of the clear button, and (1*10)+(9*9)+(35*8)+(75*7)+(90*6)+(42*5) = 1646 presses of the number buttons. For a new total of 2922 button presses, or about 41% of the original estimate.</div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-6bq1h2Zv4HA/WR7KxEYKztI/AAAAAAAAnGI/UfJC1FalrTceByhX1FoeMRTfH6zVoHjcQCLcB/s1600/PINDistribution.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Graph" border="0" height="404" src="https://4.bp.blogspot.com/-6bq1h2Zv4HA/WR7KxEYKztI/AAAAAAAAnGI/UfJC1FalrTceByhX1FoeMRTfH6zVoHjcQCLcB/s640/PINDistribution.png" title="Graph" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Distribution of PIN lengths</td></tr>
</tbody></table>
<div style="text-align: justify;">
There's no guarantee that these sequences exist though and I had no deep understanding of how to create them, so I tried the first thing that came to mind and got lucky.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
First, generate all possible combinations for each PIN length and then sort the numbers in each PIN. Then sort the PINs for each length comparing them element by element. Start in the middle with the PINs of length 5 as there are more of these than the others. Then take the PINs of length 4 and go through them one by one from the start and place them to the left of first 5 digit PIN that could follow it. For instance (1, 5, 6, 7) might go to the left of (1, 2, 5, 6, 7) as only a 2 would have to be pressed to get to the 5 digit PIN. Do the same for the 6 digit PINs and place them on the right of the 5 digits. In this case (1, 2, 3, 5, 6, 7) might go to the right of (1, 2, 5, 6, 7) as only a 3 needs to be pressed. Repeat this left right procedure until all PINs are processed. It will look like a mess, but if you sort the sequences by length you will get a spreadsheet that looks like the one below (zoomed and rotated to fit). Look familiar? It's reflects the distribution graph above, and it shows that the sequences can be generated.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-xjOutodWmZU/WR7K1QUCA-I/AAAAAAAAnGM/URHyH7khlcMxYBy1z2df-IQfgfixEgPJgCLcB/s1600/Spreadsheet.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Spreadsheet" border="0" height="114" src="https://4.bp.blogspot.com/-xjOutodWmZU/WR7K1QUCA-I/AAAAAAAAnGM/URHyH7khlcMxYBy1z2df-IQfgfixEgPJgCLcB/s640/Spreadsheet.png" title="Spreadsheet" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Rotated spreadsheet of the sequences</td></tr>
</tbody></table>
<div style="text-align: justify;">
I've placed my code in a <a href="https://gist.github.com/GrantTrebbin/c3997bb2f07f897af25156e06ba0675c">Github Gist</a> for you to generate your own sequences in case there are a different number of buttons on your lock. If you have a lock with 10 buttons I've already generated the <a href="https://drive.google.com/file/d/0B5Hb04O3hlQSVnRDY2IwbHpVdE0/view?usp=sharing">file</a> for you. It looks a little different from the output of the Python file because I've done some some find and replace operations in Notepad++. I've used the word test instead of unlock as well.</div>
<div style="text-align: justify;">
<br />
<u>Update1</u> There is a MP3 file of the instructions in this blog post, <a href="http://www.grant-trebbin.com/2017/05/linux-text-to-speech-with-saved-audio.html">Linux Text To Speech With Saved Audio</a>.<br />
<br />
<u>Update2</u> I've sorted the sequences by how often the 4 digit PINs appear in the <a href="https://en.wikipedia.org/wiki/RockYou">2009 Rock You data breach</a>. There are two new files that cover the all the PINs. One of them has the sequences sorted by the 4 digit PIN popularity but still groups the sequences lengths, while the other sorts by PIN popularity only. An Excel file with all this data is also included so you can sort the data however you want. The associated files are in this <a href="https://drive.google.com/drive/folders/0B5Hb04O3hlQSUGlFVUpNUXVjcFU?usp=sharing">Google drive folder</a>. It could be argued that Rock You users and the users of lock boxes are a completely different demographic, and it's true. However, their users will exhibit similar behaviours like using birthdays and years that make the effort worthwhile. Although the instructions for the lock suggest selecting a PIN between 4 and 7 digits long, 4 digit PINs have been targeted as they are what people tend to think of when you mention PINs, even though 5 digit PINS are more secure.<br />
<br /></div>
<div style="text-align: justify;">
So what about those locks you see in banks and other offices that have 14 buttons. I've done the maths so you don't have to, but they can be broken with 50316 button presses. So 4 extra buttons buys you an increase in security by a factor of about 17. Not that it matters, whenever I've seen these used, people aren't too discreet about entering the PIN.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-Ux_8vBAI5gs/WR7LMf6dfUI/AAAAAAAAnGQ/fXxHWAfbKIMYTTgFuQ8P1PV4-Z4NDggrACLcB/s1600/combination-door-lock.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Door Lock" border="0" height="320" src="https://3.bp.blogspot.com/-Ux_8vBAI5gs/WR7LMf6dfUI/AAAAAAAAnGQ/fXxHWAfbKIMYTTgFuQ8P1PV4-Z4NDggrACLcB/s320/combination-door-lock.jpg" title="Door Lock" width="219" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">PIN Door Lock</td></tr>
</tbody></table>
<br />Grant Trebbinhttp://www.blogger.com/profile/13253301568478517009noreply@blogger.com0Brisbane QLD, Australia-27.4697707 153.02512350000006-28.3721187 151.73423000000005 -26.5674227 154.31601700000007tag:blogger.com,1999:blog-3153881528840143069.post-11970165909391628182017-05-05T23:47:00.000+10:002017-05-05T23:47:04.647+10:00Generating Seed Points For Voronoi Stippling<div style="text-align: justify;">
I've been working on a way to generate an initial distribution of seed points for a <a href="http://www.grant-trebbin.com/2017/02/voronoi-stippling.html">Voronoi stippling</a> program that I played with a while ago. The problem is that for the final image to look good you really need a lot of points, and when you have a lot of points they are very slow to converge to a solution. The process I used in the past is to generate a few points and allow them to be processed, split them in two, process them and so on and so on. Each time the number of points is doubled and the solution is eventually found but it's still not great. An improvement I thought I could try is to linearize the image via a Pseudo-Hilbert (PH) curve and apply a rolling threshold to the data and place points at locations where the counter rolls over. You may see a major optimisation that I've know all along but haven't implemented. I'll give you a clue, it a PH curve really necessary? Find out at the end of the post.😉</div>
<br />
<div style="text-align: justify;">
The implementation of the threshold is a little abstract so I'll just explain the general concept. First of all we always work on an inverse grey scale version of the image as we are distributing black dots and the background is white. Imagine that the sum of all the pixels in the image is equal to 1,000,000 and you want 2000 points. This means that each point represents 500. So as you travel along the PH curve you add the pixel values and every time you accumulate another 500 place a point.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
The points generated from this process are then iterated on via the Voronoi stippling process to produce a result. Another small feature I've added is a dithering step. For a certain number of iterations a random displacement is added to each point. This can be seen in the GIF below as a jiggling of the points. What is the purpose of this? Imagine a jar of jelly beans that won't quite close. What do you do? You pick the jar up and shake it to settle the contents. That's what we're doing here. What you end up with is a number of points that when randomly perturbed, return to their original position. i.e. a stable arrangement.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
The results in the GIF aren't that great. The main reason for this is that I've kept the features large so you can see what's happening. If you really wanted to process this image the best way to do it is to increase the size of the image and then process it. When the calculated Voronoi regions are small and they only contain a few pixels, due to quantization issues the points won't move as the centroid calculations will always yield the same result. So if you notice herding of points in the final image try enlarging the image and reprocessing it.</div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-v4td3x48KFQ/WQxkCD1rbAI/AAAAAAAAm9U/ZeLqd046ejo9NsVEhossM65HuxG1kXSLQCLcB/s1600/HilbertStippleTest.gif" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="472" src="https://4.bp.blogspot.com/-v4td3x48KFQ/WQxkCD1rbAI/AAAAAAAAm9U/ZeLqd046ejo9NsVEhossM65HuxG1kXSLQCLcB/s640/HilbertStippleTest.gif" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Distribution of Seed Stippling Points on a Pseudo-Hilbert Curve</td></tr>
</tbody></table>
To test the algorithm I've used an image of a plant from the paper I'm working from. <a href="https://www.cs.ubc.ca/labs/imager/tr/2002/secord2002b/secord.2002b.pdf">Weighted Voronoi Stippling, by Adrian Secord</a>. If this link becomes dead, contact me, I have a copy of the paper.<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-xcA5HN9kImI/WQxg8HBlcyI/AAAAAAAAm80/scvtAw_ah6ExqfJpOpGMt6IVFYjlo555gCLcB/s1600/plant4h.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="376" src="https://3.bp.blogspot.com/-xcA5HN9kImI/WQxg8HBlcyI/AAAAAAAAm80/scvtAw_ah6ExqfJpOpGMt6IVFYjlo555gCLcB/s400/plant4h.png" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Test Image Used in Adrian Secord's Paper</td></tr>
</tbody></table>
<div style="text-align: justify;">
In the image below I've started modestly with 4000 points to test that everything is working properly, and as you can see, everything is working. On closer inspection though, you can see that the dynamic range, for want of a better term, of the image has been reduced. In other words, the areas that are meant to be dark aren't as dark as they're meant to be, and in comparison, the areas that are meant to be light aren't as light.</div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-JjqVkv46D8c/WQxgt8aYloI/AAAAAAAAm8s/_P6Y77r28aYckbfYiAkASPf-8UolI4PRQCLcB/s1600/4000_r1p0_d2p0.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="301" src="https://1.bp.blogspot.com/-JjqVkv46D8c/WQxgt8aYloI/AAAAAAAAm8s/_P6Y77r28aYckbfYiAkASPf-8UolI4PRQCLcB/s320/4000_r1p0_d2p0.jpg" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">4000 points - power 1</td></tr>
</tbody></table>
<div style="text-align: justify;">
The dynamic range problem can be solved by pre-compensating the image. Specifically raising each pixel to a power or exponent. In the image below the value of each pixel has been squared before processing. I've referred to this as a power parameter. I've re-scaled the resulting data back to a range of 0-255 just for consistency but it's really not required.</div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-Tq0rXbTGW8M/WQxgy8ZofWI/AAAAAAAAm8w/JfELokIPVJg7QZAiXy-xTQAguXr-BSinQCLcB/s1600/4000_r2p0_d2p0.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="301" src="https://3.bp.blogspot.com/-Tq0rXbTGW8M/WQxgy8ZofWI/AAAAAAAAm8w/JfELokIPVJg7QZAiXy-xTQAguXr-BSinQCLcB/s320/4000_r2p0_d2p0.jpg" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">4000 points - power 2</td></tr>
</tbody></table>
<span style="text-align: justify;">In the next image the number of points has been doubled and the power parameter has been pulled back slightly to 1.9 and things are starting to look even better.</span><br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://2.bp.blogspot.com/-wn4Wql5Ablw/WQxhWVAmAnI/AAAAAAAAm84/shTR75IZDGQZiViMFIbT5HGDKqrdcGwUACLcB/s1600/8000_r1p9_d1p5.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="301" src="https://2.bp.blogspot.com/-wn4Wql5Ablw/WQxhWVAmAnI/AAAAAAAAm84/shTR75IZDGQZiViMFIbT5HGDKqrdcGwUACLcB/s320/8000_r1p9_d1p5.jpg" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">8000 points - power 1.9</td></tr>
</tbody></table>
<span style="text-align: justify;">Let's step things up once again and go for 20000 thousand points to match the example in the paper. I've also pulled back the power parameter to 1.6. Why? It's subjective. I think it looks better.</span><br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-Iae1TSXFeo4/WQxhikiSLYI/AAAAAAAAm88/rrnNraSYWOMZWfG4pk_Uae9MYb_D5lrAACLcB/s1600/20000_r1p6_d1p2.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="602" src="https://3.bp.blogspot.com/-Iae1TSXFeo4/WQxhikiSLYI/AAAAAAAAm88/rrnNraSYWOMZWfG4pk_Uae9MYb_D5lrAACLcB/s640/20000_r1p6_d1p2.jpg" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">20000 points - power 1.6</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
I think that looks pretty spectacular. Of course I've had to resize the image and scale it down a bit so downloading this page isn't a 100 MB exercise, so there's a little bit of quality degradation, but the original vector files are even better.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
The point of this post however is to discuss the PH curve approximation for the seed points and how close it gets us to the final image. What does the initial distribution of seed points look like before any processing?</div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://2.bp.blogspot.com/-I65S9zfE2bo/WQxhwvCmDkI/AAAAAAAAm9A/MS6xonBkzaAr-MbN4IOJUXrZ3lsRXJdhwCLcB/s1600/square20000_r1p6_d1p2.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="602" src="https://2.bp.blogspot.com/-I65S9zfE2bo/WQxhwvCmDkI/AAAAAAAAm9A/MS6xonBkzaAr-MbN4IOJUXrZ3lsRXJdhwCLcB/s640/square20000_r1p6_d1p2.jpg" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">20000 points - power 1.6 - no processing</td></tr>
</tbody></table>
<div style="text-align: justify;">
The structure is immediately visible, but there is a fuzziness to the image. This is more apparent when looking at an enlarged section. The points are distributed on a grid so you will see more lines and square corners in the arrangement.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-PatkKr5R60g/WQxjlxB-R6I/AAAAAAAAm9M/QnoCN5TaiNAcF9M-IQQra4hAB82HsqHigCLcB/s1600/square20000_r1p6_d1p2_1000x1000.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="640" src="https://1.bp.blogspot.com/-PatkKr5R60g/WQxjlxB-R6I/AAAAAAAAm9M/QnoCN5TaiNAcF9M-IQQra4hAB82HsqHigCLcB/s640/square20000_r1p6_d1p2_1000x1000.png" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Close Up Section of Seed Point Distribution</td></tr>
</tbody></table>
<div style="text-align: justify;">
So what happens after processing? The points are allowed to find their own space and curved features start to appear. I can't explain the exact reasoning but in sections the points form curved lines running in multiple directions. If you can't see what I'm talking about, go and have a look at something called a <a href="https://en.wikipedia.org/wiki/Fermat%27s_spiral">Fermat Spira</a>l (also a way to distribute points to evenly cover an area) and you'll see what I mean. In all things just look more pleasing to the eye.</div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://2.bp.blogspot.com/-Zv6htEDiaTM/WQxjtXItKpI/AAAAAAAAm9Q/lSRjyqVWXbcVlz073bs4BNRMXzs4Scf7ACLcB/s1600/20000_r1p6_d1p2_1000x1000.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="640" src="https://2.bp.blogspot.com/-Zv6htEDiaTM/WQxjtXItKpI/AAAAAAAAm9Q/lSRjyqVWXbcVlz073bs4BNRMXzs4Scf7ACLcB/s640/20000_r1p6_d1p2_1000x1000.png" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Close Up Section of Points After Processing</td></tr>
</tbody></table>
<div style="text-align: justify;">
I'm sorry but I'm not releasing the code on this one just yet. Why? Because it's terrible. There are very few comments and a lot of sections where code has been commented out. I know the theory is to develop in public and let the code be scrutinised, but I try to make a program so that it's not only functional but it also explains the concept I'm trying to describe to the user. At this point I think it would just confuse people.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
It's also hard to develop things cleanly when you don't exactly know where they are going to go. Unlike a lot of programming where you have a clearly defined goal and a general way to get there. I start not usually knowing either. Think of this type of coding as a science experiment. I'll try different things and see what the results are, change things until I get what I want and then go back and clean up a section and lock it down.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
I will release this soon though. There are couple things to fix but it's mostly there. If for some reason I don't post the code, let me know and I'll help you out.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
Here is the optimization I didn't implement. You don't need a PH curve. Just add a white border to the source image to make it a square so that the length of a side is a power of 2 and then use an actual Hilbert curve and crop the result. They are way more efficient to generate than a PH curve. I did it this way because I was interested in the problem of covering arbitrary rectangular regions with a curve. As this blog is a labour of love I reserve the right to go off on the occasional tangent to satisfy my curiosity.</div>
Grant Trebbinhttp://www.blogger.com/profile/13253301568478517009noreply@blogger.com0Brisbane QLD, Australia-27.4697707 153.02512350000006-28.3721187 151.73423000000005 -26.5674227 154.31601700000007tag:blogger.com,1999:blog-3153881528840143069.post-74294709805861250242017-04-21T23:10:00.003+10:002017-04-21T23:10:55.708+10:00Efficient Centroid Calculation for Discrete Areas<div style="text-align: justify;">
A project I'm working on requires the repeated calculation of weighted centroids for arbitrary regions in an image. Calculation of centroids is fairly straight forward but computationally expensive. To calculate the x and y coordinates you first need to calculate three other values, the denominator, x-numerator and y-numerator. The denominator is simply equal to the sum of all the values in the region, the x-numerator is the sum of all the values in the region multiplied by their x coordinate, and the y-numerator is the sum of all the values in the region multiplied by their y coordinate. From these values the x coordinate of the centroid is equal to the the x-numerator divided by the denominator likewise for the y coordinate of the centroid. </div>
<br />
<div style="text-align: justify;">
You can see from this description that there are a lot of time consuming multiplication operations to perform for each area that you want to calculate the centroid for. As it turns out though, you can perform two cumulative summations along the rows of the input data as a first step, store this and then perform the centroid calculation by only accessing values at the boundary of the region. For reasons I'll explain later a column of zeros with x coordinate -1 is added to the start of the data. A cumulative summation is performed along each row to obtain $$$P$$$. A cumulative summation along each row of $$$P$$$ is performed to generate $$$Q$$$ The following equations describe the process. Before we get started, the <a href="https://drive.google.com/file/d/0B5Hb04O3hlQSYXhEei1XVG9TaUU/view?usp=sharing">derivation of these equations can be found in this small article</a> I wrote.</div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-11_4L3SroxI/WPnrwVen9YI/AAAAAAAAm1Y/zyvbrnpbLFo--DMfu0UbfDd8rsIKJvjhwCLcB/s1600/CentroidEquations.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Equations" border="0" height="384" src="https://1.bp.blogspot.com/-11_4L3SroxI/WPnrwVen9YI/AAAAAAAAm1Y/zyvbrnpbLFo--DMfu0UbfDd8rsIKJvjhwCLcB/s640/CentroidEquations.png" title="Equations" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Centroid Calculations</td></tr>
</tbody></table>
<div style="text-align: justify;">
It may not be immediately obvious what these mean so I'll give a quick explanation. First of all each of the above calculations are done row by row and added together. This is what the summation symbol over $$$y$$$ represents. For the denominator the value to be summed is the difference between two values on a row of $$$P$$$. For the y-numerator the calculation is the same as the denominator but each row is multiplied by the y coordinate. The calculation of the x-numerator is a little different. It's similar in that values of $$$P$$$ at the boundary are subtracted and multiplied by $$$x+1$$$ but the additional step of subtracting the difference of the values of $$$Q$$$ at the boundaries is now added. Maybe an example will help.</div>
<div style="text-align: justify;">
<br /></div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-kz2H6Q80TmM/WPnr0Adh4vI/AAAAAAAAm1c/QtszUU5WxPc6FSCnYTPXcsfJddOT_7EBQCLcB/s1600/CentroidExample.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Spreadsheet" border="0" height="454" src="https://4.bp.blogspot.com/-kz2H6Q80TmM/WPnr0Adh4vI/AAAAAAAAm1c/QtszUU5WxPc6FSCnYTPXcsfJddOT_7EBQCLcB/s640/CentroidExample.png" title="Spreadsheet" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Example Calculation</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
In the first data set on the top left an area is marked green. The centroid of this region is to be found. A column of zeros is added to the start of the data. This is seen in the data set on the top right. These are added because when performing the operation in software you end up accessing array outside of their bounds.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
Typically when calculating centroids each green cell would have to be accessed for each calculation. However when using the new method described above only the cells in blue are accessed. You may also notice that the width of these doesn't change the number of operations. The complexity of the calculation is only dependant on the height of the region. I've <a href="https://drive.google.com/file/d/0B5Hb04O3hlQSaVB5R1l3eXc5Slk/view?usp=sharing">included this spreadsheet</a> for you to play around with and get a better understanding of the process.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
One last this to note is that the addition of the column of zeros while maintaining the original $$$x$$$ indices is silly as it creates a column with an index of negative one. This is where the adjusted x index comes in. Using this and the following adjusted equations allow the calculation to be performed easily on computers.</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://4.bp.blogspot.com/-H3q81VMzGQQ/WPn_7x0EfiI/AAAAAAAAm18/6oWxmcLphc8VTBAwuLav0ZK2TP-H9Y1bwCLcB/s1600/AdjustedCentroidEquations.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img alt="Equations" border="0" height="334" src="https://4.bp.blogspot.com/-H3q81VMzGQQ/WPn_7x0EfiI/AAAAAAAAm18/6oWxmcLphc8VTBAwuLav0ZK2TP-H9Y1bwCLcB/s640/AdjustedCentroidEquations.png" title="Equations" width="640" /></a></div>
<br />
<div style="text-align: justify;">
Let's for example calculate the centroid of the green section on only row 5. Its $$$x$$$ bounds are $$$x_1=4$$$ and $$$x_2=7$$$, but in the above equations $$$P$$$ and $$$Q$$$ are accessed via the adjusted $$$x$$$ index at 4 and 8 (8 because of +1 on the upper index). This means the denominator is equal to $$$(356-170) = 186$$$, the y-numerator is equal to $$$5(356-170)=930$$$, and the x-numerator is equal to $$$(8 \times 356-4 \times 170)-(1560-420)=1028$$$. This leads to centroid coordinates of (5.526, 5). This is what you would expect as it's a single row the y value is obviously 5 and the x value is a little to the right of centre due to the increasing trend in the numbers. The centroid coordinates calculated are given in the original x index to allow accessing the original data.</div>
Grant Trebbinhttp://www.blogger.com/profile/13253301568478517009noreply@blogger.com0Brisbane QLD, Australia-27.4697707 153.02512350000006-28.3721187 151.73423000000005 -26.5674227 154.31601700000007tag:blogger.com,1999:blog-3153881528840143069.post-17673579987687140152017-04-10T21:20:00.000+10:002017-04-10T21:20:05.335+10:00Pseudo Hilbert Curve for Arbitrary Rectangular Regions - Part 2<div style="text-align: justify;">
I fixed the problems mentioned in <a href="http://www.grant-trebbin.com/2017/03/pseudo-hilbert-curve-for-arbitrary.html">my last blog post about Pseudo Hilbert curves</a>. When both side of a block are of length divisible by 4 the block is divided into 2x2 sub-blocks. Each of these blocks are scanned in an appropriate manner to maintain the flow of the parent block. I won't show all the examples from the paper I'm working from, but the python module I wrote does generate all the example curves. I can see room for improvement in places but I'm happy with its operation and how fast it works. After all, perfect is the enemy of good.</div>
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://1.bp.blogspot.com/-90B7CWiRwAI/WOtnsAnZzuI/AAAAAAAAmwc/H6LPC_htLGI4Mn3hdXSFnLiS7eC68AQMgCLcB/s1600/125x88mixed.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="478" src="https://1.bp.blogspot.com/-90B7CWiRwAI/WOtnsAnZzuI/AAAAAAAAmwc/H6LPC_htLGI4Mn3hdXSFnLiS7eC68AQMgCLcB/s640/125x88mixed.png" width="640" /></a></div>
<br />
<div style="text-align: justify;">
The module allows you to specify an rectangular region. It will then create an in order list of the (x,y) coordinates of the curve and it will create a "2D" list of the length along the curve. I have some plans for this that I hope workout.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><span style="margin-left: auto; margin-right: auto;"><a href="https://github.com/GrantTrebbin/PseudoHilbert/releases/tag/v1.0"><img border="0" height="131" src="https://4.bp.blogspot.com/-wf-JMJGuFdU/WOto30AArZI/AAAAAAAAmwo/sAgpxlkRodE6sSQ-iuuZ0RE2munYaODtwCLcB/s320/GitHub_Logo.png" width="320" /></a></span></td></tr>
<tr><td class="tr-caption" style="text-align: center;"><a href="https://github.com/GrantTrebbin/PseudoHilbert/releases/tag/v1.0">Get the Code!</a></td></tr>
</tbody></table>
<br />Grant Trebbinhttp://www.blogger.com/profile/13253301568478517009noreply@blogger.com2Brisbane QLD, Australia-27.4697707 153.02512350000006-28.3721187 151.73423000000005 -26.5674227 154.31601700000007tag:blogger.com,1999:blog-3153881528840143069.post-12929899264093539662017-03-30T23:48:00.000+10:002017-03-31T11:45:04.570+10:00Pseudo Hilbert Curve for Arbitrary Rectangular Regions - Part 1<div style="text-align: justify;">
It's been a bit longer than usual so I thought that an update was in order. I've been working on implementing an algorithm that generates Hilbert curves for arbitrary rectangular regions and I've been having issues. The paper that describes the algorithm is </div>
<br />
<a href="https://drive.google.com/file/d/0B5Hb04O3hlQSdl9pTHZCSkpVQUE/view?usp=sharing">Zhang, Kamata, Ueshige "<i>A Pseudo-Hilbert Scan for Arbitrarily-Sized Arrays</i>"</a><br />
<br />
<div style="text-align: justify;">
The problems I've been having aren't so much related to my understanding of the problem, it's coming up with a understandable, fast piece of code to generate the curve (while finding time for sleep and work). I'm using python so I could increase the speed by going to C for some parts, but I've worked on my implementation until it generates a curve for a 3000 by 2000 area in about 20 seconds. I think that's a reasonable speed. The plan was to hold off on this post until I'd solved it. It forces me to work and sets a deadline to meet. The code reached a point last night that I was happy with and I was ready to post and then I compared my results with the curves in the paper. Guess what, they don't match. I know why and I'll get to that later but first an explanation of the algorithm.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
The first step is to recursively divide the region vertically and horizontally. In the small example below the region is divided into 4 blocks vertically and 4 blocks horizontally. There will always be an equal number of blocks vertically and horizontally and it will be a power of two. These blocks determine the general direction of the curve as they can be easily traversed by a Hilbert curve. The division algorithm also ensures that the dimensions of each block in all but the bottom and left rows will be a power of two.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://2.bp.blogspot.com/-XSShGiPUas0/WNz7s_cF5_I/AAAAAAAAmpQ/rQXDu5MIjGcRoHXUTAJvNFzeuKx5Vf7QQCLcB/s1600/Demo.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Pseudo Hilbert Curve" border="0" height="298" src="https://2.bp.blogspot.com/-XSShGiPUas0/WNz7s_cF5_I/AAAAAAAAmpQ/rQXDu5MIjGcRoHXUTAJvNFzeuKx5Vf7QQCLcB/s320/Demo.png" title="Pseudo Hilbert Curve" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Partition a 17 x 15 Region into Blocks</td></tr>
</tbody></table>
<div style="text-align: justify;">
The next step is to determine a scanning method for each block. The way the sides are divided makes this step easier. Depending on the oddness or evenness of the each of the dimensions some block scanning methods are determined by a simple lookup process. Others are a bit more complicated.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://2.bp.blogspot.com/-jG-mRfv76Kk/WN0K01tx-YI/AAAAAAAAmp4/Wv3gEAEvkJYhUPRL6c2eYMBlGkp7d3ydgCLcB/s1600/ScanningMethods.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Hilbert scanning methods" border="0" height="241" src="https://2.bp.blogspot.com/-jG-mRfv76Kk/WN0K01tx-YI/AAAAAAAAmp4/Wv3gEAEvkJYhUPRL6c2eYMBlGkp7d3ydgCLcB/s400/ScanningMethods.png" title="Hilbert scanning methods" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Scanning methods</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
Once you know the size of the blocks, their location, and their scanning method, the curve can be easily generated.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
Here's where things went wrong. My curves match the curves in the paper for some sections but not others. Bellow are a couple example of my curve vs the one from the paper and an overlay to show where they match and where they differ.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://2.bp.blogspot.com/-7H2xEVoyV3E/WNz7zBIyYjI/AAAAAAAAmpU/kthBQ-AfNGsptc3lIhXCnkkUezcDOjKdACLcB/s1600/123x97_2.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Pseudo Hilbert Curve" border="0" height="514" src="https://2.bp.blogspot.com/-7H2xEVoyV3E/WNz7zBIyYjI/AAAAAAAAmpU/kthBQ-AfNGsptc3lIhXCnkkUezcDOjKdACLcB/s640/123x97_2.png" title="Pseudo Hilbert Curve" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">My version of a 123 x 97 curve</td></tr>
</tbody></table>
.<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-CN68inEOYi4/WNz8Fj_p_8I/AAAAAAAAmpY/JTknFXYB5K0MHk9vjKGLFrkdEC-D3UxWwCLcB/s1600/123x97.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Pseudo Hilbert Curve" border="0" height="523" src="https://4.bp.blogspot.com/-CN68inEOYi4/WNz8Fj_p_8I/AAAAAAAAmpY/JTknFXYB5K0MHk9vjKGLFrkdEC-D3UxWwCLcB/s640/123x97.png" title="Pseudo Hilbert Curve" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">The 123 x 97 curve in the paper</td></tr>
</tbody></table>
.<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://2.bp.blogspot.com/-MP6fEeL9PBY/WNz8OyzUxxI/AAAAAAAAmpc/zrr2LQkGxKAlPb22pP92hFSwoyEQe0fSACLcB/s1600/123x97_3.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Pseudo Hilbert Curve" border="0" height="530" src="https://2.bp.blogspot.com/-MP6fEeL9PBY/WNz8OyzUxxI/AAAAAAAAmpc/zrr2LQkGxKAlPb22pP92hFSwoyEQe0fSACLcB/s640/123x97_3.png" title="Pseudo Hilbert Curve" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Overlay of the two curves to see where they differ</td></tr>
</tbody></table>
.<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-v28ebb09Dys/WNz8Zn00S3I/AAAAAAAAmpg/cW5LHBuPzpE0f4iTETvx1CIF8_vabX3WQCLcB/s1600/125x88_2.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Pseudo Hilbert Curve" border="0" height="460" src="https://3.bp.blogspot.com/-v28ebb09Dys/WNz8Zn00S3I/AAAAAAAAmpg/cW5LHBuPzpE0f4iTETvx1CIF8_vabX3WQCLcB/s640/125x88_2.png" title="Pseudo Hilbert Curve" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">My version of the 125 x 88 curve</td></tr>
</tbody></table>
.<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://2.bp.blogspot.com/-O2QaJHnVNZo/WNz8fc3HYsI/AAAAAAAAmpk/S20hTWToy6g_O5FCrhUJdG4X5jE7T2vbgCLcB/s1600/125x88.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Pseudo Hilbert Curve" border="0" height="478" src="https://2.bp.blogspot.com/-O2QaJHnVNZo/WNz8fc3HYsI/AAAAAAAAmpk/S20hTWToy6g_O5FCrhUJdG4X5jE7T2vbgCLcB/s640/125x88.png" title="Pseudo Hilbert Curve" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">The version of the 125 x 88 curve from the paper</td></tr>
</tbody></table>
.<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-y__pW4cpBoM/WNz8tVnOeaI/AAAAAAAAmpo/6zEJwWnqWMAu4ZwHPZnrvaAkKjp2-eugwCLcB/s1600/125x88_3.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Pseudo Hilbert Curve" border="0" height="488" src="https://3.bp.blogspot.com/-y__pW4cpBoM/WNz8tVnOeaI/AAAAAAAAmpo/6zEJwWnqWMAu4ZwHPZnrvaAkKjp2-eugwCLcB/s640/125x88_3.png" title="Pseudo Hilbert Curve" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Overlay of the two curves to see where they differ</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
I was scratching my head trying to figure out why, and after a bit of research I discovered that the author later made some optimisations to the scan methods for blocks larger than or equal to 4x4. The images in the paper were generated with that method. Basically larger blocks are scanned with a Hilbert like method and not the bidirectional raster scans shown above. So I'm not losing my mind. Well, not for that reason anyway. I need to think about how to alter my code to make this work. Hmmm.</div>
<br />
My other blog posts on the hilbert curve can be found here.<br />
<a href="http://www.grant-trebbin.com/2017/03/calculating-hilbert-curve-coordinates.html">Calculating Hilbert Curve Coordinates</a>Grant Trebbinhttp://www.blogger.com/profile/13253301568478517009noreply@blogger.com0Brisbane QLD, Australia-27.4697707 153.02512350000006-28.3721187 151.73423000000005 -26.5674227 154.31601700000007tag:blogger.com,1999:blog-3153881528840143069.post-754892473043725872017-03-16T23:02:00.001+10:002017-03-16T23:02:26.562+10:00Calculating Hilbert Curve Coordinates<div style="text-align: justify;">
You may have noticed from some of my previous blog posts that I've fallen down a rabbit hole learning about Gray codes and Hilbert curves. They weren't just random topics. I wrote those articles in order to understand the topic of this one, how to easily convert a Hilbert Index to Hilbert Coordinates via a method described in a paper by John Skilling.</div>
<br />
<a href="https://drive.google.com/file/d/0B5Hb04O3hlQSRkhuRHpTUU9kUHc/view?usp=sharing">Skilling, J. (2004), "Programming the Hilbert Curve", AIP Conference Proceedings.</a><br />
<br />
Regrettably I don't yet understand why it works to a level that I'm satisfied with. The paper describes the process and gives a summary of previous work by Butz and Lawder but doesn't really give a clear explanation of why the transform works. It may be perfectly clear to someone who works in the field, but I don't get it... yet.<br />
<br />
<div style="text-align: justify;">
What I am capable of doing though is summarising the information here with some graphics to explain the concept to the next person that gets <a href="https://xkcd.com/356/">nerd sniped</a> by this. I'll start by recommending my last few blog posts as they will give you an idea as to my train of thought.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
<a href="http://www.grant-trebbin.com/2017/02/entry-and-exit-points-for-space-filling.html">Entry and Exit Points for Space Filling Paths on a Grid</a></div>
<div style="text-align: justify;">
<a href="http://www.grant-trebbin.com/2017/02/hilbert-curve-generation-with-lookup.html">Hilbert Curve Generation With Lookup Tables</a></div>
<div style="text-align: justify;">
<a href="http://www.grant-trebbin.com/2017/03/converting-binary-to-gray-code-with-xor.html">Converting Binary to Gray Code with XOR</a></div>
<br />
<div style="text-align: justify;">
A basic concept to understand is how binary numbers are treated as coordinates. In the animation below, the index is 6 bits long and counts up from 000000 to 111111. This can be used to cover every coordinate on an 8 x 8 two dimensional grid if every second bit belongs to the coordinates of one dimension while the others belong to the other dimension. In this case the red bits belong to the x axis while the blue bits belong to the y axis. Everything I'll describe in this post is for two dimensions, but it works for any number of dimensions. For example an 8x8x8 grid could be covered with a 9 bit index where bits 0, 3, 6 belong to one axis, 1, 4, 7 to another, and 2, 5 ,8 to another.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://2.bp.blogspot.com/-QIHr5uKems4/WMpzXv65ewI/AAAAAAAAmcM/bn2HNdA3tFIn26eiwX1vp5tCXpBoedO3QCLcB/s1600/BinaryIndex.gif" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Binary Indexing Animation" border="0" height="360" src="https://2.bp.blogspot.com/-QIHr5uKems4/WMpzXv65ewI/AAAAAAAAmcM/bn2HNdA3tFIn26eiwX1vp5tCXpBoedO3QCLcB/s640/BinaryIndex.gif" title="Binary Indexing Animation" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Binary indexing in 2 dimensions</td></tr>
</tbody></table>
<div style="text-align: justify;">
In the binary indexing animation you can see that there are diagonal lines. These occur because more than one bit of the index can change at once affecting both dimensions.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
The first step in the Skilling Transform is to take the binary reflected Gray code of the index. This means that only one bit at a time can change. Therefore the value of only one axis can change at a time leaving only vertical and horizontal movements.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://2.bp.blogspot.com/-YyJMyUIWUx4/WMpzuCAoBGI/AAAAAAAAmcQ/xyFRgkALy6cJJYoYG4bX6fw9LCukWWqOACLcB/s1600/GrayIndex.gif" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Gray Code Animation" border="0" height="360" src="https://2.bp.blogspot.com/-YyJMyUIWUx4/WMpzuCAoBGI/AAAAAAAAmcQ/xyFRgkALy6cJJYoYG4bX6fw9LCukWWqOACLcB/s640/GrayIndex.gif" title="Gray Code Animation" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Gray code indexing in 2 dimensions</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
The addressing scheme detailed above is formally described in this section of the paper. I put this here just so we're all on the same page about the variable names.</div>
<br />
$$$p$$$ is the number of bits in each axis<br />
$$$n$$$ is the number of dimensions<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-yxKeIDqVmfU/WMp0CvKuxxI/AAAAAAAAmcU/xDciFPlCs9I2adVZJS4bnTQJ3oAewZRLgCLcB/s1600/Skilling1.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Addressing Scheme" border="0" height="78" src="https://4.bp.blogspot.com/-yxKeIDqVmfU/WMp0CvKuxxI/AAAAAAAAmcU/xDciFPlCs9I2adVZJS4bnTQJ3oAewZRLgCLcB/s640/Skilling1.png" title="Addressing Scheme" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Addressing description</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
Now onto the actual transform. It's minimal and easy to compute. It's not a recursive algorithm and takes a bit string that specifies the Hilbert index as an input and performs a series of swaps and inversions to return a bit string of the same length that describes the Hilbert coordinates.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://2.bp.blogspot.com/-Iw8QhzAZp3c/WMp0ND0LVDI/AAAAAAAAmcY/PQ1dp5B4lb0p8eSulBrDf4gImKr1Vw-RwCLcB/s1600/Skilling2.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Algorithm" border="0" height="162" src="https://2.bp.blogspot.com/-Iw8QhzAZp3c/WMp0ND0LVDI/AAAAAAAAmcY/PQ1dp5B4lb0p8eSulBrDf4gImKr1Vw-RwCLcB/s640/Skilling2.png" title="Algorithm" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Skilling transform</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
To see if I could understand the process better I wanted to visualise the transform. The animation below show the transformation from Gray code indexing to the Hilbert curve. You can see how the algorithm starts the transformation on the smaller features first and works up to larger features at each step.</div>
<div style="text-align: justify;">
<br /></div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-7F-Texre6ts/WMp0g9bLCiI/AAAAAAAAmcc/yZEwCErhvoIjRU5__iXIzCP-bFC71Y1GwCLcB/s1600/GrayToHilbert.gif" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Hilbert Curve Animation" border="0" height="360" src="https://3.bp.blogspot.com/-7F-Texre6ts/WMp0g9bLCiI/AAAAAAAAmcc/yZEwCErhvoIjRU5__iXIzCP-bFC71Y1GwCLcB/s640/GrayToHilbert.gif" title="Hilbert Curve Animation" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Gray code to Hilbert curve via the Skilling transform in 2 dimensions.</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
Hopefully the worked example below will help people understand the process a little better. The index is converted to its Gray code and the algorithm processes bits in a reverse order. The grey boxes refer to the bit $$$r$$$ shown in the algorithm above. The bits that are classified as low bits at each stage are underlined.</div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://2.bp.blogspot.com/-HhlE_xy2V5A/WMp4z9x9lCI/AAAAAAAAmcs/R61xUba94pMxxW4WUtNGFCqX5Zb7RewtgCLcB/s1600/Example137.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Hilbert Index to Coordinates" border="0" height="640" src="https://2.bp.blogspot.com/-HhlE_xy2V5A/WMp4z9x9lCI/AAAAAAAAmcs/R61xUba94pMxxW4WUtNGFCqX5Zb7RewtgCLcB/s640/Example137.png" title="Hilbert Index to Coordinates" width="570" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Worked example</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
I can't really offer much of a conclusion here. The understanding I've gleaned so far is minimal and superficial at best. I 'll leave this one for a while and come back to it in the future when I have more time.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
I have a love hate relationship with problems like this. I find them fascinating, but at the same time they remind me how much I miss formal study, and I get bummed out. Kinda sucks having no one to bounce ideas off either. Having said that though, I've finally generated some animations that I'm proud of. You can find the undocumented scratch code <a href="https://gist.github.com/GrantTrebbin/e4bfcdb047e4883e785e3e192e95aa55">here</a>.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
If you come across this page and have a better understanding of why this works I'd be glad to hear from you.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
<br /></div>
Grant Trebbinhttp://www.blogger.com/profile/13253301568478517009noreply@blogger.com0Brisbane QLD, Australia-27.4697707 153.02512350000006-28.3721187 151.73423000000005 -26.5674227 154.31601700000007tag:blogger.com,1999:blog-3153881528840143069.post-74682092083270511672017-03-04T15:18:00.001+10:002017-03-05T22:50:08.349+10:00Converting Binary to Gray Code with XOR<div style="text-align: justify;">
Over the last week I've been researching <a href="https://en.wikipedia.org/wiki/Gray_code">Gray Codes</a> and how to generate them. I understand the basic concept but I wanted a deeper understanding. Most of the explanations out there are a little dense so I'm going to try to make the available information a little bit more accessible to everyone. So let's start with a basic explanation of what a Gray code is.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
A Gray Code is a special way of counting, where adjacent entries differ by only one digit. In practice this almost always refers to a binary counting sequence and more specifically a special code called the Binary Reflected Gray Code (BRGC). From here on, this is the Gray code that I'll be talking about.</div>
<br />
<div style="text-align: justify;">
These code have practical uses in many areas. The one that I'm most familiar with is in rotary encoders where it's advantageous that only one digit changes at a time. In a normal binary counting sequence you may have multiple bits change at once. For example from $$$0111$$$ to $$$1000$$$. The problem with this is that if all the bits don't change at exactly the same moment, the value $$$1010$$$ may be read from the sensor. If Gray codes are used, as you progress through the series only one bit changes at a time. This leaves no ambiguity as to what the value is.</div>
<br />
Let's start with a formal definition of a Gray code and try to explain things in easier to understand terms.<br />
<br />
$$G_0=\epsilon \\ G_{k+1}=0G_k,1G_k^R$$<br />
<br />
<div style="text-align: justify;">
The series for zero bits is shown as $$$G_0=\epsilon$$$ and indicates an empty series. The next equation, $$$G_{k+1}=0G_k,1G_k^R$$$ indicates that the series for a Gray code series of $$$k+1$$$ bits is created by taking the the Gray code of $$$k$$$ bits and joining a reversed copy to its end, with zeros added before entries in the first half of the series, and ones added before entries in the second half of the series. This is how the series ensures that consecutive entries only differ by one digit. This may be clearer in the diagram below.</div>
<div style="text-align: justify;">
<br /></div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-TXhKvhNFyhQ/WLppua7rvJI/AAAAAAAAmYY/CVYIajLAJjIudlfy0AOY2yVRdeGGjRB-wCLcB/s1600/Grayk-k%252B1.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Equation" border="0" height="188" src="https://4.bp.blogspot.com/-TXhKvhNFyhQ/WLppua7rvJI/AAAAAAAAmYY/CVYIajLAJjIudlfy0AOY2yVRdeGGjRB-wCLcB/s640/Grayk-k%252B1.png" title="Equation" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Constructing $$$G_{k+1}$$$ from $$$G_{k}$$$</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
If $$$G_k$$$ is a Gray code where consecutive entries differ by one digit, then appending a mirror of itself to its end won't change that, except for where the two series join, as those two entries will be the same. Adding zero to the first half of the new series and one to the second half of the new series won't change it either but it does mean that the entries where the series join now differ by one digit. This means that the new series $$$G_{k+1}$$$ is now also a Gray code. It also proves that the entries in the output are unique. Starting with $$$G_0$$$, we know that all its entries are unique. If we then assume that all the elements of $$$G_k$$$ are unique, then the elements of $$$G_{k+1}$$$ must also be unique as $$$G_k$$$ with zeros added before it and a reverse copy of $$$G_k$$$ with ones added before it create a new unique series. It's then provable by induction that the each entry in a Gray code is unique.<br />
<br />
This gives us the instructions needed to construct a Gray code of any length. Start with the minimal Gray Code that contains one empty element and keep doubling its length when adding a new digit. </div>
<div>
<br /></div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-eu8KQleYQG4/WLppzgjFEMI/AAAAAAAAmYc/6CbfsAHq7WgKdrlV5kk0glp4hlqZWaONQCLcB/s1600/Gray2-3.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Gray Code" border="0" height="280" src="https://3.bp.blogspot.com/-eu8KQleYQG4/WLppzgjFEMI/AAAAAAAAmYc/6CbfsAHq7WgKdrlV5kk0glp4hlqZWaONQCLcB/s640/Gray2-3.png" title="Gray Code" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Constructing $$$G_3$$$ from $$$G_2$$$</td></tr>
</tbody></table>
Getting a picture in your mind of what a Gray code looks like will be helpful for the next step. For some situations the above representation can help, but in others, the vertical table representation with the index $$$n$$$ of each element is better.<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://2.bp.blogspot.com/-K_SMCvaT8cs/WLqTCpCEyEI/AAAAAAAAmY0/EtRi8nSNP3w-_jBhXmg3mhH0Ux-QNcs6ACLcB/s1600/Table.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Gray Code" border="0" src="https://2.bp.blogspot.com/-K_SMCvaT8cs/WLqTCpCEyEI/AAAAAAAAmY0/EtRi8nSNP3w-_jBhXmg3mhH0Ux-QNcs6ACLcB/s1600/Table.png" title="Gray Code" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Gray code indices in decimal</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
Now that I've explained the basics of what a Gray code is, I want to detail a proof of a well known formula to generate them with an xor operation.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
$$H[n] = n \oplus (n>>1)$$</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
Where $$$H[n]$$$ is the $$$n$$$th element of the Gray code. $$$H$$$ is used at the moment as it's a hypothesis that this formula is equivalent to $$$G[n]$$$ described above.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
I found a well thought out explanation of this proof in a <a href="https://www.quora.com/I-came-across-this-code-which-generates-the-nth-gray-code-number-G-n-n-n-1-How-can-we-proof-that-it-is-correct">Quora post</a> but it could do with some further explanation. So I'll repeat the proof here with some commentary to help those new to the subject. To be clear all of these operations are performed on the binary representation of the numbers involved.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
First, let's define a helper function.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
$$F[n,k]=(2^k-1) \oplus n$$</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
$$$F[n,k]$$$ is a function that inverts all the bits of a binary string $$$n$$$ of length $$$k$$$. $$$2^k$$$ is a binary string of length $$$k+1$$$ that is all zeros except for the most significant bit. Subtracting one from this will create a binary string of length $k$ that is all ones. When the string $n$ is xored with this all of the bits are inverted. This is a function that essentially reverses the direction of a binary count. For example, when $$$k=3$$$, and for a value of $$$n=001$$$, $$$F[001,3] = 110$$$. Where $$$001$$$ is the second entry when counting in binary, $$$110$$$ is the second last. It's a mathematical representation of reflecting/mirroring a binary count.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
Now we have that out of the way we will prove the following</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
$$H[x] \oplus H[F[x,k]]=2^{k-1}$$</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
What does that mean? It's saying that the output of the hypothesis function xored with the hypothesis function with the input ordering reversed will give a string of length $$$k$$$ that is all zeros except for the most significant bit. This is a fancy way of saying that the output of $$$H$$$ is symmetrically except for the most significant bit. This is a property of the Gray code that we are trying to prove. From the beginning of the series each element of a Gray code is equal to the element the same distance from the end except for the most significant bit.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
As $$$F[x,k]$$$ is an inverted version of $$$x$$$ the most significant bit of one or the other, but not both, will be equal to one. Let's assume that it's $$$x$$$. It doesn't matter which one is chosen, the proof works either way. We can now write</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
$$x=2^{k-1} \oplus y \quad where \quad y<2^{k-1}$$</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
It then follows that $$$F[x,k] = F[y,k-1]$$$. This says that inverting $$$x$$$ which we have defined to start with one, will now start with zero and is equal to the inverted value of the new shorter bit string $$$y$$$. For example if $$$x=1100101$$$ then $$$y = 100101$$$. So $$$F[1100101,7]=0011010$$$ and $$$F[100101,6]=011010$$$.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
Now onto the proof. It's all maths at this point, you can ignore conceptual ideas here and just work through the process.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
\begin{align}H[x] \oplus H[F[x,k]]&=(2^{k-1} \oplus y) \oplus (2^{k-2} \oplus (y>>1)) \oplus H[F[y,k-1]] \\ &=2^{k-1} \oplus 2^{k-2} \oplus H[y] \oplus H[F[y,k-1]] \\ &= 2^{k-1} \oplus 2^{k-2} \oplus 2^{k-2} \\ &= 2^{k-1}\end{align}</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
Now we've proven this, for strings of length $$$k$$$ using strings of length $$$k-1$$$ it just needs to be proved for strings of length 1 ie $$$k=1$$$ for the inductive proof to be complete.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
\begin{align} H[0] \oplus H[1] &= 0 \oplus 0 \oplus 1 \oplus 0 \\&=1\end{align}</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
All of that above just proves that $$$H[n] = n \oplus (n>>1)$$$ results in an output series that is mirrored with the most significant bit inverted. Now we need to prove the following</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
$$H[2^k \oplus x] = 2^k \oplus H[F[x,k]] \quad where \quad x<2^k$$</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
This states that if we add a one to the input to the hypothesis function, it's equivalent to inverting the input and then adding a one to the output. It's hard to see, but this describes the process of going from a Gray code of $$$k-1$$$ bits to a Gray code of $$$k$$$ bits.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
\begin{align} H[2^k \oplus x] &= 2^k \oplus x \oplus 2^{k-1} \oplus (x>>1) \\ &= 2^k \oplus 2^{k-1} \oplus H[x] \\ &=2^k \oplus H[F[x,k]]\end{align}</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
As we did before, this needs to be proved for $$$k=1$$$ for the induction proof to work.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
\begin{align}H[10 \oplus 1] &= 10 \oplus H[0] \\H[11] &= 10 \oplus 0 \oplus 0 \\ 11 \oplus 01 &= 10 \\ 10=10 \end{align}</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
OK, that was a confusing rabbit hole we just fell down, but it proves that $$$H[n]=G[n]$$$ for all $$$n$$$. I'm not entirely sure we need both parts of that proof, but it can't hurt to prove it twice. 😅 </div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
We can now be sure that $$$G[n] = n \oplus (n>>1)$$$ How simple is that! A Gray code can be generated by xoring its index with itself but right shifted by one. This means that each digit of the Gray code is the xor of two consecutive digits in the input.</div>
<div style="text-align: justify;">
<br /></div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-AfKRa1HHs84/WLv-aDA8mSI/AAAAAAAAmZM/yqbnOvXDS6877eqgHHbDPa9cd1ZT1TCKwCLcB/s1600/Diff.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="94" src="https://1.bp.blogspot.com/-AfKRa1HHs84/WLv-aDA8mSI/AAAAAAAAmZM/yqbnOvXDS6877eqgHHbDPa9cd1ZT1TCKwCLcB/s320/Diff.png" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Generating a Gray code from an index - input in green output in purple</td></tr>
</tbody></table>
<div style="text-align: justify;">
In the image above it's kind of like differentiating the bit stream. If two consecutive bits are different it generates a one in the output. So if we go from index to Gray code with something like a differentiation you might think we can go the other way with integration. You sure can. I won't prove it but you can look it up.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
Now all this seems a little simple and useless apart from the use case I gave at the start, but this goes into some deep concepts. We're looking at mathematics over a <a href="https://en.wikipedia.org/wiki/Finite_field_arithmetic#Rijndael.27s_finite_field">finite field</a>, in this case $$$GF(2)$$$. Now here's the really cool part. If you use each digit of a Gray code as a coordinate and plot it, you visit each vertex of a square for a two bit Gray code. For a three bit Gray code you visit each vertex of a cube travelling along the edges. More generally for a k bit code you travel along the edges of a k-dimensional hypercube visiting all vertices. This is called a Hamilton cycle.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
Sorry if I'm ranting but I find all this fascinating, but it hasn't solidified in my mind yet.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
If you've made it this far you deserve a joke.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
Q. What's the best way to visit all the vertices of a hypercube?</div>
<div style="text-align: justify;">
A. On a Hamilton bicycle.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
Hey give me a break. I didn't say it'd be funny.<br />
<br />
In case the equations don't render properly, <a href="https://drive.google.com/file/d/0B5Hb04O3hlQSVDRtenVpaDRHTTQ/view?usp=sharing">here is a PDF of this page</a>.<br />
<a href="https://drive.google.com/file/d/0B5Hb04O3hlQSTm1WMEVsUmEycnc/view?usp=sharing">A PDF of the original solution on Quora</a>.</div>
Grant Trebbinhttp://www.blogger.com/profile/13253301568478517009noreply@blogger.com0Brisbane QLD, Australia-27.4697707 153.02512350000006-28.3721187 151.73423000000005 -26.5674227 154.31601700000007tag:blogger.com,1999:blog-3153881528840143069.post-45889285229935194372017-02-22T23:02:00.001+10:002017-02-22T23:02:55.834+10:00Hilbert Curve Generation With Lookup Tables<div style="text-align: justify;">
I've been researching something that requires a Hilbert curve and I thought I'd share how to generate the path and also move between the index and coordinates of points.</div>
<br />
<div style="text-align: justify;">
For those of you unfamiliar with Hilbert curves let me quickly explain what one is and why you would want to use one. The curve covers every point in a square with side length 2^n by moving up, down, left and right, starting at one corner and ending at an adjacent corner. You could accomplish the same requirements by just scanning back and forth across the rows, but the advantage the Hilbert curve has is that nearby points on the 2D grid are generally also near each other on the curve. If you were to scan back and forth you get a lot of points that are directly beside each other in 2D space but very far apart on the curve.</div>
<br />
<div style="text-align: justify;">
So why would you want to use one? They're great for turning 2D areas into 1D streams of data while maintaining locality. This comes in handy in image processing. Depending on what you want to do, this may make the processing a lot easier.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
Generation of the curve can be done recursively by first selecting an initial shape type and then using tables of sub-types and locations to generate the next stage. In the animation below the initial shape is type 1. When you go to the sub-type table you see that type 1 is replaced with types 2, 1, 1, and 4 in that order. The position of each sub-type is defined by the parent type. As the parent is type 1 the locations of the sub-types from the location table are:</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
2 at (0, 0)</div>
<div style="text-align: justify;">
1 at (0, 1)</div>
<div style="text-align: justify;">
1 at (1, 1)</div>
<div style="text-align: justify;">
4 at (1, 0)</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
The location table can then be used to find the coordinates of the sub-types. As binary coordinates are used, the x and y coordinates of the sub-type can be appended to its coordinates to find the new sub-coordinates. For example, the coordinates of the type 4 sub-type at position (1, 0) above are (1, 1) (0, 1) (0, 0) (1, 0). Appending these to the coordinates of (1, 0) you find the new sub coordinates (11, 01) (10, 01) (10, 00) (11, 00). Trust me it's confusing at first but after a while it all makes complete sense. I'm still trying to come up with appropriate terminology for the process. These tables are from a paper</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
<a href="https://drive.google.com/file/d/0B5Hb04O3hlQSdl9pTHZCSkpVQUE/view?usp=sharing">Zhang, Kamata, Ueshige "<i>A Pseudo-Hilbert Scan for Arbitrarily-Sized Arrays</i>"</a></div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
It's a little confusing at first but I recommend reading that to help understand the process.</div>
<div style="text-align: justify;">
<br /></div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-m9AgssBF-vw/WK1wumFbcoI/AAAAAAAAmPo/cdXoP-ap75QKO9h99trbvOCr2CcJ7klWACLcB/s1600/hilbert.gif" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="413" src="https://3.bp.blogspot.com/-m9AgssBF-vw/WK1wumFbcoI/AAAAAAAAmPo/cdXoP-ap75QKO9h99trbvOCr2CcJ7klWACLcB/s640/hilbert.gif" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Recursive Hilbert Curve Generation</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
What if you don't want to generate the full curve and just want to know where along the curve a point lays or where a point on the curve is in 2D space? Let's use the below example to demonstrate this.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-GC0lBjpXVg4/WK1w2gwvbpI/AAAAAAAAmPs/r72daBN6qIw2EeOs2IMxfeF54dk9XUkIACLcB/s1600/HilbertExample.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="412" src="https://4.bp.blogspot.com/-GC0lBjpXVg4/WK1w2gwvbpI/AAAAAAAAmPs/r72daBN6qIw2EeOs2IMxfeF54dk9XUkIACLcB/s640/HilbertExample.png" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">44th Point at location (111, 101)</td></tr>
</tbody></table>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
The above image shows the 44th point of the third stage at (111, 101). It's actually the 45th point but we start counting at 0. We add an index row to the tables provided in the above paper to make the process easier.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-qVyv8BuMCpw/WK1w9RRsAXI/AAAAAAAAmPw/sJx3Xoztx2kokw5mN-XMNqSsg2IuKQI2QCLcB/s1600/Tables.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="254" src="https://1.bp.blogspot.com/-qVyv8BuMCpw/WK1w9RRsAXI/AAAAAAAAmPw/sJx3Xoztx2kokw5mN-XMNqSsg2IuKQI2QCLcB/s640/Tables.png" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Generation Tables</td></tr>
</tbody></table>
<br />
We start by converting the index to a binary number with 2 bits for every stage. In this case it's the third stage, so we get 6 bits. These bits are placed two at a time on rows under the index column. We also define the initial shape as type 1. From this, the sub-type and location for the first row can be found. The sub-type becomes the type for the next row. This process is repeated two more times until we have three locations. To get the final location coordinates, just append the x and y coordinates downwards to get (111, 101).<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-dSZpg6zYihs/WK1xC4O2p3I/AAAAAAAAmP0/qEMyFzNVVmga9btkoF8ucOGz6p5IHwqtQCLcB/s1600/IndexToLocation.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="330" src="https://1.bp.blogspot.com/-dSZpg6zYihs/WK1xC4O2p3I/AAAAAAAAmP0/qEMyFzNVVmga9btkoF8ucOGz6p5IHwqtQCLcB/s640/IndexToLocation.jpg" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Converting an Index to a location</td></tr>
</tbody></table>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
To go from coordinate to index, split the location up by removing the highest bit from the x and y coordinate for each line. As the start type is known, the index can be found. This index is then used to find the sub-type for the next row. This is repeated two more times. The indices are then concatenated to get 101100 in binary which is 44.</div>
<div style="text-align: justify;">
<br /></div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-dMDyMn-kcAY/WK1xJhPGL4I/AAAAAAAAmP4/J9kYUkXDSkweMPQU-bJgp8OvsLzFzPt3wCLcB/s1600/LocationToIndex.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="382" src="https://3.bp.blogspot.com/-dMDyMn-kcAY/WK1xJhPGL4I/AAAAAAAAmP4/J9kYUkXDSkweMPQU-bJgp8OvsLzFzPt3wCLcB/s640/LocationToIndex.jpg" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Converting a location to an index</td></tr>
</tbody></table>
<br />
I hope this helped to explain the process. Trust me, even if it's still confusing, having diagrams and a couple of hopefully easy to follow examples will help.Grant Trebbinhttp://www.blogger.com/profile/13253301568478517009noreply@blogger.com0Brisbane QLD, Australia-27.4697707 153.02512350000006-28.3721187 151.73423000000005 -26.5674227 154.31601700000007tag:blogger.com,1999:blog-3153881528840143069.post-15275894424068966492017-02-11T21:39:00.001+10:002017-02-11T21:39:17.642+10:00Entry and Exit Points for Space Filling Paths on a Grid<div style="text-align: justify;">
I've been researching space filling curves recently and came across an interesting algorithm to generate curves for arbitrary areas. To be completely accurate, space filling curves cover the entire unit square in continuous space, whereas what I'm looking at is the discrete form that covers a grid. Below when a path or curve is mentioned, what is meant is a way to cover a rectangular area by moving one square at a time, either up, down, left, or right, without crossing over itself. The curve starts in one corner and ends in another.</div>
<br />
<div style="text-align: justify;">
Being almost completely new to this, I set about understanding the description of the algorithm. Although it was accompanied by code, details of the process were scant. The first part described rules for valid corner exit points given a starting point on grids with edges that are either odd or even. This is what I want to explore in this blog post.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
A rectangular area can have an either odd or even width and an either odd or even height. There are 4 possible combinations of these edge dimensions and for each one, a set of directions were supplied. I didn't just want to take these at face value. Some sort of proof was needed.</div>
<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://2.bp.blogspot.com/-Meawnx8RzMs/WJ7h1sdoUFI/AAAAAAAAkoY/EWQZEIke4qQEA9fChVeE8WZGqVTdNrl_ACLcB/s1600/spacefillingEveneOdd.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="240" src="https://2.bp.blogspot.com/-Meawnx8RzMs/WJ7h1sdoUFI/AAAAAAAAkoY/EWQZEIke4qQEA9fChVeE8WZGqVTdNrl_ACLcB/s640/spacefillingEveneOdd.jpg" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;"><a href="http://lutanho.net/pic2html/draw_sfc.html">Space Filling Curve Algorithm by Lutz Tautenhahn</a></td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
The proof below doesn't say anything about the existence of a path/curve that starts at one corner and ends at another covering all squares. All it does is show if a path is possible or not. Although it's relatively easy to prove that a path can be found for all of the scenarios below, we'll leave that for another time.</div>
<br />
<div style="text-align: justify;">
So what are the results? In grids with two even edges, a path can be found from a corner to either adjacent corner, but not to the diagonal corner. In grids with an even and odd side a path can be found to the diagonal corner and the adjacent corner on the even side but not the odd side. Finally in a grid with two odd sides a path can be found to any other corner except if one of the odd edges is equal to 1. In that case the path is only diagonal or along the odd side that isn't one. That last bit isn't in the proof but it's obvious.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-jC8l60fpn-0/WJ7aC2NZxQI/AAAAAAAAkoA/aHyw7PAbyZk2hHdKwCDEstm4f5KZoK_4QCLcB/s1600/Epson_0694_1%2B-%2BCopy.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Directions" border="0" height="334" src="https://4.bp.blogspot.com/-jC8l60fpn-0/WJ7aC2NZxQI/AAAAAAAAkoA/aHyw7PAbyZk2hHdKwCDEstm4f5KZoK_4QCLcB/s640/Epson_0694_1%2B-%2BCopy.jpg" title="Directions" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Allow directions in a space filling grid</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
Proving the directions is straight forward. If you imagine that the corner start square of a grid is covered, and every time you move, another square is covered, it becomes obvious that there are (wh-1) moves until the entire space is covered. The total number of moves is also equal to the number of up, down, left, and right moves. If you want to move right side of the grid the number of right moves minus the number of left moves has to be equal to (w-1). If you want to stay on the left, the number of left moves is equal to the number of right moves. Similarly if you want to move to the bottom of the grid, the number of down moves minus the number of up moves is equal to (h-1). If you want to stay at the top, the number of down and up moves mus t be equal. When these equations are combined the directions above can be found.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-qBrOpWHl9SE/WJ7aKnm7HEI/AAAAAAAAkoE/f26hdABhmp0gxiYK1lAvBmPKo_MPSsrggCLcB/s1600/Epson_0693_1%2B-%2BCopy.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="proof" border="0" height="640" src="https://1.bp.blogspot.com/-qBrOpWHl9SE/WJ7aKnm7HEI/AAAAAAAAkoE/f26hdABhmp0gxiYK1lAvBmPKo_MPSsrggCLcB/s640/Epson_0693_1%2B-%2BCopy.jpg" title="proof" width="444" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Grid movement proof</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
It was redundant to prove both the Odd-Even and Even-Odd case as they are a diagonal mirroring of the same scenario. It's also sufficient to only show the paths starting at the top left corner as paths starting in other corners are vertical and or horizontal mirrors of paths in the top left corner.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
Although I didn't end up using the curve filling path in the first image, it helped me understand some of the subtleties of curve generation.</div>
Grant Trebbinhttp://www.blogger.com/profile/13253301568478517009noreply@blogger.com0Brisbane QLD, Australia-27.4697707 153.02512350000006-28.3721187 151.73423000000005 -26.5674227 154.31601700000007tag:blogger.com,1999:blog-3153881528840143069.post-62299485818254496212017-02-01T21:55:00.000+10:002017-02-01T21:55:04.874+10:00Voronoi StipplingI'm trying to write my own software to convert normal raster images to a corresponding stippled version. If you're unfamiliar with the term, stippling is a style of artwork that that uses are large number of small dots to represent a scene. Areas with a high density of dots appear darker, while areas without dots are white. Normally I like to have reasonably good understanding of a subject before I do a blog post about it, but in this case I'll give a quick outline of what I'm trying to achieve and then fill in the details in a later post.<br />
<br />
So, how do you get an image like this,<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-dAMtYlyYmS8/WJGjf4fJv8I/AAAAAAAAkPk/iNLZjsg9S04DCHRU76gWKGwFgcL01NwzACLcB/s1600/figure_11.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Plant" border="0" height="435" src="https://4.bp.blogspot.com/-dAMtYlyYmS8/WJGjf4fJv8I/AAAAAAAAkPk/iNLZjsg9S04DCHRU76gWKGwFgcL01NwzACLcB/s640/figure_11.png" title="Plant" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Stippled Image</td></tr>
</tbody></table>
<br />
From something like this.<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-iGsP0GnZqL0/WJGjoibA8zI/AAAAAAAAkPo/PMMPNFsOOFoRwYwwOrvGOTxs3Z2Si35HwCLcB/s1600/plant4h.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Plant" border="0" height="376" src="https://3.bp.blogspot.com/-iGsP0GnZqL0/WJGjoibA8zI/AAAAAAAAkPo/PMMPNFsOOFoRwYwwOrvGOTxs3Z2Si35HwCLcB/s400/plant4h.png" title="Plant" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Original Image</td></tr>
</tbody></table>
<br />
To start with I'm trying to replicate the process in a paper by Adrian Secord.<br />
<br />
<i><a href="https://mrl.nyu.edu/~ajsecord/npar2002/npar2002_ajsecord_preprint.pdf">Weighted Voronoi Stippling</a></i><br />
<i><a href="https://mrl.nyu.edu/~ajsecord/npar2002/npar2002_ajsecord_preprint.pdf">Adrian Secord</a></i><br />
<i><a href="https://mrl.nyu.edu/~ajsecord/npar2002/npar2002_ajsecord_preprint.pdf">2nd International Symposium on Non-Photorealistic Animation and Rendering (NPAR 2002)</a></i><br />
<br />
<div style="text-align: justify;">
The first step is to generate a number of points equal to the desired number of stippling points in the final image. They can be randomly distributed over the image, or ideally via a rough approximation, close to the locations of the stippling dots in the output image. As the process I'm about to describe is iterative, the closer the initial approximation is the final output, the faster the algorithm will converge.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
After the points have been created, their Voronoi diagram is generated. A Voronoi diagram produces a region for each input point that identifies all the locations that are closest to that dot than any other. There are some tricks to making sure that the regions around the boundary are properly created but in general it's a simple call to scipy.spatial.Voronoi</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
That's great, but the process so far hasn't taken the input image into account(unless you use it to generate the initial point locations). Now that a number of points and their corresponding regions are created, the weighted centroid of the area is calculated. The centroid then becomes the location of the new point. This process of creating Voronoi diagrams and calculating centroids is repeated until some convergence criteria is met and is better known as <a href="https://en.wikipedia.org/wiki/Lloyd's_algorithm">Lloyd's Algorithm</a>.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
In the image below, the black dots are the initial points and the white dots are the centroids of the Voronoi regions after an iteration.</div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-rP8zLPbJG1I/WJGj2YM4DcI/AAAAAAAAkPs/7hwQuojrAascd6n-rVmS_ATMaqOOOogGwCLcB/s1600/figure_12.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Voronoi Diagram" border="0" height="475" src="https://4.bp.blogspot.com/-rP8zLPbJG1I/WJGj2YM4DcI/AAAAAAAAkPs/7hwQuojrAascd6n-rVmS_ATMaqOOOogGwCLcB/s640/figure_12.png" title="Voronoi Diagram" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Voronoi Diagram with centroids</td></tr>
</tbody></table>
Overlaying this diagram on the original image helps to illustrate the process a little better. Obviously the image below is sparsely stippled and the object isn't recognisable with only 64 points.<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://2.bp.blogspot.com/-P7SFrHjUWaI/WJGkBR81l0I/AAAAAAAAkP0/7VUVMXxh8ccb3wp7IJu3gAZzhHL8tHQOwCLcB/s1600/figure_13.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Voronoi Diagram" border="0" height="602" src="https://2.bp.blogspot.com/-P7SFrHjUWaI/WJGkBR81l0I/AAAAAAAAkP0/7VUVMXxh8ccb3wp7IJu3gAZzhHL8tHQOwCLcB/s640/figure_13.jpg" title="Voronoi Diagram" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Voronoi Iteration</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
I've generated the next diagram with I think 256 points to explain a subtle point. The Voronoi region for each point is a convex polygon. Therefore its centroid will always be located within itself. As the number of points increases the size of the regions decreases. This means that the process will take a long time to converge as the points can only move a small amount during each iteration. That's why you need to place the initial points as close to their final location as possible. Or do you?</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
I only discovered this problem after programming my solution and needed a quick way to overcome it. If a large number of points take a long time to converge then a small number should converge quickly. So I started with only two points. After a few iterations, each point splits, like a cell undergoing Mitosis. Each point splits into two new points diametrically opposed on a unit circle centred on the old point. The direction of the split is randomly chosen. (I have a <u>hunch</u> that continually splitting in the same direction will cause artifacts that will delay convergence) These new points are then iterated on for a while and then split again. The key is to get the points close to where they need to be early and then converge and add the detail later.</div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-a2TkDvVrcI8/WJGkS0gX3sI/AAAAAAAAkP8/hxJP0-F3wSMAyJzcZQLtQ9ml60KZfGuhgCLcB/s1600/figure_14.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Voronoi Diagram" border="0" height="476" src="https://4.bp.blogspot.com/-a2TkDvVrcI8/WJGkS0gX3sI/AAAAAAAAkP8/hxJP0-F3wSMAyJzcZQLtQ9ml60KZfGuhgCLcB/s640/figure_14.png" title="Voronoi Diagram" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Dense Voronoi diagram</td></tr>
</tbody></table>
I have some ideas I want to try to make the image better. There are obviously some linearity problems with the output. White parts aren't as light as they are should be. My code is a mess too. It needs a clean up. I'm having fun though.Grant Trebbinhttp://www.blogger.com/profile/13253301568478517009noreply@blogger.com0Brisbane QLD, Australia-27.4697707 153.02512350000006-28.3721187 151.73423000000005 -26.5674227 154.31601700000007tag:blogger.com,1999:blog-3153881528840143069.post-2203008336998057792017-01-17T23:53:00.003+10:002017-01-17T23:57:40.071+10:00Arrange Rectangles with Python to Design a Carton<div style="text-align: justify;">
Recently I've been interested in cardboard boxes and how to design and model them. In my <a href="http://www.grant-trebbin.com/2017/01/designing-homemade-cardboard-boxes-in.html">last blog post</a> I described how to create a box in Fusion 360. It works but it's a cumbersome, frustrating, and time consuming process. What was needed was a way to go from concept to template quickly. After looking around and not finding a tool for the job, I designed one. It's called <a href="https://gist.github.com/GrantTrebbin/7cb290b91f2192a2551339e8b053c2f7">rectangleBuilder</a>.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
Laying out a template isn't too hard once you get the hang of it. Draw all the rectangles that make up the box you intend to build and then dimension them. Then define relationships between all the rectangles. An example of a relationship can be seen in the plan below. The bottom middle of rectangle B is in the same location as the top middle of rectangle A.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-aKF9JfAfYDw/WH4TUDzi37I/AAAAAAAAkGM/BVKKC7hen-YjqAgeUZu3b_3XSgZ7OzIoQCLcB/s1600/1_Layout.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Plan" border="0" height="472" src="https://3.bp.blogspot.com/-aKF9JfAfYDw/WH4TUDzi37I/AAAAAAAAkGM/BVKKC7hen-YjqAgeUZu3b_3XSgZ7OzIoQCLcB/s640/1_Layout.jpg" title="Plan" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Box Template Plan</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
This can be done by defining a Rectangle class in python, It is initialized with its width and height and by default is placed with its bottom left corner at (0,0). The Rectangle object is also aware of the position of all its corners and edge midpoints. When called with a code for one of these points it returns the xy coordinates in list form. For example, calling an object with the argument 'TM' will return the coordinates of the top middle. All of this shorthand is explained in the code.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-gn83QZqWqHI/WH4TYMKI6qI/AAAAAAAAkGQ/FQ5ePhx_3SszNc6AsKEl1bZh18vQYp53QCLcB/s1600/2_Code1.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Python Code" border="0" height="315" src="https://4.bp.blogspot.com/-gn83QZqWqHI/WH4TYMKI6qI/AAAAAAAAkGQ/FQ5ePhx_3SszNc6AsKEl1bZh18vQYp53QCLcB/s400/2_Code1.png" title="Python Code" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Define rectangle sizes</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
This is the part that I think is really cool. Positioning the rectangles by defining geometric relationships. In the code below the bottom middle of rectangle A is positioned at the origin. Rectangle B is then positioned so that it's bottom middle is in the same position as the top middle of rectangle A. The last line demonstrates the offset feature. It essentially says, place rectangle M so that its bottom left corner is in the same position as the bottom right of rectangle B then shift it in the y direction by an amount (t+b). The few lines of code above and below completely describe the template for the box.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-DH04pSIPkZU/WH4Tbhy_fWI/AAAAAAAAkGU/YV-93L4uAL4ahW9eBw6tayc0Dgk1_H3NACLcB/s1600/3_Code2.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Python Code" border="0" height="295" src="https://4.bp.blogspot.com/-DH04pSIPkZU/WH4Tbhy_fWI/AAAAAAAAkGU/YV-93L4uAL4ahW9eBw6tayc0Dgk1_H3NACLcB/s400/3_Code2.png" title="Python Code" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Position rectangles</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
This data can then be used to generate an SVG template in python to see if everything is as expected. The outline to cut is in black and the bend lines are marked in red.</div>
<div style="text-align: justify;">
<br /></div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-aGkxXtlFnj0/WH4TewCWYRI/AAAAAAAAkGY/cHVwKpGxpGckQeM-Gfbm1QyX7XEk9gdAQCLcB/s1600/4_test.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Box Template" border="0" height="268" src="https://4.bp.blogspot.com/-aGkxXtlFnj0/WH4TewCWYRI/AAAAAAAAkGY/cHVwKpGxpGckQeM-Gfbm1QyX7XEk9gdAQCLcB/s400/4_test.png" title="Box Template" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Box template</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
That's all well and good but how do we transfer that to cardboard? I don't have a plotter or laser cutter so it has to be done by hand. After some experimenting, the below instructions are the easiest way to describe the rectangle edges so that they can be easily drawn. The y coordinate and the start and end x coordinates of the horizontal lines are listed in increasing y order.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://2.bp.blogspot.com/-aEET3IpMp4c/WH4TlbF0fWI/AAAAAAAAkGc/L9tTzjEYm48PLAii_uHyyVIDs0kge1kVgCLcB/s1600/5_Instruction1.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Coordinates" border="0" height="400" src="https://2.bp.blogspot.com/-aEET3IpMp4c/WH4TlbF0fWI/AAAAAAAAkGc/L9tTzjEYm48PLAii_uHyyVIDs0kge1kVgCLcB/s400/5_Instruction1.png" title="Coordinates" width="241" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Stats and Horizontal lines</td></tr>
</tbody></table>
<br />
The same process is repeated for the vertical lines as well.<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://2.bp.blogspot.com/-H7a1eAyb9qc/WH4TpCliY9I/AAAAAAAAkGg/CKbJ6sFFJcQgGuxP6cOWQ4eGywJxCXp8ACLcB/s1600/6_Instruction2.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Coordinates" border="0" height="400" src="https://2.bp.blogspot.com/-H7a1eAyb9qc/WH4TpCliY9I/AAAAAAAAkGg/CKbJ6sFFJcQgGuxP6cOWQ4eGywJxCXp8ACLcB/s400/6_Instruction2.png" title="Coordinates" width="300" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Vertical lines</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
Take the piece of cardboard that you plan to use and draw a base line in the direction of the x axis. At each end of this line draw perpendicular guides in the direction of the y axis. Along each of these lines mark all the y coordinates from the horizontal line list using the base line as the zero point. You can then draw the line segments in the following manner. 77.0 , (84.0 - 124.5) means place a ruler on the 77.0 marks you would have drawn in the last step with the 0 mark on the left guide. Then draw a line from 84.0 to 124.5 on the ruler. By working through the list the design will gradually appear. The vertical list is supplied just to be complete and isn't really needed as the ends of the horizontal lines can be joined to form the rectangles.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-xrFJrn7yFns/WH4Tty4SXdI/AAAAAAAAkGk/RSZbTy4F4z4pcYKACTzAS5Vw66UzlAtYACLcB/s1600/7_Guides.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="guide" border="0" height="400" src="https://3.bp.blogspot.com/-xrFJrn7yFns/WH4Tty4SXdI/AAAAAAAAkGk/RSZbTy4F4z4pcYKACTzAS5Vw66UzlAtYACLcB/s400/7_Guides.jpg" title="guide" width="292" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Edge guides</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
The layout looks like the SVG file so everything worked out OK.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://2.bp.blogspot.com/-qFKjNywMTw4/WH4T3Db6jFI/AAAAAAAAkGs/hS46aluqy2cm6YzG7hbuX61pomqT_S7QACLcB/s1600/8_Rectangles.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Box Plan" border="0" height="480" src="https://2.bp.blogspot.com/-qFKjNywMTw4/WH4T3Db6jFI/AAAAAAAAkGs/hS46aluqy2cm6YzG7hbuX61pomqT_S7QACLcB/s640/8_Rectangles.jpg" title="Box Plan" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Box to cut out</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
The bend lines can be perforated with a tool like the one below that's used for transferring dressmaking patterns.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-NR2ZlEoxuBo/WH4T82vuSwI/AAAAAAAAkGw/e2y49wyDUpcgDpjk47OW7kdoTGYk2uCrACLcB/s1600/9_Scoring.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Perforated Cardboard" border="0" height="334" src="https://3.bp.blogspot.com/-NR2ZlEoxuBo/WH4T82vuSwI/AAAAAAAAkGw/e2y49wyDUpcgDpjk47OW7kdoTGYk2uCrACLcB/s640/9_Scoring.jpg" title="Perforated Cardboard" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Perforated Bend Lines</td></tr>
</tbody></table>
<br />
Cut out the outlines with a scalpel.<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-W1YfEbD2KfE/WH4UBA-MFKI/AAAAAAAAkG0/HVNJA4djLQ4i0HsdtwLyoFaCpjp8Xml-gCLcB/s1600/10_CutOut.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="422" src="https://4.bp.blogspot.com/-W1YfEbD2KfE/WH4UBA-MFKI/AAAAAAAAkG0/HVNJA4djLQ4i0HsdtwLyoFaCpjp8Xml-gCLcB/s640/10_CutOut.jpg" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Flattened box</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
When folded together everything works quite well. You can see in the image below what my intention was. The top extends over to cover the entire top and although not necessary is a fun little design challenge.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-tGs2Mkn5J-E/WH4UF777PEI/AAAAAAAAkG4/kszXY47suFQ3elWl3AR0RXmYHLeLkTBfgCLcB/s1600/11_BoxCorner.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Cardboard Box" border="0" height="640" src="https://3.bp.blogspot.com/-tGs2Mkn5J-E/WH4UF777PEI/AAAAAAAAkG4/kszXY47suFQ3elWl3AR0RXmYHLeLkTBfgCLcB/s640/11_BoxCorner.jpg" title="Cardboard Box" width="596" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Top overlap</td></tr>
</tbody></table>
<br />
As it's a tight fit, the box needs to be taped together to stop it springing open.<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-PRzsYsTjsUw/WH4UKfCQ_1I/AAAAAAAAkG8/ohtd4dC80_cGhubVVJGuFMyyiaSxh7OqwCLcB/s1600/12_Box.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Cardboard Box" border="0" height="572" src="https://4.bp.blogspot.com/-PRzsYsTjsUw/WH4UKfCQ_1I/AAAAAAAAkG8/ohtd4dC80_cGhubVVJGuFMyyiaSxh7OqwCLcB/s640/12_Box.jpg" title="Cardboard Box" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Assembled Box</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
Everything seems to fit nicely. A little tweaking could make things better, but I'm happy with it. In the end the fit all comes down to how accurately the template is drawn and bent. Folding across the corrugations is easy to get right, but folding in the same direction as the corrugations is hard and I need to come up with a better way to do it. When folding with the corrugation it's not uncommon for the fold to follow the middle of the corrugation. This could be a couple mm away from from the line.</div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://gist.github.com/GrantTrebbin/7cb290b91f2192a2551339e8b053c2f7"><img border="0" height="131" src="https://2.bp.blogspot.com/-KgNTjBaX_Ik/WH4hAn4XTbI/AAAAAAAAkHU/8Y3Xl7YSWfYk1yxBh-1UKiyOsPX7eM_xACLcB/s320/GitHub_Logo.png" style="margin-left: auto; margin-right: auto;" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;"><a href="https://gist.github.com/GrantTrebbin/7cb290b91f2192a2551339e8b053c2f7">Get The Code!</a></td></tr>
</tbody></table>
<br />
.Grant Trebbinhttp://www.blogger.com/profile/13253301568478517009noreply@blogger.com0Brisbane QLD, Australia-27.4697707 153.02512350000006-28.3721187 151.73423000000005 -26.5674227 154.31601700000007tag:blogger.com,1999:blog-3153881528840143069.post-32982668404098763312017-01-05T22:25:00.000+10:002017-01-05T22:38:52.983+10:00Designing Homemade Cardboard Boxes in 3D CAD<div style="text-align: justify;">
I'm currently selling my old phone on eBay and I needed a sturdy box for shipping. I could buy one, but why waste money on a box when I can get my hands on cardboard for free. It was also important to make the package as small as possible to keep my postage fees low. So the obvious choice was to make my own.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
When I was young I used to make cardboard boxes for everything (That's right I was just as exciting then as I am now). They were simplistic and held together with staples, but never anything too complicated. So I thought that this would be a good opportunity to up my game and emulate how the professionals do it.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
I don't know the name of the box I'm trying to make, but I'm certain you've seen one before. Quarter circle shaped flaps on the lid slide into the sides, locking everything together. Let's work backwards and start with some photos of the final product.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://2.bp.blogspot.com/-8H_xUkrljps/WG4dTajLNWI/AAAAAAAAj5s/pvyrm826p0wa9GDkssqYuW1eVTAUvxfkgCEw/s1600/BoxPhoto1.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Cardboard Box" border="0" height="593" src="https://2.bp.blogspot.com/-8H_xUkrljps/WG4dTajLNWI/AAAAAAAAj5s/pvyrm826p0wa9GDkssqYuW1eVTAUvxfkgCEw/s640/BoxPhoto1.jpg" title="Cardboard Box" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Final Box</td></tr>
</tbody></table>
.<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-BrnjzIzCAHU/WG4dhc7r4PI/AAAAAAAAj5s/aoklEyewOAMHcF5x6OgBUzxVfI_Cv0KogCEw/s1600/BoxPhoto3.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Cardboard Box" border="0" height="223" src="https://4.bp.blogspot.com/-BrnjzIzCAHU/WG4dhc7r4PI/AAAAAAAAj5s/aoklEyewOAMHcF5x6OgBUzxVfI_Cv0KogCEw/s400/BoxPhoto3.jpg" title="Cardboard Box" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Quarter Circle Flaps</td></tr>
</tbody></table>
.<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-cjJPRnH12u4/WG4dpnvmZoI/AAAAAAAAj5g/hTdvMjhu3YoWLvRK-CTZDglcP0_ccOPowCEw/s1600/BoxPhoto2.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Cardboard Box" border="0" height="213" src="https://4.bp.blogspot.com/-cjJPRnH12u4/WG4dpnvmZoI/AAAAAAAAj5g/hTdvMjhu3YoWLvRK-CTZDglcP0_ccOPowCEw/s400/BoxPhoto2.jpg" title="Cardboard Box" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Side Slots</td></tr>
</tbody></table>
<div style="text-align: justify;">
I'm quite happy with the result, but a few bits were cut off during assembly to make things fit. I assume that this was due to the inaccurate way I transferred the pattern to the cardboard. Tacking it onto the cardboard and scoring it with my wood marking knife was rough but worked.. My end goal was the template below that was transferred onto scrap cardboard and cut out to make the box.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/---511Yf7AdM/WG4d3wzQ9lI/AAAAAAAAj5k/qRCaE5gHNPM_DsVEcRgVF7A5y3xhSyo-ACEw/s1600/Layout.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Template" border="0" height="449" src="https://4.bp.blogspot.com/---511Yf7AdM/WG4d3wzQ9lI/AAAAAAAAj5k/qRCaE5gHNPM_DsVEcRgVF7A5y3xhSyo-ACEw/s640/Layout.png" title="Template" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">2D Cardboard Box Template</td></tr>
</tbody></table>
<div style="text-align: justify;">
To generate the template I used Fusion 360 from Autodesk. Before starting, four parameters were specified, the thickness of the cardboard, the height, width, and depth of the box. By using these parameters for dimensions, the design can be altered later.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
The process is simple but frustrating. Make 3D components for each part of the box and then define how they join together. They don't have to be the right size, as long as they are close you can change them later. Defining the joins is the hard part due to the software being uncooperative. Once you have a 3D version of the template you can generate a 2D version to print.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-w9s3WTnCeL4/WG4deCjxpbI/AAAAAAAAj5s/6QX3atn8XholtaTrFGmd66pQPV_dfMx0gCEw/s1600/Box1.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="488" src="https://3.bp.blogspot.com/-w9s3WTnCeL4/WG4deCjxpbI/AAAAAAAAj5s/6QX3atn8XholtaTrFGmd66pQPV_dfMx0gCEw/s640/Box1.jpg" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">3D Cardboard Box Template</td></tr>
</tbody></table>
<div style="text-align: justify;">
The first thing you will need to think about is how to model bending cardboard. To me, a good approximation was to assume that the midpoint of the material acts as a pivot point. In the image below you can see the bend between the back (red) and top (yellow) of the box. This means that when laid out flat they will meet in a butt joint and be easy to mark out. You can then move forward by defining all joints between components using this assumption. Your mileage may vary, but this seems to have worked for me.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-pHOuQ1lD4Dk/WG4d9A9_UGI/AAAAAAAAj5o/uOmhyNvPcqwaaoTUpmf_iDjLycztwuPFQCEw/s1600/Box10.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="473" src="https://1.bp.blogspot.com/-pHOuQ1lD4Dk/WG4d9A9_UGI/AAAAAAAAj5o/uOmhyNvPcqwaaoTUpmf_iDjLycztwuPFQCEw/s640/Box10.jpg" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Pivot Point Of The Faces</td></tr>
</tbody></table>
Now for the "fun" part. Using the CAD package, assemble the box as you would in the real world by bending each joint one by one. As you do this, make sure parts don't interfere with each other. You may have to resize some.<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-cQHoAZQ0qPc/WG4e6_GqO0I/AAAAAAAAj54/K6IWtAYEFF0mhfgWh2jiFbfO0kwzvB_VQCLcB/s1600/Box2.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Assemble a Box" border="0" height="258" src="https://1.bp.blogspot.com/-cQHoAZQ0qPc/WG4e6_GqO0I/AAAAAAAAj54/K6IWtAYEFF0mhfgWh2jiFbfO0kwzvB_VQCLcB/s400/Box2.jpg" title="Assemble a Box" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Fold Up The Sides</td></tr>
</tbody></table>
.<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-O_nEAOpFjSg/WG4fAdfcZ4I/AAAAAAAAj58/bwjhiBydoaUvxUFyTlfuZj0z789iganvACLcB/s1600/Box3.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Assemble a Box" border="0" height="276" src="https://3.bp.blogspot.com/-O_nEAOpFjSg/WG4fAdfcZ4I/AAAAAAAAj58/bwjhiBydoaUvxUFyTlfuZj0z789iganvACLcB/s400/Box3.jpg" title="Assemble a Box" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Fold In The Internal Base Flaps</td></tr>
</tbody></table>
.<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-G1TjysoVMko/WG4fH1XbpLI/AAAAAAAAj6A/ansx03AoeMwA70rFlxOKZQ-TUU3SnoHyACLcB/s1600/Box4.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Assemble a Box" border="0" height="272" src="https://4.bp.blogspot.com/-G1TjysoVMko/WG4fH1XbpLI/AAAAAAAAj6A/ansx03AoeMwA70rFlxOKZQ-TUU3SnoHyACLcB/s400/Box4.jpg" title="Assemble a Box" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Fold Up The Side Flaps</td></tr>
</tbody></table>
.<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-u_P9LhOHkAs/WG4fRNoRWeI/AAAAAAAAj6E/l_Psa3EPprEEk0lFF0-UqAL3ZBs6H749QCLcB/s1600/Box5.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Assemble a Box" border="0" height="400" src="https://4.bp.blogspot.com/-u_P9LhOHkAs/WG4fRNoRWeI/AAAAAAAAj6E/l_Psa3EPprEEk0lFF0-UqAL3ZBs6H749QCLcB/s400/Box5.jpg" title="Assemble a Box" width="391" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Fold The Side Flaps Into the Box</td></tr>
</tbody></table>
.<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-zT5b1bPkDK8/WG4ffOqFv5I/AAAAAAAAj6I/OfDjqwZbG2Ik6j5qSKRG0SXjM3P_ERSbACLcB/s1600/Box6.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Assemble a Box" border="0" height="360" src="https://3.bp.blogspot.com/-zT5b1bPkDK8/WG4ffOqFv5I/AAAAAAAAj6I/OfDjqwZbG2Ik6j5qSKRG0SXjM3P_ERSbACLcB/s640/Box6.jpg" title="Assemble a Box" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Fold the Inner Side Flaps Into The Box Leaving Slots</td></tr>
</tbody></table>
.<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://2.bp.blogspot.com/-KcOZD5NHDho/WG4fkTKudPI/AAAAAAAAj6Q/dn0HffCFlQs3PomhAyDB0ILTZMd11vvXACLcB/s1600/Box7.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Assemble a Box" border="0" height="156" src="https://2.bp.blogspot.com/-KcOZD5NHDho/WG4fkTKudPI/AAAAAAAAj6Q/dn0HffCFlQs3PomhAyDB0ILTZMd11vvXACLcB/s400/Box7.jpg" title="Assemble a Box" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Fold The Top Down</td></tr>
</tbody></table>
.<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-Mjrsl-b8X8M/WG4fs65TsqI/AAAAAAAAj6U/v8iS_ZmQGxEUoNZF_QHkyTitBLALRe4WACLcB/s1600/Box8.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Assemble a Box" border="0" height="231" src="https://4.bp.blogspot.com/-Mjrsl-b8X8M/WG4fs65TsqI/AAAAAAAAj6U/v8iS_ZmQGxEUoNZF_QHkyTitBLALRe4WACLcB/s400/Box8.jpg" title="Assemble a Box" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Fold In The Ears On The Sides</td></tr>
</tbody></table>
.<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-NCg58jdgvPM/WG4f2fhPMKI/AAAAAAAAj6c/54fd4ZDPGa0HtWB0E1yWw_vKEVdTeMxaACLcB/s1600/Box9.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Assemble a Box" border="0" height="285" src="https://4.bp.blogspot.com/-NCg58jdgvPM/WG4f2fhPMKI/AAAAAAAAj6c/54fd4ZDPGa0HtWB0E1yWw_vKEVdTeMxaACLcB/s400/Box9.jpg" title="Assemble a Box" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Insert The Ears Into The Slots</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
I think the results are pretty good. If the cardboard I was using was flatter and I had transferred, cut, and bent the pattern with more care I think the results would be even better. It would be great to get a pen plotter to draw the outline. I kind of joke about going overboard and spending too much time on this but it was a conscious decision. I got some more practice in 3D CAD and because the model is parametric it can be easily reused for other purposes. At least the box from my computer case is being put to good use.<br />
<br />
There was meant to be a nifty little animation of how assemble the box to go with this post but the motion study feature of Fusion 360 is a dumpster fire. Que sera sera.</div>
Grant Trebbinhttp://www.blogger.com/profile/13253301568478517009noreply@blogger.com0Brisbane QLD, Australia-27.4697707 153.02512350000006-28.3721187 151.73423000000005 -26.5674227 154.31601700000007tag:blogger.com,1999:blog-3153881528840143069.post-67630171153334132412016-12-24T17:51:00.000+10:002016-12-24T17:51:54.289+10:00LED Bunker Light TeardownI recently picked up this LED bunker light for $33 and I thought it'd make an interesting tear down.<br />
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-1RGrDXKoSQc/WF3HC0caqgI/AAAAAAAAjvo/SQbn-jAAsAsQwi2GiSxbr0tkEtOdjeyQQCLcB/s1600/1_BunkerLight.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Bunker Light" border="0" height="550" src="https://3.bp.blogspot.com/-1RGrDXKoSQc/WF3HC0caqgI/AAAAAAAAjvo/SQbn-jAAsAsQwi2GiSxbr0tkEtOdjeyQQCLcB/s640/1_BunkerLight.jpg" title="Bunker Light" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">AT5700 bunker light</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
When you remove the diffuser from the front the first thing you see is the PCB that holds the 32 LEDs. Ideally you're meant to be able to loosen the screws and turn the PCB slightly and then lift it out, the only problem with that is that there isn't enough room to get your fingers down the side of the circuit board. As it took me a couple of minutes to remove the PCB I'd suggest that in their next design iteration they route some indentations into the edge to allow you to hold onto the board.</div>
<div style="text-align: justify;">
<br /></div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-d7-alHdabAY/WF3HICUZA8I/AAAAAAAAjvs/HFNhq7h902gIjsPaj4KJEgu6-iTU_dfTACLcB/s1600/2_LED_PCB.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="LED PCB" border="0" height="592" src="https://3.bp.blogspot.com/-d7-alHdabAY/WF3HICUZA8I/AAAAAAAAjvs/HFNhq7h902gIjsPaj4KJEgu6-iTU_dfTACLcB/s640/2_LED_PCB.jpg" title="LED PCB" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Surface mount LEDs</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
The light is just a low power bunker light for non task illumination and is rated for outdoor and indoor use.</div>
<div style="text-align: justify;">
<br /></div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-5hln13wUbj4/WF3HNTB2m8I/AAAAAAAAjvw/AiFIUd4rHtM4Mafd7LkVA15wIvmNp0OMQCLcB/s1600/3_ElectricalSpecs2.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Specifications" border="0" height="291" src="https://1.bp.blogspot.com/-5hln13wUbj4/WF3HNTB2m8I/AAAAAAAAjvw/AiFIUd4rHtM4Mafd7LkVA15wIvmNp0OMQCLcB/s400/3_ElectricalSpecs2.jpg" title="Specifications" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Box specifications</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
The LED driver is mounted to the back of the PCB and seems to be of the constant current type. It's hard to tell but I think the voltage range of 12-25 volts indicates that it will regulate the output to 350mA and vary the voltage accordingly. When measured the LEDs were drawing 350mA at 12V for a power of 4.2W. The box indicates a power draw of 6 watts so the difference is likely to be what gets wasted in the driver.</div>
<div style="text-align: justify;">
<br /></div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-HekJdENE0-w/WF3HT5fuHAI/AAAAAAAAjv0/gTuizFH6WBQ7mQkMiCaQcL8cRfWJXWGAwCLcB/s1600/4_ElectricalSpecs.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="LED Driver" border="0" height="257" src="https://3.bp.blogspot.com/-HekJdENE0-w/WF3HT5fuHAI/AAAAAAAAjv0/gTuizFH6WBQ7mQkMiCaQcL8cRfWJXWGAwCLcB/s400/4_ElectricalSpecs.jpg" title="LED Driver" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">LED driver specifications</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
The light was chosen because of its small size, almost too small in fact. As we'll see later, the 70mm thickness doesn't leave much space for cabling.</div>
<div style="text-align: justify;">
<br /></div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-c22JGfVCRz4/WF3HbvEhLAI/AAAAAAAAjv4/lF8-tnB8M1oB4S6RpDBvUkF8zbErwH4UQCLcB/s1600/5_Dimensions.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Dimensions" border="0" height="200" src="https://3.bp.blogspot.com/-c22JGfVCRz4/WF3HbvEhLAI/AAAAAAAAjv4/lF8-tnB8M1oB4S6RpDBvUkF8zbErwH4UQCLcB/s320/5_Dimensions.jpg" title="Dimensions" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Dimensions</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
The connector that supplies power to the board has a cover over its soldered terminals on the front side of the panel. I assume that this is to prevent shorting occurring and not a safety thing as the voltages on the board are low and still accessible on the sides of the surface mount LEDs. It's a good idea but I wish they'd put the same amount of thought into the installation process as it's quite hard. Ripping a surface mount component off a board isn't that hard to do.</div>
<div style="text-align: justify;">
<br /></div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://2.bp.blogspot.com/-jueGb8UH0Mk/WF3Hg8uuJrI/AAAAAAAAjv8/Ze2eaVZOkKUHNi4aMo4qxA8UcrmvorpgwCLcB/s1600/6_Connector_Cover.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="LED PCB" border="0" height="263" src="https://2.bp.blogspot.com/-jueGb8UH0Mk/WF3Hg8uuJrI/AAAAAAAAjv8/Ze2eaVZOkKUHNi4aMo4qxA8UcrmvorpgwCLcB/s320/6_Connector_Cover.jpg" title="LED PCB" width="320" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Insulator over connector solder points</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
The main problem I have is that the driver is mounted to the back of the LED PCB. During installation you have to first connect the cabling to the terminal block. This means that you need to leave about 8 inches of extra wire so you can get a screw driver in there before putting the board into the base and if you can't shove that extra cable into a wall or wherever the light is going, it has to be curled up inside the fitting and that's hard as there is only about 30mm of space behind the board. I think a better solution would have been to mount the driver to the base of the fixture so that the driver can be wired in first and then connect the LED PCB via the header connector to the driver. The connector on the PCB could be also moved to the front side to allow connection after mounting the LED board. There is plenty of room, you just bring a small cable up the gap beside the PCB and connect it on the front side.</div>
<div style="text-align: justify;">
<br /></div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-G-KtVnqoDvw/WF3HlmmVCdI/AAAAAAAAjwE/D4rUsvy19600C5WyxJ1akzT9diCbcdL7QCLcB/s1600/7_PCB_Back.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="LED PCB" border="0" height="585" src="https://4.bp.blogspot.com/-G-KtVnqoDvw/WF3HlmmVCdI/AAAAAAAAjwE/D4rUsvy19600C5WyxJ1akzT9diCbcdL7QCLcB/s640/7_PCB_Back.jpg" title="LED PCB" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Rear of the PCB as it sits upside down in the base</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
Curious about how the LEDs were arranged I mapped out the layout of the board. In the image below each different section of copper track has its own colour to clearly identify them.</div>
<div style="text-align: justify;">
<br /></div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-11_1lgtH05Y/WF3HucASsHI/AAAAAAAAjwI/75s43mwD4JYgBYwuNqrGdvRE8HCQ1gdSgCLcB/s1600/8_LEDPCB.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="LED PCB" border="0" height="640" src="https://3.bp.blogspot.com/-11_1lgtH05Y/WF3HucASsHI/AAAAAAAAjwI/75s43mwD4JYgBYwuNqrGdvRE8HCQ1gdSgCLcB/s640/8_LEDPCB.jpg" title="LED PCB" width="634" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Electrical layout of PCB</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
This shows that the 32 LEDs are arranged in 4 serially connected groups of 8 parallel lights. I would usually have an issue with this because there isn't any form of load balancing, but I think the lights are under-driven enough that it isn't a concern. I'll take a minute to explain that better. If the LED driver is generating 12 volts with a constant current of 350 mA, you would assume that each component is getting 43.75mA at 3V, but due to manufacturing tolerances it's unlikely that the 350mA will get evenly split between the 8 LEDs in each group. You then have a situation where one will be drawing more current than the others and if there isn't enough of a safety factor in the design it will eventually fail. When this happens, the 350 mA will now be divided between the 7 remaining lights and another will fail this will continue until an entire group fails. The reason that I'm not too concerned about this is that I think the packages are 2835 LEDs and they can usually handle more than the (0.04375 x 3) 131.25 mW per device. The forward voltage of a white LED is usually considered to be above 3V. This is what makes me think that to get the reliability they wanted, all they had to do was add extra LEDs to split the current and under drive each chip. You would probably find that if there were only 7 LEDs in each group the higher current would cause the forward voltage to increase and instead of regulating at 12V, the driver may go to 13V.</div>
<div style="text-align: justify;">
<br /></div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://2.bp.blogspot.com/-L3r2dAR2LAE/WF3H6s8c4GI/AAAAAAAAjwQ/hlG3Hfv8zBoymGaJ_npWszZZC0iVyv7SACLcB/s1600/9_Schematic.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img alt="Schematic" border="0" height="345" src="https://2.bp.blogspot.com/-L3r2dAR2LAE/WF3H6s8c4GI/AAAAAAAAjwQ/hlG3Hfv8zBoymGaJ_npWszZZC0iVyv7SACLcB/s400/9_Schematic.png" title="Schematic" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">LED schematic</td></tr>
</tbody></table>
<br />
It's not too bad for $33 but I think the design could be improved with only some minor adjustments.Grant Trebbinhttp://www.blogger.com/profile/13253301568478517009noreply@blogger.com0Brisbane QLD, Australia-27.4697707 153.02512350000006-28.3721187 151.73423000000005 -26.5674227 154.31601700000007tag:blogger.com,1999:blog-3153881528840143069.post-66997113022676526752016-12-20T23:03:00.000+10:002016-12-20T23:03:10.637+10:00Cron Based Discrete Event Simulator<div style="text-align: justify;">
In my last post I showed how to <a href="http://www.grant-trebbin.com/2016/12/finding-all-cron-events-between-two.html">use the croniter package to find all the cron events that occur between two dates</a>. I wanted to see if it was suitable for integration into my discrete event simulator, and after a overhaul of the original simulator that's exactly what I've done. To demonstrate the functionality it's helpful to have a real world scenario to model.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
<u>Scenario</u></div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
A programmer is addicted to energy drinks and every night at 8 pm they put all the empty cans on their desk in the bin. Some days are more stressful than others so the number of cans taken out is a random number between 0 and 10 included. The rubbish bin is emptied every Monday morning at 8 am. The programmer only works from home January through April but the number of cans in the bin needs to be determined between December to May. The amount of rubbish in the bin needs to be monitored every 30 minutes.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
The first step is to define tasks that need to be performed. They are simply functions that accept a variable describing the simulation environment.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-BJ6bvQ9EkqU/WFkhEGokWbI/AAAAAAAAjss/1-A7a89DBuQMqx0h300fUTDSuPr2bamDwCLcB/s1600/RubbishDemo1.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="https://1.bp.blogspot.com/-BJ6bvQ9EkqU/WFkhEGokWbI/AAAAAAAAjss/1-A7a89DBuQMqx0h300fUTDSuPr2bamDwCLcB/s1600/RubbishDemo1.png" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Define Events</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
The parameters to initialise the simulator include a start time, an end time, and a default location. The times are made up of a year, month, day of the month, hour, minute, second and an optional location that is a valid entry for the pytz package. If no location is supplied for the times, the default location is used. Other parameters specific to the state of the simulation are included as parameters. Locations are needed as the underlying simulator uses unix timestamps as the timebase. This prevents ambiguous time due to daylight saving and different time zones. Essentially a time and date is useless information without a location.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-IRfddUXyn7k/WFkk8-16nwI/AAAAAAAAjtI/dZZVDIqn4JY1x7dMcKe1BgtnFcD2Cf8YgCLcB/s1600/RubbishDemo0.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="https://3.bp.blogspot.com/-IRfddUXyn7k/WFkk8-16nwI/AAAAAAAAjtI/dZZVDIqn4JY1x7dMcKe1BgtnFcD2Cf8YgCLcB/s1600/RubbishDemo0.png" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Initialise the simulator</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
The tasks are scheduled to run via a cron string and a location for the event. If a location isn't supplied the default simulation location is used. You can also set a range for the cron events to run. In the example below the log_data and the empty_rubbish tasks don't have start and end times so they run for the entire simulation. The take_out_trash task runs for a shorter period of time and has defined start and end times. The simulation is then run with the results logged to file.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://2.bp.blogspot.com/-ZG_DX_sSt1E/WFkhJCIIQqI/AAAAAAAAjsw/4aRw6nTcsY4AyM5KS6Ex3nzEMCBZPR6WwCLcB/s1600/RubbishDemo2.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" src="https://2.bp.blogspot.com/-ZG_DX_sSt1E/WFkhJCIIQqI/AAAAAAAAjsw/4aRw6nTcsY4AyM5KS6Ex3nzEMCBZPR6WwCLcB/s1600/RubbishDemo2.png" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Schedule Events</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
The results show that on one occasion there are at more than 50 cans in the bin. This could be used to determine the size of a bin to buy if the current one is too small. Let's say you have a bin that takes only 40 cans, it wouldn't be too much trouble to calculate the percentage of the time that there are more than 40 cans to be placed in it. You may decide that it's acceptable for the bin to be overfull for a certain percentage of the time. It's all about quantifying data from the simulation and using it to make informed decisions instead of just going by your gut.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-hj_qnk6aajk/WFkhNYz9rzI/AAAAAAAAjs0/cVse4WM6uCMWvHTZ7muvmTB4tj7Sz1gSQCLcB/s1600/RubbishBinLevel.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="298" src="https://4.bp.blogspot.com/-hj_qnk6aajk/WFkhNYz9rzI/AAAAAAAAjs0/cVse4WM6uCMWvHTZ7muvmTB4tj7Sz1gSQCLcB/s640/RubbishBinLevel.png" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Simulation Results</td></tr>
</tbody></table>
<br />
This is a work in progress and there are parts I want to improve, and although this scenario is simple I hope I've demonstrated the value of simulating a situation.<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><span style="margin-left: auto; margin-right: auto;"><a href="https://github.com/GrantTrebbin/DiscreteEventSimulator"><img border="0" height="131" src="https://4.bp.blogspot.com/-qSZxdhLHR4Q/WFkhZn9r5jI/AAAAAAAAjs4/WRse6Sh5ZhAubcFTkyYXZu-Z4VjhtrgLgCLcB/s320/GitHub_Logo.png" width="320" /></a></span></td></tr>
<tr><td class="tr-caption" style="text-align: center;"><a href="https://github.com/GrantTrebbin/DiscreteEventSimulator">Get the Code!</a></td></tr>
</tbody></table>
<br />
<br />Grant Trebbinhttp://www.blogger.com/profile/13253301568478517009noreply@blogger.com0Brisbane QLD, Australia-27.4697707 153.02512350000006-28.3721187 151.73423000000005 -26.5674227 154.31601700000007tag:blogger.com,1999:blog-3153881528840143069.post-75301038560923873062016-12-04T23:54:00.000+10:002016-12-04T23:57:00.080+10:00Finding All Cron Events Between Two Times With Python and Croniter<div style="text-align: justify;">
I've been playing around with the idea of a discrete event simulator for a while but I needed a clear way to specify when events will occur, particularly recurring ones. In situations like this I try to use standards that already exist, so the cron format seemed ideal. The goal is to supply a start and end time with a cron string and have all the events in between automatically generate and with the help of the croniter package this a relatively painless process.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
I've thrown together a quick demonstration of how I intend to use the package including using datetime objects with timezones attached. I'm not sure if I'll eventually use timezones or not but I wanted to make sure I knew how it worked.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
The example below calculates all the cron events that occur in December 2016. In this case cron events occur at 8 am on Monday, Tuesday and Thursday.</div>
<br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">from croniter import croniter</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">from datetime import datetime</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">import pytz</span><br />
<div>
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;"><br /></span></div>
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">simulation_timezone = pytz.timezone('Australia/Brisbane')</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">simulation_start_time = simulation_timezone.localize(datetime</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;"> (2016, 12, 1, 0, 0, 0))</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">simulation_end_time = simulation_timezone.localize(datetime</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;"> (2016, 12, 31, 23, 59, 59))</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;"><br /></span>
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">cron_iterator = croniter('00 8 * * 1-2,4', simulation_start_time)</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;"><br /></span>
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">print("---------start time---------")</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">print(simulation_start_time)</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">print(simulation_start_time.timestamp())</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">print("-----------events-----------")</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;"><br /></span>
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">while True:</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;"> next_event = cron_iterator.get_next(datetime)</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;"> if next_event > simulation_end_time:</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;"> break</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;"> print(next_event)</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;"> print(next_event.timestamp())</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;"><br /></span>
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">print("----------end time----------")</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">print(simulation_end_time)</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">print(simulation_end_time.timestamp())</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">print("----------------------------")</span><br />
<br />
<div style="text-align: justify;">
You start by defining a base time, in this case it is simulation_start_time. A croniter iterator can then be declared. This is done by supplying a cron string and a base time. You can now step forward and backward through events with the get_next and get_prev methods. These return a float or a datetime object depending on what type you pass as an argument.</div>
<br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">---------start time---------</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">2016-12-01 00:00:00+10:00</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">1480514400.0</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">-----------events-----------</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">2016-12-01 08:00:00+10:00</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">1480543200.0</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">2016-12-05 08:00:00+10:00</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">1480888800.0</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">2016-12-06 08:00:00+10:00</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">1480975200.0</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">2016-12-08 08:00:00+10:00</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">1481148000.0</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">2016-12-12 08:00:00+10:00</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">1481493600.0</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">2016-12-13 08:00:00+10:00</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">1481580000.0</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">2016-12-15 08:00:00+10:00</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">1481752800.0</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">2016-12-19 08:00:00+10:00</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">1482098400.0</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">2016-12-20 08:00:00+10:00</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">1482184800.0</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">2016-12-22 08:00:00+10:00</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">1482357600.0</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">2016-12-26 08:00:00+10:00</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">1482703200.0</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">2016-12-27 08:00:00+10:00</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">1482789600.0</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">2016-12-29 08:00:00+10:00</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">1482962400.0</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">----------end time----------</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">2016-12-31 23:59:59+10:00</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">1483192799.0</span><br />
<span style="color: #6aa84f; font-family: "courier new" , "courier" , monospace;">----------------------------</span><br />
<br />
<div style="text-align: justify;">
By stepping through events until the end time, all events are found. I'm still working on making everything more readable and clearer for the end user, but this gets me 90% of the way there.</div>
Grant Trebbinhttp://www.blogger.com/profile/13253301568478517009noreply@blogger.com0Brisbane QLD, Australia-27.4697707 153.02512350000006-28.3721187 151.73423000000005 -26.5674227 154.31601700000007tag:blogger.com,1999:blog-3153881528840143069.post-86619324431656963052016-11-21T23:04:00.001+10:002016-11-21T23:04:30.203+10:00How Can Polls Be Wrong and Right At The Same Time?<div style="text-align: justify;">
The results of the 2016 Presidential election have surprised many and caused people to call into question how accurate polls are. There are endless think pieces about how the polls were wrong and how people were lulled into a false sense of certainty, but what seems to get overlooked in all of these conversations is the probabilistic nature of polling. That's what I want to delve into a little deeper and understand better.</div>
<br />
<div style="text-align: justify;">
Before going too far, it should be said that conducting an unbiased poll is an incredibly hard thing to do. You need to sample a representative cross section of the electorate, and that's becoming harder as the available ways to contact people are fragmenting due to technology. There are many other causes for polls giving unexpected results, but what I'm really interested in is what the underlying mathematics tells us about the results of a poll when all these other effects are stripped away.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
From this point on we're going to look at a simplistic poll where we ask people if they prefer Apples or Bananas, and we'll consider a response for an Apple as positive response. We also need to ask the question "what are we trying to discover with this poll?". The answer to that is we are trying to determine the proportion of the public that prefer Apples to Bananas. We don't know what that number is. It's a hidden parameter of the population that we are trying to discover through random sampling.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
Let's define some variables, do some math and take a poll. It won't be anything too formal. I'm not labelling my graphs, this is just a casual chat between friends.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
p is the probability of a positive response for an Apple</div>
<div style="text-align: justify;">
n is the number of people surveyed for the poll</div>
<div style="text-align: justify;">
k is the number of positive responses for an apple</div>
<div style="text-align: justify;">
P(k;p) is the probability of k responses given the probability of a single response is p</div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://3.bp.blogspot.com/-YCzbaRBRo_A/WDLMktXZSiI/AAAAAAAAjgI/mWBqpqLqPTIT97sgyScRy2ZO8kgwP_74gCLcB/s1600/probability.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="112" src="https://3.bp.blogspot.com/-YCzbaRBRo_A/WDLMktXZSiI/AAAAAAAAjgI/mWBqpqLqPTIT97sgyScRy2ZO8kgwP_74gCLcB/s400/probability.jpg" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Binomial pmf</td></tr>
</tbody></table>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-bQO70NI2cwU/WDLMs51-GvI/AAAAAAAAjgM/kIPsHQZ4mFc821b0gRpKiYPkeD9vG_HrgCLcB/s1600/range.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="56" src="https://4.bp.blogspot.com/-bQO70NI2cwU/WDLMs51-GvI/AAAAAAAAjgM/kIPsHQZ4mFc821b0gRpKiYPkeD9vG_HrgCLcB/s200/range.jpg" width="200" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Binomial pmf range</td></tr>
</tbody></table>
<div style="text-align: justify;">
The probability mass function for a series of Bernoulli trials is the the binomial function. In this case it is telling us the probability of a certain result given that we already know the underlying probability parameter, p. However, we don't know p, so it's more useful to look at the same equation but this time with the results of a series of trials. Given that we know the number of positive results, what is the likelihood of the parameter p being equal to a value? The new equation L(p;k) is referred to as the likelihood function, and it doesn't follow the same rules as a probability density function, but it does allow comparison of relative likelihoods.</div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-rvrXwHCHdlw/WDLNHtsnClI/AAAAAAAAjgQ/sV08QGGta6IpyOd_mMatab_HYe8iXGbYQCLcB/s1600/likelihood.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="91" src="https://4.bp.blogspot.com/-rvrXwHCHdlw/WDLNHtsnClI/AAAAAAAAjgQ/sV08QGGta6IpyOd_mMatab_HYe8iXGbYQCLcB/s400/likelihood.jpg" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Likelihood Function</td></tr>
</tbody></table>
<div style="text-align: justify;">
For example: 100 people are polled and 35 people say that they prefer apples to bananas. This gives a likelihood function of:</div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-n2C_ZSIMfOI/WDLdIwu0eFI/AAAAAAAAjgk/laTgSRb8PaQ8aQ0e0za-HHCLHpkimcUbACLcB/s1600/likelihood1eq.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="88" src="https://4.bp.blogspot.com/-n2C_ZSIMfOI/WDLdIwu0eFI/AAAAAAAAjgk/laTgSRb8PaQ8aQ0e0za-HHCLHpkimcUbACLcB/s400/likelihood1eq.jpg" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">A poll of 100 people with 35 positive responses</td></tr>
</tbody></table>
<div style="text-align: justify;">
When the above likelihood function is graphed we get the following.</div>
<div style="text-align: justify;">
<br /></div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://1.bp.blogspot.com/-P2Ql9UTPtv8/WDLhzIL5dGI/AAAAAAAAjgw/ZYl8OMfXLT4DDi3f9EjNUEXMwRKvej8qwCLcB/s1600/likelihood1.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="448" src="https://1.bp.blogspot.com/-P2Ql9UTPtv8/WDLhzIL5dGI/AAAAAAAAjgw/ZYl8OMfXLT4DDi3f9EjNUEXMwRKvej8qwCLcB/s640/likelihood1.jpg" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">A poll of 100 people with 35 positive responses</td></tr>
</tbody></table>
<div style="text-align: justify;">
From this we can see that the relative likelihood that p is 0.35 compared to 0.3 is around twice as likely but the possibility isn't remote. We can visually see that p could be anywhere between about 0.27 and 0.43 and you wouldn't be surprised. What if we conduct more polling? Let's say we poll 300 people.</div>
<div style="text-align: justify;">
<br /></div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-S-jyOdTQChA/WDLi4rdB4oI/AAAAAAAAjg4/8XLwD1pXx4IXJtFTfR1s0uWYGwSvltXeQCLcB/s1600/likelihood2.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="448" src="https://4.bp.blogspot.com/-S-jyOdTQChA/WDLi4rdB4oI/AAAAAAAAjg4/8XLwD1pXx4IXJtFTfR1s0uWYGwSvltXeQCLcB/s640/likelihood2.jpg" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">A poll of 300 people with 105 positive responses</td></tr>
</tbody></table>
<div style="text-align: justify;">
You can now see that the peak of likely values has now tightened, and we can more confidently say that the value of p likely lies between 0.3 and 0.4. This shows how additional polling allows the margin of error to be reduced. If you're astute you may have noticed that the results of the polls don't rely on the size of the population being polled. As long as you select a representative cross section of society the size of the population is irrelevant. You may also be interested in what happens if a relatively small number of people are polled. This can be seen when you poll 20 people.</div>
<div style="text-align: justify;">
<br /></div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://4.bp.blogspot.com/-4Xu-6CnAI1A/WDLkbPs93uI/AAAAAAAAjhE/wmvBXbukhmE6z26vfBT7nod79ExR59hEgCLcB/s1600/likelihood3.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="386" src="https://4.bp.blogspot.com/-4Xu-6CnAI1A/WDLkbPs93uI/AAAAAAAAjhE/wmvBXbukhmE6z26vfBT7nod79ExR59hEgCLcB/s640/likelihood3.jpg" width="640" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">A poll of 20 people with 7 positive responses</td></tr>
</tbody></table>
<div style="text-align: justify;">
It wouldn't really surprise you if p was between 0.18 and 0.56 a pretty wide range. and doesn't reveal too much about the actual value of p. It's also interesting to note that all of the example above have 35% positive response rates and therefore p peaks at 0.35 for all surveys. Polling more people only increases confidence in our results. In reality the peak would move around a little bit with each new bit of data. However, the more people that you poll, the more confident you would be that about one in three people prefer apples to bananas.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
There is a rule of thumb for margin of error in polling that states that 100 divided by the square root of the number of respondents is equal to the percentage margin of error. So for our 3 examples above the margin of error for 20, 100, and 300 people respectively are 22%, 10% and 6%. It's not uncommon to see a political poll of 2000 respondents, and using our rule of thumb above, it would still have a margin of error of 2.2%.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
I suppose what I'm trying to get at is that even if you could remove all of the external human factors affecting the poll and you chose a perfectly random cross section of the population, your sample size will limit how accurately your poll determines the underlying parameters the population.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
For all the talk about how every polling model got the result of the Presidential election wrong, remember that the 538 model gave this outcome a one in three chance of occurring. That isn't an insignificant probability. It's true that polling methods need improvement, but in this case I think the main problem is the way probabilities are communicated to the general public are too confusing. People don't intuitively understand what percentage probabilities mean. The IPCC have this problem and even have defined terms in everyday language to communicate probabilities to the public.</div>
<div style="text-align: justify;">
<br /></div>
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="https://2.bp.blogspot.com/-IlzoI6zYZEM/WDLugEf0ENI/AAAAAAAAjhU/SstbfwCZJbku79mYh8ZGXSmb9WUX9BCrwCLcB/s1600/IPCCLikelihoodScale.jpg" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="255" src="https://2.bp.blogspot.com/-IlzoI6zYZEM/WDLugEf0ENI/AAAAAAAAjhU/SstbfwCZJbku79mYh8ZGXSmb9WUX9BCrwCLcB/s400/IPCCLikelihoodScale.jpg" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">IPCC likelihood scale</td></tr>
</tbody></table>
<div style="text-align: justify;">
I actually have some modelling problems in mind that I would like to work on one day, and until now I had always envisaged communicating them as percentages, but given the intended audience I think I might change my approach.</div>
Grant Trebbinhttp://www.blogger.com/profile/13253301568478517009noreply@blogger.com0Brisbane QLD, Australia-27.4697707 153.02512350000006-28.3721187 151.73423000000005 -26.5674227 154.31601700000007