{"id":648,"date":"2012-07-25T16:05:00","date_gmt":"2012-07-25T20:05:00","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/?p=648"},"modified":"2019-10-31T14:52:37","modified_gmt":"2019-10-31T18:52:37","slug":"cody-problem-solvers-simplify-a-polygon","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2012\/07\/25\/cody-problem-solvers-simplify-a-polygon\/","title":{"rendered":"Cody problem solvers: simplify a polygon"},"content":{"rendered":"<div class=\"content\"><p>A couple of weeks ago I <a href=\"https:\/\/blogs.mathworks.com\/steve\/2012\/07\/09\/a-cody-problem-simplify-a-polygon\/\">posted<\/a> about how one might want to simplify the output of <tt>bwboundaries<\/tt> in order to remove unneeded vertices in the output boundaries. That is, turn this polygon:<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/2012\/simplify_polygon_cody_02.png\" alt=\"\"> <\/p><p>into this one:<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/2012\/simplify_polygon_cody_03.png\" alt=\"\"> <\/p><p>At the same time, I created a new problem on <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/cody\">Cody<\/a> called <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/cody\/problems\/820-eliminate-unnecessary-polygon-vertices\">\"Eliminate unnecessary polygon vertices\"<\/a> and invited everyone to try it.<\/p><p>Well, in the last sixteen days or so, almost 300 solutions have been submitted for this problem!<\/p><p>I've been putting off writing a follow-up blog post because there's so much interesting to look at in the various solution attempts. But I decided today that I need to at least go ahead and recognize the efforts of everyone who participated in this effort.<\/p><p>(As an aside, the MATLAB Community team <a href=\"https:\/\/blogs.mathworks.com\/community\/2012\/07\/23\/cody-and-trendy-release-notes\/\">released updates to Cody just this week<\/a> that make it a lot easier to see who has solved a problem and to search for all solutions by a particular player. That helped me a lot; thanks, team!)<\/p><p>By clicking on the <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/cody\/problems\/820-eliminate-unnecessary-polygon-vertices\/players\">\"Solvers\"<\/a> button I can see the eight players who (as of this writing) have submitted correct solutions to this problem:<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/2012\/820-solvers.png\" alt=\"\"> <\/p><p>I especially appreciate the input from Sven, Richard, and Cris, who all helped \"debug\" my initial test suite in the first few hours.<\/p><p>Sven and Richard engaged in a very impressive tag team effort over the course of several days to find the smallest solution.<\/p><p>And I want to recognize Sagiv for making this his first solved Cody problem! (But keep going, Sagiv, try some more!)<\/p><p>When I was looking at various solutions, I found it helpful to create a function to help visualize them. You can download my visCody820Solution.m file from <a href=\"https:\/\/blogs.mathworks.com\/images\/steve\/2012\/visCody820Solution.m\">here<\/a>. (You'll also need <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/278-arrow\">arrow.m by Erik Johnson<\/a>.)<\/p><p>For example, here is the visualization of one of the test cases.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/2012\/cody-vis-example.png\" alt=\"\"> <\/p><p>Next time I'll write about some of the interesting concepts and MATLAB techniques raised by this problem and its many solutions, including:<\/p><div><ul><li>Making sure the problem is well defined<\/li><li>Floating-point round-off error and the use of tolerances (or not)<\/li><li><tt>diff<\/tt><\/li><li><tt>circshift<\/tt><\/li><li>modulo (or periodic) indexing<\/li><li><tt>bsxfun<\/tt><\/li><li>Subtle behaviors of function input and output arguments<\/li><li>The \"automatic\" output variable <tt>ans<\/tt><\/li><li>Philosophical meanderings about the merits of the Cody solution scoring method<\/li><\/ul><\/div><script language=\"JavaScript\"> <!-- \r\n    function grabCode_cfca97f9be254b3f8a6cc989c7fa1b37() {\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='cfca97f9be254b3f8a6cc989c7fa1b37 ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' cfca97f9be254b3f8a6cc989c7fa1b37';\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 2012 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_cfca97f9be254b3f8a6cc989c7fa1b37()\"><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; 7.14<br><\/p><p class=\"footer\"><br>\r\n      Published with MATLAB&reg; 7.14<br><\/p><\/div><!--\r\ncfca97f9be254b3f8a6cc989c7fa1b37 ##### SOURCE BEGIN #####\r\n%%\r\n% A couple of weeks ago I\r\n% <https:\/\/blogs.mathworks.com\/steve\/2012\/07\/09\/a-cody-problem-simplify-a-polygon\/\r\n% posted> about how one might want to simplify the output of |bwboundaries|\r\n% in order to remove unneeded vertices in the output boundaries. That is,\r\n% turn this polygon:\r\n%\r\n% <<https:\/\/blogs.mathworks.com\/images\/steve\/2012\/simplify_polygon_cody_02.png>>\r\n%\r\n% into this one:\r\n%\r\n% <<https:\/\/blogs.mathworks.com\/images\/steve\/2012\/simplify_polygon_cody_03.png>>\r\n%\r\n% At the same time, I created a new problem on\r\n% <https:\/\/www.mathworks.com\/matlabcentral\/cody Cody> called\r\n% <https:\/\/www.mathworks.com\/matlabcentral\/cody\/problems\/820-eliminate-unnecessary-polygon-vertices\r\n% \"Eliminate unnecessary polygon vertices\"> and invited everyone to try it.\r\n%\r\n% Well, in the last sixteen days or so, almost 300 solutions have been\r\n% submitted for this problem!\r\n%\r\n% I've been putting off writing a follow-up blog post because there's so\r\n% much interesting to look at in the various solution attempts. But I\r\n% decided today that I need to at least go ahead and recognize the efforts\r\n% of everyone who participated in this effort.\r\n%\r\n% (As an aside, the MATLAB Community team\r\n% <https:\/\/blogs.mathworks.com\/community\/2012\/07\/23\/cody-and-trendy-release-notes\/\r\n% released updates to Cody just this week> that make it a lot easier to see\r\n% who has solved a problem and to search for all solutions by a particular\r\n% player. That helped me a lot; thanks, team!)\r\n%\r\n% By clicking on the\r\n% <https:\/\/www.mathworks.com\/matlabcentral\/cody\/problems\/820-eliminate-unnecessary-polygon-vertices\/players\r\n% \"Solvers\"> button I can see the eight players who (as of this writing)\r\n% have submitted correct solutions to this problem:\r\n%\r\n% <<https:\/\/blogs.mathworks.com\/images\/steve\/2012\/820-solvers.png>>\r\n%\r\n% I especially appreciate the input from Sven, Richard, and Cris, who all\r\n% helped \"debug\" my initial test suite in the first few hours.\r\n%\r\n% Sven and Richard engaged in a very impressive tag team effort over the\r\n% course of several days to find the smallest solution.\r\n%\r\n% And I want to recognize Sagiv for making this his first solved Cody\r\n% problem! (But keep going, Sagiv, try some more!)\r\n%\r\n% When I was looking at various solutions, I found it helpful to create a\r\n% function to help visualize them. You can download my visCody820Solution.m\r\n% file from\r\n% <https:\/\/blogs.mathworks.com\/images\/steve\/2012\/visCody820Solution.m here>.\r\n% (You'll also need\r\n% <https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/278-arrow arrow.m\r\n% by Erik Johnson>.)\r\n%\r\n% For example, here is the visualization of one of the test cases.\r\n%\r\n% <<https:\/\/blogs.mathworks.com\/images\/steve\/2012\/cody-vis-example.png>>\r\n%\r\n% Next time I'll write about some of the interesting concepts and MATLAB\r\n% techniques raised by this problem and its many solutions, including:\r\n%\r\n% * Making sure the problem is well defined\r\n% * Floating-point round-off error and the use of tolerances (or not)\r\n% * |diff|\r\n% * |circshift|\r\n% * modulo (or periodic) indexing\r\n% * |bsxfun|\r\n% * Subtle behaviors of function input and output arguments\r\n% * The \"automatic\" output variable |ans|\r\n% * Philosophical meanderings about the merits of the Cody solution scoring\r\n% method\r\n\r\n##### SOURCE END ##### cfca97f9be254b3f8a6cc989c7fa1b37\r\n-->","protected":false},"excerpt":{"rendered":"<p>A couple of weeks ago I posted about how one might want to simplify the output of bwboundaries in order to remove unneeded vertices in the output boundaries. That is, turn this polygon: into this... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/steve\/2012\/07\/25\/cody-problem-solvers-simplify-a-polygon\/\">read more >><\/a><\/p>","protected":false},"author":42,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[320,88,434,695],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/648"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/users\/42"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/comments?post=648"}],"version-history":[{"count":5,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/648\/revisions"}],"predecessor-version":[{"id":3793,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/648\/revisions\/3793"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/media?parent=648"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/categories?post=648"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/tags?post=648"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}