tag:blogger.com,1999:blog-14579665030341543972015-05-30T01:49:02.566-07:00CrossCut FractalEarly versions of the fractal here described have been in use in the graphic arts industry since 1986. This algorithm finds the best way to "crosscut" full size sheets of flat stock to a smaller size with least amount of waste on an industrial knife cutter (guillotine). It is here being described for scientific value as an example of a fractal algorithm that can navigate the search space of a relatively complex real-world problem, often beyond human ability to fully solve any other way.Gary Gaulinhttp://www.blogger.com/profile/10925297296758439900noreply@blogger.comBlogger1125tag:blogger.com,1999:blog-1457966503034154397.post-10396288784695614662009-12-29T05:27:00.000-08:002010-01-01T08:35:52.521-08:00How It WorksIn as simple words possible, a <a href="http://en.wikipedia.org/wiki/Fractal" target="_blank">fractal</a> is a multi-step (<a href="http://en.wikipedia.org/wiki/Polar_coordinate_system">polar coordinate system</a>) math equation which uses recursion (iteration) to keep itself going by jumping to previously done steps that are repeated until no more such steps can be taken, to map out a multiple level 2D (or more) geometric world that much resembles something found in our world.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://3.bp.blogspot.com/_Gyn0-PcXrJY/Sz4kBtjYlHI/AAAAAAAAAuo/YdPjMQUXeII/s1600-h/2x5.JPG" imageanchor="1" style="clear: left; cssfloat: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" ps="true" src="http://3.bp.blogspot.com/_Gyn0-PcXrJY/Sz4kBtjYlHI/AAAAAAAAAuo/YdPjMQUXeII/s320/2x5.JPG" /></a><br /></div><br /><br />This fractal uses a 360 degree 4 quadrant system where the <a href="http://en.wikipedia.org/wiki/Rotation_(mathematics)" target="_blank">rotation angle</a> is a function of possible rotation of two cut sizes (example: 3.5 x 5.5) and two full sizes (example: 22 x 34) relative to each other, and with a <a href="http://en.wikipedia.org/wiki/Sine_wave" target="_blank">sine wave phase angle</a> at 0 when both sizes are as printers usually enter them (unrotated) with small dimension first as in standard paper sizes of 8.5x11, 11x17, 22x34, etc.. When rotated we get 11x8.5, 17x11, 34x22 which here changes the spiraling trajectory in the same way the rotation Angle of Cos(A) and Sin(A) is the trajectory of a point of a circle with radius of 1. The rotation angle here determines trajectory of a vector that spirals with 90 degree turns while covering the full distance of the full size sheet in the forward direction as does the knife blade that always cuts from one end to the other.<br /><br /><div style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;"><a href="http://4.bp.blogspot.com/_Gyn0-PcXrJY/Sz4h-WU6RKI/AAAAAAAAAug/wW0A5Af3M90/s1600-h/BugFound.JPG" imageanchor="1" style="clear: left; cssfloat: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" ps="true" src="http://4.bp.blogspot.com/_Gyn0-PcXrJY/Sz4h-WU6RKI/AAAAAAAAAug/wW0A5Af3M90/s320/BugFound.JPG" /></a><br /></div><div style="border-bottom: medium none; border-left: medium none; border-right: medium none; border-top: medium none;">There are often one or more empty quadrants. This is caused by all the layouts it contains having fewer out of the sheet than a layout in another found.<br /></div><br />The fractal property of self-similarity is most evident in the multiple levels of spiraling depth that are possible. Each is a new level of detail resulting in a screen of layouts (similar to each other) with the least complicated to cut usually the last to be calculated, which here puts the best at the outer four corners and on top. Because of the fractal having four points around its 360 degree polar coordinate rotation it has these four radials of 2D layout diagrams. Instead of "zooming" in or out we change the depth of spiraling, are not seeing the entire fractal all at once. How much detail is shown is here used to narrow down the field of layouts on the screen to a manageable number. This can make it difficult to recognize the crosscut algorithm as a fractal, but the four radials that must be shown for it to be easy to select a crosscut makes it necessary to recognize as such. This four quadrant property is the result of the logic of problem itself (related to rectangles having four 90 degree corners/rotations per 360 degrees of geometry) so even if the crosscutting problem could be solved without a fractal then where all possible layouts were actually found the geometry problem would still exist. Showing one layout on the screen at a time would still hide up to three more that are just as good which need to be compared to it. This has been a serious design problem that required the somewhat unorthodox approach of showing a fractal to select from.<br /><br />A fractal like this makes it easy to sort out turn directions and jogs to "square up" stock that has rough uneven edges. To do this on a knife with a blade that swings from right to left (thus pulls slippery stock to the left from under hold-down clamp when not against the left side) the stock is first jogged against the left side then push back until it just touches the back guide/gauge not caring whether it is flush. After taking a trim there is a perfect (as the machine can get it) 90 degree angle between left side of machine and blade, such that another 90 degree turn of the stock puts the angle against the back guide where the stock will (hopefully) now jog flush to both side of knife and backgauge at the same time.<br /><br /><div class="separator" style="clear: both; text-align: center;"><a href="http://www.challengemachinery.com/images/products/large/champion_370xt.jpg" imageanchor="1" style="clear: left; cssfloat: left; float: left; margin-bottom: 1em; margin-right: 1em;" target="_blank"><img border="0" height="190" ps="true" src="http://www.challengemachinery.com/images/products/large/champion_370xt.jpg" width="320" /></a><br /></div>An <a href="http://www.challengemachinery.com/products/champion370_video.htm" target="_blank">industrial knife cutter</a> like this newer model of the machine that helped inspire this fractal (result of arguments over the amount of scrap in the bins the result of poor planning) often has a programmable motorized backgauge and internal computer to enter dimensions to move to after each cut. Modern models will calculate straightcuts, where all cut sizes are in same direction. But crosscuts present a unique four quadrant geometric problem that requires a fractal representation showing all four quadrants at the same time for it to be easy to select from the viable possibilities. Where of benefit, some of the layouts might have trim all around for squaring up the stock. While others have a useful size trim in one or more corners that could be used for another job. And when the fractal is showing too much detail there can also be thousands of nonsense layouts mixed in that include ones that spiral so many times one would get dizzy cutting it, as well as waste time cutting so many differing length strips to the other dimension. <br /><br />Although having an algorithm that can immediately settle shop-floor arguments over how to best cut the stock is very welcome relief, in regular use crosscuts can add a surprising number of inherently user-unfriendly problems that must be overcome by the software developer for it to worth the time to learn to use properly then be useful on a regular basis. And without there being a tested math theorem that can determine how many out of a sheet is possible there is no way of knowing whether the algorithm is functioning as expected. In such a case the best one can do is try to do better by hand or calculator until convinced that it is 100% which is misleading when the method used to calculate is unable to find them all, in the first place. There is also the problem of nonsense layouts that appear when you reach the point where you are likely not missing any at all, which requires setting a limit to how complex of a layout to allow which causes other problems including leaving enough trim space for another cut size to fit into that the algorithm then misses because it was told not to look past that point. And with no easy way to limit the complexity of layouts it's relatively easy for a job planner with little knife experience to choose one that will have a knife operator struggling with a diagram of a complicated 4 turn crosscut just to save fifty cents worth of paper. Or worse wastes much more than that by having made a mistake while cutting and replacement stock must be reordered.<br /><br />On the other side of the equation is the fact that a hundred+ dollars worth of paper at a time is regularly loaded into a production knife where in a few minutes it's cut then another lift loaded in. On an average (for industry) sized job getting one or two more out of the sheet while cutting at a good pace can pay the knife operators weekly wages for that week (and cost of software to make finding a crosscut easy) all in one job. Unfortunately, the job planner can't usually spend all day looking for a layout that will use up the trim (not be enough square inch/mm left to get another cut size from) and many layouts have 3 or more sheets worth of wasted paper with it being impossible to get any more than that so in that case it's a waste of time to even look for a crosscut yet it is so wasteful it looks like they did not even try, which has them looking bad either way. Only way out of that situation is to have a printout from an algorithm that would have found a crosscut, where one existed. Which in turn requires a logical construct such as a fractal that reduces the dimensional complexities of crosscutting down to a testable science, and is prepared to stand whatever peer-review may exist for it.<br /><br />Since missing just one (cutable) layout which gets more out of the sheet than the fractal could find sends it back to the drawing board, a program was made for those who want to try to beat it. Doing so would not change the fact that it almost instantly finds crosscuts that we might never find with a calculator, but it would disprove the theoretical premise that the fractal is based on where geometry and 360 degree recursion should find them all. And credit will be given for finding a fault. It is being described in more than the usual detail and reported in a scientific manner to test the science, not test a sales-pitch. The goal is an algorithm that can solve a very frustrating real-world problem and all that is discovered along the way (including bugs and faults) are a part of getting there, unless of course a good testing (tentatively) proves that the fractal here described is already there.<br /><br />-Gary Gaulinhttp://www.blogger.com/profile/10925297296758439900noreply@blogger.com