{"id":8840,"date":"2022-08-21T10:42:36","date_gmt":"2022-08-21T14:42:36","guid":{"rendered":"https:\/\/blogs.mathworks.com\/cleve\/?p=8840"},"modified":"2022-11-10T18:37:15","modified_gmt":"2022-11-10T23:37:15","slug":"polygons-polyshapes-and-puzzles","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/cleve\/2022\/08\/21\/polygons-polyshapes-and-puzzles\/","title":{"rendered":"Polygons, Polyshapes and Puzzles"},"content":{"rendered":"\r\n<div class=\"content\"><!--introduction--><p>Until recently, I knew nothing about the <tt>polyshape<\/tt> object in MATLAB. Now I can use polyshape to simulate an extraordinary puzzle.<\/p><!--\/introduction--><h3>Contents<\/h3><div><ul><li><a href=\"#b44ef23f-8ee4-4710-970e-758273aef673\">Puzzles<\/a><\/li><li><a href=\"#af839423-9061-445a-abcc-33e483845857\">Not a T<\/a><\/li><li><a href=\"#fbfbf351-698a-410b-9cba-7272f394fe65\">A slice of cheese<\/a><\/li><li><a href=\"#55c27f57-400d-4f4c-8849-298407ab936f\">My first solution<\/a><\/li><li><a href=\"#87aa86ac-b133-4c46-abed-79b9b9669023\">Is this solution correct?<\/a><\/li><li><a href=\"#07004175-0ad2-4431-9504-3d9d8c33a86c\">Spoiler alert !<\/a><\/li><li><a href=\"#bbdd0ff0-9265-4089-9325-4929faa2d325\">My second solution<\/a><\/li><li><a href=\"#30e29a25-e0f0-449b-b09c-4ff8ee26a6b8\">A round peg in a square hole<\/a><\/li><li><a href=\"#19fcdc7d-f204-47d7-9e55-221680530003\">Theta<\/a><\/li><li><a href=\"#4933cc60-9813-49dd-8f8c-d822d7b9b2d2\">Polyshapes<\/a><\/li><li><a href=\"#1dcd1993-0fec-49da-87a9-4b75d997227f\">The solution<\/a><\/li><li><a href=\"#ed22add4-a328-41ed-9696-c5cebc945091\">Software<\/a><\/li><\/ul><\/div><h4>Puzzles<a name=\"b44ef23f-8ee4-4710-970e-758273aef673\"><\/a><\/h4><p>The Web site <a href=\"https:\/\/www.artofplay.com\">Art of Play<\/a>, from some folks in San Diego, has well over two-hundred puzzles.  Recently, one of their most popular puzzles, <a href=\"https:\/\/www.artofplay.com\/collections\/packing-puzzles\/products\/mighty-cheese-travel-puzzle\">Mighty Cheese<\/a>, caught my attention. The idea is to move the slices of plastic cheese around within the frame in order to create a hole large enough to hold the little plastic mouse.  However, when I last checked, Mighty Cheese was sold out. Not wanting to be dissuaded by the unavailability of the puzzle itself, and not knowing the solution, I set out to build a simulator.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/July_22_2022_small.png\" alt=\"\"> <\/p><h4>Not a T<a name=\"af839423-9061-445a-abcc-33e483845857\"><\/a><\/h4><p>I expected Mighty Cheese to be something like the <a href=\"https:\/\/www.mathworks.com\/company\/newsletters\/articles\/introducing-cleves-laboratory.html\">T-puzzle<\/a> that I enjoyed several years ago. But, unlike the T, the geometry of cheese cannot be modelled by simple rectangular patches.  I needed help. Steve Eddins answered my plea and told me about MATLAB's \"polyshapes\". That led to this blog post.<\/p><h4>A slice of cheese<a name=\"fbfbf351-698a-410b-9cba-7272f394fe65\"><\/a><\/h4><p>A \"selfie\" of a cheese slice provides an example of a <tt>polyshape<\/tt>. It has curved boundaries and a hole.  The MATLAB documentation for <a href=\"https:\/\/www.mathworks.com\/help\/matlab\/ref\/polyshape.html\"><tt>polyshape<\/tt><\/a> says this a <i>polygon<\/i>. In my mathematical world, <i>polygons<\/i> can't have curved boundaries or holes.  But, I guess that I am being pedantic.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/polyshape.png\" alt=\"\"> <\/p><p>I began with this photo of the Mighty Cheese puzzle.<\/p><pre class=\"language-matlab\">puzzle = imread(<span class=\"string\">'Cheese_puzzle.png'<\/span>);\r\n<\/pre><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/puzzle.gif\" alt=\"\"> <\/p><p>Two lines of code and the <tt>L*a*b<\/tt> color model find the regions in <tt>photo<\/tt> that look like cheese.<\/p><pre class=\"language-matlab\">[L,a,b] = imsplit(rgb2lab(puzzle));\r\nmask = a &gt; 30;\r\nspy(mask)\r\n<\/pre><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/mask.gif\" alt=\"\"> <\/p><p>Steve provided a function that turns <tt>mask<\/tt> into a <tt>polyshape<\/tt> object.<\/p><pre class=\"language-matlab\">slice = my_polyshapes(mask);\r\n<\/pre><p>An overloaded <tt>plot<\/tt> function then generates the selfie from <tt>slice<\/tt>.<\/p><pre class=\"language-matlab\">sliceplot = plot(slice, <span class=\"keyword\">...<\/span>\r\n    <span class=\"string\">'facecolor'<\/span>,cheese_yellow, <span class=\"keyword\">...<\/span>\r\n    <span class=\"string\">'facealpha'<\/span>,1);\r\n<\/pre><h4>My first solution<a name=\"55c27f57-400d-4f4c-8849-298407ab936f\"><\/a><\/h4><p>I didn't use AI or simulated annealing or any other modern technique to search for a solution.  I just poked around while I was learning about polyshapes and programming my simulator.  It was just me and a <i>real<\/i> mouse.  No, not a <i>real real<\/i> mouse.  You know the kind I mean.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/Cheese.gif\" alt=\"\"> <\/p><h4>Is this solution correct?<a name=\"87aa86ac-b133-4c46-abed-79b9b9669023\"><\/a><\/h4><p>I almost made a blog post claiming this is the solution the designers of Mighty Cheese must have had in mind. But I wasn't sure. My solution made use of the white  space around the outside edges of the slices.  How wide are those gaps?  I didn't yet have a real physical puzzle to measure tolerances.<\/p><h4>Spoiler alert !<a name=\"07004175-0ad2-4431-9504-3d9d8c33a86c\"><\/a><\/h4><p>I am sure glad now that I didn't post that \"solution\". It wasn't correct, and it wasn't pretty.<\/p><p>This puzzle is not as easy as it looks. In fact, the solution is very hard to find and is very elegant. If you want to try to solve it yourself, stop reading this post, bookmark this spot, and come back later.<\/p><h4>My second solution<a name=\"bbdd0ff0-9265-4089-9325-4929faa2d325\"><\/a><\/h4><p>As I should have known, this puzzle is no secret to the Internet It is available for about $10 at many places and YouTube offers several solutions.  But I'm glad that I didn't see any of them until a few weeks ago.<\/p><p>When I made more careful measurements on \"Cheese_puzzle.png\" and had a more accurate model to simulate, it became clear that my precious first solution just wouldn't fit.<\/p><h4>A round peg in a square hole<a name=\"30e29a25-e0f0-449b-b09c-4ff8ee26a6b8\"><\/a><\/h4><p>Nobody said that the mouse had to fit neatly into a circular hole with just the right diameter.  Once you realize that you might be looking for a noncircular hole, you are on the way to finding the solution.<\/p><h4>Theta<a name=\"19fcdc7d-f204-47d7-9e55-221680530003\"><\/a><\/h4><p>The key to the puzzle's geometry is the purple axes in this picture. They cross at right angles at a point in the center hole at the tip of the protruding slice.  The angle between the purple axes and the orange vertical\/horizontal axes can be measured accurately on the photo and everything else follows. The angle is<\/p><pre class=\"language-matlab\">theta = atand((y(b)-y(a))\/(b-a)) = 11.62 degrees\r\n<\/pre><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/Mighty_Cheese_theta.gif\" alt=\"\"> <\/p><h4>Polyshapes<a name=\"4933cc60-9813-49dd-8f8c-d822d7b9b2d2\"><\/a><\/h4><p>The mask that I was using for my first solution got me started with polyshapes, but I eventually abandoned it.  It is easy to make a polyshape directly from a list of points around the boundary, like this.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/Mighty_Cheese_S3_dots.gif\" alt=\"\"> <\/p><h4>The solution<a name=\"1dcd1993-0fec-49da-87a9-4b75d997227f\"><\/a><\/h4><p>The three holes in the original cheese slices do not appear to serve any purpose.  So, I have moved them and given them an important role in this simulation. Combine the two triangular slices in the upper left into a single slice. Rotate each of the resulting four slices by an angle of 180-theta = 168.38 degrees about its center.  The four right-angled corners from the central hole go to the corners of the puzzle while the outer corners form a central square just large enough to hold the mouse.<\/p><p>That is really elegant.<\/p><p>Where did this puzzle originate?  What mathematics was involved in its design?<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/MCsolution.gif\" alt=\"\"> <\/p><h4>Software<a name=\"ed22add4-a328-41ed-9696-c5cebc945091\"><\/a><\/h4><p>My code is here: <a href=\"https:\/\/blogs.mathworks.com\/cleve\/files\/Mighty_Polyshape.m\">Mighty_Polyshape.m<\/a>.<\/p><script language=\"JavaScript\"> <!-- \r\n    function grabCode_2f68df87f4004e7ea2832e4310206744() {\r\n        \/\/ Remember the title so we can use it in the new page\r\n        title = document.title;\r\n\r\n        \/\/ Break up these strings so that their presence\r\n        \/\/ in the Javascript doesn't mess up the search for\r\n        \/\/ the MATLAB code.\r\n        t1='2f68df87f4004e7ea2832e4310206744 ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' 2f68df87f4004e7ea2832e4310206744';\r\n    \r\n        b=document.getElementsByTagName('body')[0];\r\n        i1=b.innerHTML.indexOf(t1)+t1.length;\r\n        i2=b.innerHTML.indexOf(t2);\r\n \r\n        code_string = b.innerHTML.substring(i1, i2);\r\n        code_string = code_string.replace(\/REPLACE_WITH_DASH_DASH\/g,'--');\r\n\r\n        \/\/ Use \/x3C\/g instead of the less-than character to avoid errors \r\n        \/\/ in the XML parser.\r\n        \/\/ Use '\\x26#60;' instead of '<' so that the XML parser\r\n        \/\/ doesn't go ahead and substitute the less-than character. \r\n        code_string = code_string.replace(\/\\x3C\/g, '\\x26#60;');\r\n\r\n        copyright = 'Copyright 2022 The MathWorks, Inc.';\r\n\r\n        w = window.open();\r\n        d = w.document;\r\n        d.write('<pre>\\n');\r\n        d.write(code_string);\r\n\r\n        \/\/ Add copyright line at the bottom if specified.\r\n        if (copyright.length > 0) {\r\n            d.writeln('');\r\n            d.writeln('%%');\r\n            if (copyright.length > 0) {\r\n                d.writeln('% _' + copyright + '_');\r\n            }\r\n        }\r\n\r\n        d.write('<\/pre>\\n');\r\n\r\n        d.title = title + ' (MATLAB code)';\r\n        d.close();\r\n    }   \r\n     --> <\/script><p style=\"text-align: right; font-size: xx-small; font-weight:lighter;   font-style: italic; color: gray\"><br><a href=\"javascript:grabCode_2f68df87f4004e7ea2832e4310206744()\"><span style=\"font-size: x-small;        font-style: italic;\">Get \r\n      the MATLAB code <noscript>(requires JavaScript)<\/noscript><\/span><\/a><br><br>\r\n      Published with MATLAB&reg; R2022a<br><\/p><\/div><!--\r\n2f68df87f4004e7ea2832e4310206744 ##### SOURCE BEGIN #####\r\n%% Polygons, Polyshapes and Puzzles\r\n% Until recently, I knew nothing about the |polyshape| object in MATLAB.\r\n% Now I can use polyshape to simulate an extraordinary puzzle.\r\n\r\n%% Puzzles\r\n% The Web site <https:\/\/www.artofplay.com Art of Play>, from some folks in\r\n% San Diego, has well over two-hundred puzzles.  Recently, one of \r\n% their most popular puzzles,\r\n% <https:\/\/www.artofplay.com\/collections\/packing-puzzles\/products\/mighty-cheese-travel-puzzle\r\n% Mighty Cheese>, caught my attention.\r\n% The idea is to move the slices of plastic cheese around within the\r\n% frame in order to create a hole large enough to hold the little\r\n% plastic mouse.  However, when I last checked, Mighty Cheese was\r\n% sold out.\r\n% Not wanting to be dissuaded by the unavailability of the puzzle itself,\r\n% and not knowing the solution, I set out to build a simulator.\r\n%\r\n% <<July_22_2022_small.png>>\r\n%\r\n\r\n%% Not a T\r\n% I expected Mighty Cheese to be something like the\r\n% <https:\/\/www.mathworks.com\/company\/newsletters\/articles\/introducing-cleves-laboratory.html\r\n% T-puzzle> that I enjoyed several years ago.\r\n% But, unlike the T, the geometry of cheese cannot be modelled by simple\r\n% rectangular patches.  I needed help. Steve Eddins answered my plea and \r\n% told me about MATLAB's \"polyshapes\". That led to this blog post.\r\n\r\n%% A slice of cheese\r\n% A \"selfie\" of a cheese slice provides an example of a |polyshape|.\r\n% It has curved boundaries and a hole.  The MATLAB documentation for\r\n% <https:\/\/www.mathworks.com\/help\/matlab\/ref\/polyshape.html\r\n% |polyshape|> says this a _polygon_.\r\n% In my mathematical world, _polygons_ can't have curved boundaries\r\n% or holes.  But, I guess that I am being pedantic.\r\n%\r\n% <<polyshape.png>>\r\n\r\n%%\r\n% I began with this photo of the Mighty Cheese puzzle.\r\n%\r\n%   puzzle = imread('Cheese_puzzle.png');\r\n%\r\n% <<puzzle.gif>>\r\n%\r\n% Two lines of code and the |L*a*b| color model find the regions\r\n% in |photo| that look like cheese.\r\n%\r\n%   [L,a,b] = imsplit(rgb2lab(puzzle));\r\n%   mask = a > 30;\r\n%   spy(mask)\r\n%\r\n% <<mask.gif>>\r\n%\r\n% Steve provided a function that turns |mask| into a |polyshape|\r\n% object.\r\n%\r\n%   slice = my_polyshapes(mask);\r\n%\r\n% An overloaded |plot| function then generates the selfie from |slice|.\r\n%\r\n%   sliceplot = plot(slice, ...\r\n%       'facecolor',cheese_yellow, ...\r\n%       'facealpha',1);\r\n\r\n%% My first solution\r\n% I didn't use AI or simulated annealing or any other modern technique\r\n% to search for a solution.  I just poked around while I was learning\r\n% about polyshapes and programming my simulator.  It was just me and\r\n% a _real_ mouse.  No, not a _real real_ mouse.  You know the kind I mean. \r\n%\r\n% <<Cheese.gif>>\r\n\r\n%% Is this solution correct?\r\n% I almost made a blog post claiming this is the solution the designers of\r\n% Mighty Cheese must have had in mind. But I wasn't sure.\r\n% My solution made use of the white  space around the outside edges of the\r\n% slices.  How wide are those gaps?  I didn't yet have a real physical \r\n% puzzle to measure tolerances.\r\n\r\n%% Spoiler alert !\r\n% I am sure glad now that I didn't post that \"solution\".\r\n% It wasn't correct, and it wasn't pretty.\r\n%\r\n% This puzzle is not as easy as it looks.\r\n% In fact, the solution is very hard to find and is very elegant.\r\n% If you want to try to solve it yourself, stop reading this post,\r\n% bookmark this spot, and come back later.\r\n\r\n%% My second solution\r\n% As I should have known, this puzzle is no secret to the Internet\r\n% It is available for about $10 at many places and\r\n% YouTube offers several solutions.  But I'm glad that I didn't see any\r\n% of them until a few weeks ago.\r\n%\r\n% When I made more careful measurements on \"Cheese_puzzle.png\"\r\n% and had a more accurate model to simulate,\r\n% it became clear that my precious first solution just wouldn't fit.\r\n \r\n%% A round peg in a square hole\r\n% Nobody said that the mouse had to fit neatly into a circular hole \r\n% with just the right diameter.  Once you realize that you might be\r\n% looking for a noncircular hole, you are on the way to finding the\r\n% solution.\r\n\r\n%% Theta\r\n% The key to the puzzle's geometry is the purple axes in this picture.\r\n% They cross at right angles at a point in the center hole at the tip \r\n% of the protruding slice.  The angle between the purple axes and the\r\n% orange vertical\/horizontal axes can be measured accurately on the\r\n% photo and everything else follows. The angle is\r\n%\r\n%   theta = atand((y(b)-y(a))\/(b-a)) = 11.62 degrees\r\n% \r\n% <<Mighty_Cheese_theta.gif>>\r\n\r\n%% Polyshapes\r\n% The mask that I was using for my first solution got me started with\r\n% polyshapes, but I eventually abandoned it.  It is easy to make a \r\n% polyshape directly from a list of points around the boundary, like this.\r\n% \r\n% <<Mighty_Cheese_S3_dots.gif>>\r\n\r\n%% The solution\r\n% The three holes in the original cheese slices do not appear\r\n% to serve any purpose.  So, I have moved them and given them an\r\n% important role in this simulation.\r\n% Combine the two triangular slices in the upper left into a single slice.\r\n% Rotate each of the resulting four slices by an\r\n% angle of 180-theta = 168.38 degrees about its center.  The four\r\n% right-angled corners from the central hole go to the corners of the \r\n% puzzle while the outer corners form a central square just large enough\r\n% to hold the mouse.\r\n%\r\n% That is really elegant.\r\n%\r\n% Where did this puzzle originate?  What mathematics was involved in\r\n% its design?\r\n%\r\n% <<MCsolution.gif>>\r\n\r\n%% Software\r\n% My code is here:\r\n% <https:\/\/blogs.mathworks.com\/cleve\/files\/Mighty_Polyshape.m\r\n% Mighty_Polyshape.m>.\r\n##### SOURCE END ##### 2f68df87f4004e7ea2832e4310206744\r\n-->","protected":false},"excerpt":{"rendered":"<div class=\"overview-image\"><img src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/Mighty_Cheese_0.gif\" class=\"img-responsive attachment-post-thumbnail size-post-thumbnail wp-post-image\" alt=\"\" decoding=\"async\" loading=\"lazy\" \/><\/div><!--introduction--><p>Until recently, I knew nothing about the <tt>polyshape<\/tt> object in MATLAB. Now I can use polyshape to simulate an extraordinary puzzle.... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/cleve\/2022\/08\/21\/polygons-polyshapes-and-puzzles\/\">read more >><\/a><\/p>","protected":false},"author":78,"featured_media":8861,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[5,23,47],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/8840"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/users\/78"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/comments?post=8840"}],"version-history":[{"count":11,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/8840\/revisions"}],"predecessor-version":[{"id":8981,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/8840\/revisions\/8981"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/media\/8861"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/media?parent=8840"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/categories?post=8840"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/tags?post=8840"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}