{"id":656,"date":"2012-08-28T13:06:13","date_gmt":"2012-08-28T17:06:13","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/?p=656"},"modified":"2019-10-31T14:56:23","modified_gmt":"2019-10-31T18:56:23","slug":"wrapping-up-the-analysis-of-cody-solutions","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2012\/08\/28\/wrapping-up-the-analysis-of-cody-solutions\/","title":{"rendered":"Wrapping up the analysis of Cody solutions"},"content":{"rendered":"<div class=\"content\"><!--introduction--><p>Today I'm wrapping up my analysis of the results of my Cody problem on <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/cody\/problems\/820-eliminate-unnecessary-polygon-vertices\">eliminating unnecessary polygon vertices.<\/a><\/p><!--\/introduction--><h3>Contents<\/h3><div><ul><li><a href=\"#08aff129-efa2-46da-91c8-26330cfa5e62\">A solution by Cris<\/a><\/li><li><a href=\"#2136d0c2-51c5-4702-a31a-848d5ad736d5\">Handling Edge Cases<\/a><\/li><li><a href=\"#d76e1f0d-bc60-4a01-b94b-4086465bc4ec\">Preprocess and Postprocess the Vertex List<\/a><\/li><li><a href=\"#9a8772af-ef66-4c8a-86a1-7bffd04f798e\">Use the <tt>mod<\/tt> Function for Circular Indexing<\/a><\/li><li><a href=\"#65ef6a34-16f0-40c4-9333-ff7655eea2d3\">Using the MATLAB File Compare Tool<\/a><\/li><li><a href=\"#1932c59f-d98a-4728-b50d-72fa5c41de79\">A Solution by Sven<\/a><\/li><li><a href=\"#eccd35ff-7305-4a70-88a7-7c532ec70452\">A Solution by Richard<\/a><\/li><li><a href=\"#c91444f7-2317-4f71-8a0c-ea9c665392e1\">Tag Team Effort<\/a><\/li><li><a href=\"#ff4aeb55-c6ed-4fb1-989b-7314a03f9558\">Output Argument = Input Argument<\/a><\/li><li><a href=\"#e5dfd3b8-e187-4cd3-8fbf-471ca4ba83bd\">Automatic Output Variable, ans<\/a><\/li><li><a href=\"#b13eec76-ddcb-4af4-b664-3f24a97af219\">The Importance of Formulating Your Problem Carefully<\/a><\/li><li><a href=\"#4cad1808-0890-4233-b245-0aa3fdb7152c\">Thanks to All the Solvers!<\/a><\/li><\/ul><\/div><h4>A solution by Cris<a name=\"08aff129-efa2-46da-91c8-26330cfa5e62\"><\/a><\/h4><p>Here is <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/cody\/players\/210779-cris-luengo\">Cris'<\/a> first correct solution.<\/p><pre class=\"language-matlab\"><span class=\"keyword\">function<\/span> P = simplify_polygon_108897_luengo(P)\r\n  N = size(P,1);\r\n  <span class=\"keyword\">if<\/span> N&lt;=2\r\n     <span class=\"keyword\">return<\/span>\r\n  <span class=\"keyword\">end<\/span>\r\n  <span class=\"comment\">% assume last point is same as first one -- remove<\/span>\r\n  <span class=\"comment\">%    in production code I'd run through the whole list and remove<\/span>\r\n  <span class=\"comment\">%    duplicate points.<\/span>\r\n  P(end,:) = [];\r\n  N = N-1\r\n  <span class=\"comment\">% I use 0-based indexing to use MOD more easily, always index with ii+1!<\/span>\r\n  ii = 0; <span class=\"comment\">% The point under consideration<\/span>\r\n  first = NaN; <span class=\"comment\">% The first point we did not remove<\/span>\r\n  <span class=\"keyword\">while<\/span> N&gt;=3 &amp;&amp; ii~=first\r\n    p1 = P(mod(ii-1,N)+1,:);\r\n    p2 = P(ii+1,:);\r\n    p3 = P(mod(ii+1,N)+1,:);\r\n    v1 = p2-p1;\r\n    v2 = p3-p2;\r\n    disp([v1;v2])\r\n    <span class=\"keyword\">if<\/span> ( v1(1)*v2(2) == v1(2)*v2(1) ) &amp;&amp; any(v1.*v2&gt;0)\r\n       <span class=\"comment\">% the two vectors are in the same direction: delete the middle point<\/span>\r\n       P(ii+1,:) = [];\r\n       N = N-1;\r\n       ii = mod(ii,N); <span class=\"comment\">% in case this was the last point<\/span>\r\n    <span class=\"keyword\">else<\/span>\r\n       <span class=\"comment\">% keep the point &amp; move on<\/span>\r\n       <span class=\"keyword\">if<\/span> isnan(first)\r\n           first = ii;\r\n       <span class=\"keyword\">end<\/span>\r\n       ii = mod(ii+1,N);\r\n    <span class=\"keyword\">end<\/span>\r\n  <span class=\"keyword\">end<\/span>\r\n  <span class=\"comment\">% add first point to end again<\/span>\r\n  P(end+1,:) = P(1,:);\r\n<span class=\"keyword\">end<\/span>\r\n<\/pre><p>This code walks forward (in the while loop) through the polygon vertices. Each iteration of the while loop checks one vertex to see if it lies on the line segment between the previous vertex and the next one. If so, the code deletes that vertex.<\/p><p>When I first formulated this problem, I wasn't certain whether a fully vectorized solution was possible. I thought it might be necessary to remove vertices one at a time, as Cris does here.<\/p><p>Cris uses a few different techniques that I have often used in my own code.<\/p><h4>Handling Edge Cases<a name=\"2136d0c2-51c5-4702-a31a-848d5ad736d5\"><\/a><\/h4><p>I prefer to write code that handles edge cases naturally, without conditional logic. However, when edge cases can't be handled smoothly by the main algorithm without adding conditional logic, I often handle them with special-case code and an early return at the beginning.<\/p><pre class=\"language-matlab\">N = size(P,1);\r\n<span class=\"keyword\">if<\/span> N&lt;=2\r\n   <span class=\"keyword\">return<\/span>\r\n<span class=\"keyword\">end<\/span>\r\n<\/pre><h4>Preprocess and Postprocess the Vertex List<a name=\"d76e1f0d-bc60-4a01-b94b-4086465bc4ec\"><\/a><\/h4><p>For his algorithm, Cris didn't want the first polygon vertex to appear again at the end of the list. So he removed it at the beginning and added it back at the end.<\/p><pre class=\"language-matlab\">P(end,:) = [];\r\n<\/pre><pre>     -SNIP-<\/pre><pre class=\"language-matlab\"><span class=\"comment\">% add first point to end again<\/span>\r\nP(end+1,:) = P(1,:);\r\n<\/pre><h4>Use the <tt>mod<\/tt> Function for Circular Indexing<a name=\"9a8772af-ef66-4c8a-86a1-7bffd04f798e\"><\/a><\/h4><p>Suppose you have an index into a vector, and you want the \"next\" element in the vector, where \"next\" means go back to the beginning if you are at the end. One could use conditional logic to achieve this:<\/p><pre class=\"language-matlab\"><span class=\"keyword\">if<\/span> i &lt; length(v)\r\n    i = i + 1;\r\n<span class=\"keyword\">else<\/span>\r\n    i = 1;\r\n<span class=\"keyword\">end<\/span>\r\n<\/pre><p>Or you could use the <tt>mod<\/tt> (modulo) function. You just have to account for 1-based indexing in MATLAB.<\/p><pre class=\"language-matlab\">i = mod(i - 1,length(v)) + 1;\r\n<\/pre><p>The MATLAB function <tt>circshift<\/tt> is implemented using exactly this idea. Here's the key part of <tt>circshift<\/tt>:<\/p><pre class=\"language-matlab\"><span class=\"comment\">% Loop through each dimension of the input matrix to<\/span>\r\n<span class=\"comment\">% calculate shifted indices<\/span>\r\n<span class=\"keyword\">for<\/span> k = 1:numDimsA\r\n  m      = sizeA(k);\r\n  idx{k} = mod((0:m-1)-p(k), m)+1;\r\n<span class=\"keyword\">end<\/span>\r\n<\/pre><pre class=\"language-matlab\"><span class=\"comment\">% Perform the actual conversion by indexing<\/span>\r\n<span class=\"comment\">% into the input matrix<\/span>\r\nb = a(idx{:});\r\n<\/pre><h4>Using the MATLAB File Compare Tool<a name=\"65ef6a34-16f0-40c4-9333-ff7655eea2d3\"><\/a><\/h4><p>Have you ever used the MATLAB File Comparison Tool? It's can be very useful.<\/p><p>I was interested to see how the code changed when Cris submitted his second correct solution. Here's what the File Comparison Tool (available from the Current Folder Browser) showed:<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/2012\/simplify-polygon-file-compare.jpg\" alt=\"\"> <\/p><p>I don't see any algorithm changes. It looks like Cris has started to tweak his solution to make it smaller (as measured by the <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/about\/cody\/\">Cody solution scoring system<\/a>).<\/p><h4>A Solution by Sven<a name=\"1932c59f-d98a-4728-b50d-72fa5c41de79\"><\/a><\/h4><p>The first correct solution was this one by <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/cody\/players\/1672378-sven\">Sven<\/a>:<\/p><pre class=\"language-matlab\"><span class=\"keyword\">function<\/span> Ps = simplify_polygon(P)\r\n  <span class=\"comment\">% Handle degenerate cases!<\/span>\r\n  <span class=\"keyword\">if<\/span> size(P,1)&lt;3\r\n      Ps = P;\r\n      <span class=\"keyword\">return<\/span>;\r\n  <span class=\"keyword\">end<\/span>\r\n  <span class=\"comment\">% Normalise the difference between successive points<\/span>\r\n  pdiff = diff(P([end-1 1:end],:)); <span class=\"comment\">% Append the 2nd-to-last<\/span>\r\n  npdiff = bsxfun(@rdivide, pdiff, sqrt(sum(pdiff.^2,2)));\r\n  <span class=\"comment\">% Any successive normalised differences that don't change can be discarded<\/span>\r\n  keepIdxs = find(any(diff(npdiff),2));\r\n  <span class=\"comment\">% Append the first\/last points (the question states that P(1,:)==P(end,:))<\/span>\r\n  Ps = P(keepIdxs([1:end 1]),:);\r\n<span class=\"keyword\">end<\/span>\r\n<\/pre><p>Sven uses <tt>diff<\/tt> and <tt>bsxfun<\/tt> to get a vectorized solution. He also handles edge cases up front and postprocesses the vertex list.<\/p><h4>A Solution by Richard<a name=\"eccd35ff-7305-4a70-88a7-7c532ec70452\"><\/a><\/h4><p><a href=\"https:\/\/www.mathworks.com\/matlabcentral\/cody\/players\/870621-richard-brown\">Richard<\/a> got into the game early with Cris and Sven. Here is his first correct solution.<\/p><pre class=\"language-matlab\"><span class=\"keyword\">function<\/span> Ps = simplify_polygon(P)\r\n  <span class=\"keyword\">if<\/span> ismember(size(P, 1), [0 1])\r\n    Ps = P;\r\n    <span class=\"keyword\">return<\/span>\r\n  <span class=\"keyword\">end<\/span>\r\n<\/pre><pre>   dP = diff(P);\r\n   dP = bsxfun(@times, 1.\/hypot(dP(:, 1), dP(:, 2)), dP);\r\n   idx = find(abs(1 - dot(dP, circshift(dP, 1), 2)) &gt; 1e-10);\r\n   Ps = P([idx; idx(1)], :);\r\n end<\/pre><p>This solution is somewhat similar to Sven's. Note the use of <tt>hypot<\/tt> and <tt>circshift<\/tt>.<\/p><h4>Tag Team Effort<a name=\"c91444f7-2317-4f71-8a0c-ea9c665392e1\"><\/a><\/h4><p>Sven and Richard engaged in a tag team effort to make their solutions smaller and smaller. Their creative burst certainly contributed to one of the highest \"average solutions per solver\" seen on Cody:<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/2012\/solutions-per-solver.png\" alt=\"\"> <\/p><p>Here's the one of the smallest solutions (at least, it's one of the smallest that doesn't use a Neural Networks toolbox function):<\/p><pre class=\"language-matlab\"><span class=\"keyword\">function<\/span> P = simplify_polygon(P)\r\n  <span class=\"keyword\">try<\/span>\r\n  diag(sum(abs(diff(P)),2)) \\ diff(P);\r\n  P(any(ans - circshift(ans,1),2),:);\r\n  P = vertcat(ans, ans(1,:));\r\n  <span class=\"keyword\">end<\/span>\r\n<\/pre><p>No, I wouldn't write production code like this. But it's clever, and understanding how it works can teach us useful things about MATLAB.<\/p><h4>Output Argument = Input Argument<a name=\"ff4aeb55-c6ed-4fb1-989b-7314a03f9558\"><\/a><\/h4><p>Did you know that you can use the same variable name in both the input argument list and the output argument list of a function? In other words, you can do this:<\/p><pre>  function P = simplify_polygon(P)<\/pre><p>The effect is to initialize the output argument value to the value of the input argument. It's equivalent to this:<\/p><pre>  function P_out = simplify_polygon(P_in)\r\n  P_out = P_in;<\/pre><p>My favorite example of using this technique shows up as a solution to another of my Cody problems, <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/cody\/problems\/262-swap-the-input-arguments\">swapping two values<\/a>.<\/p><pre>  function [b,a] = swap(a,b)<\/pre><p>That's the entire function!<\/p><p>Richard and Sven use this technique in combination with a <tt>try<\/tt> block to avoid having to explicity write code to handle the special cases.<\/p><h4>Automatic Output Variable, ans<a name=\"e5dfd3b8-e187-4cd3-8fbf-471ca4ba83bd\"><\/a><\/h4><p>When a function returns an output argument and you don't assign it to a variable, MATLAB automatically creates a variable called <tt>ans<\/tt> to hold the result. You have probably seen this behavior in the Command Window:<\/p><pre>&gt;&gt; magic(3)<\/pre><pre>ans =<\/pre><pre>     8     1     6\r\n     3     5     7\r\n     4     9     2<\/pre><pre>&gt;&gt; sum(ans)<\/pre><pre>ans =<\/pre><pre>    15    15    15<\/pre><p>But this behavior also happens when you are running functions. The behavior is exploited in these two lines:<\/p><pre>   diag(sum(abs(diff(P)),2)) \\ diff(P);\r\n   P(any(ans - circshift(ans,1),2),:);<\/pre><p>The call to <tt>diag<\/tt> produces an output argument that isn't stored explicitly in a variable. The next line can get that result by using the automatic variable <tt>ans<\/tt>.<\/p><h4>The Importance of Formulating Your Problem Carefully<a name=\"b13eec76-ddcb-4af4-b664-3f24a97af219\"><\/a><\/h4><p>This Cody problem was originally inspired by the problem of postprocessing the output of the Image Processing Toolbox function <tt>bwboundaries<\/tt> in order to remove unneeded vertices. This function produces polygons containing horizontal and vertical line segments vertices whose coordinates are integers. My selection of test cases was heavily influenced by this use case. However, I posed the problem on Cody as a more general problem: \"Eliminate unnecessary polygon vertices.\" As I pointed out <a href=\"https:\/\/blogs.mathworks.com\/steve\/2012\/08\/22\/visualizing-the-floating-point-behavior-of-the-point-on-line-test\/\">last week<\/a>, solving this problem robustly in general can be quite complicated because of floating-point arithmetic issues.<\/p><p>Richard and Sven were very aware of this:<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/2012\/polygon-vertices-floating-point.png\" alt=\"\"> <\/p><h4>Thanks to All the Solvers!<a name=\"4cad1808-0890-4233-b245-0aa3fdb7152c\"><\/a><\/h4><p>Although I have focused on a few particular solutions from three different people today, this problem sparked a very creative collection of solutions from many people. I wish could have spent more time analyzing and discussing all of the solutions.<\/p><p>Thanks for giving it a try, everyone, and I hope you enjoyed it!<\/p><p>Cody solvers, if you'd like to add a comment to this post, please tell us about a particularly interesting Cody problem that you think we should go look at.<\/p><script language=\"JavaScript\"> <!-- \r\n    function grabCode_d186be4bc57243079edacef15ef9493d() {\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='d186be4bc57243079edacef15ef9493d ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' d186be4bc57243079edacef15ef9493d';\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_d186be4bc57243079edacef15ef9493d()\"><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\nd186be4bc57243079edacef15ef9493d ##### SOURCE BEGIN #####\r\n%%\r\n% Today I'm wrapping up my analysis of the results of my Cody problem on\r\n% <https:\/\/www.mathworks.com\/matlabcentral\/cody\/problems\/820-eliminate-unnecessary-polygon-vertices\r\n% eliminating unnecessary polygon vertices.>\r\n%\r\n%% A solution by Cris\r\n% Here is <https:\/\/www.mathworks.com\/matlabcentral\/cody\/players\/210779-cris-luengo \r\n% Cris'> first correct solution.\r\n%\r\n%   function P = simplify_polygon_108897_luengo(P)\r\n%     N = size(P,1);\r\n%     if N<=2\r\n%        return\r\n%     end\r\n%     % assume last point is same as first one REPLACE_WITH_DASH_DASH remove\r\n%     %    in production code I'd run through the whole list and remove\r\n%     %    duplicate points.\r\n%     P(end,:) = [];\r\n%     N = N-1\r\n%     % I use 0-based indexing to use MOD more easily, always index with ii+1!\r\n%     ii = 0; % The point under consideration\r\n%     first = NaN; % The first point we did not remove\r\n%     while N>=3 && ii~=first\r\n%       p1 = P(mod(ii-1,N)+1,:);\r\n%       p2 = P(ii+1,:);\r\n%       p3 = P(mod(ii+1,N)+1,:);\r\n%       v1 = p2-p1;\r\n%       v2 = p3-p2;\r\n%       disp([v1;v2])\r\n%       if ( v1(1)*v2(2) == v1(2)*v2(1) ) && any(v1.*v2>0)\r\n%          % the two vectors are in the same direction: delete the middle point\r\n%          P(ii+1,:) = [];\r\n%          N = N-1;\r\n%          ii = mod(ii,N); % in case this was the last point\r\n%       else\r\n%          % keep the point & move on\r\n%          if isnan(first)\r\n%              first = ii;\r\n%          end\r\n%          ii = mod(ii+1,N);\r\n%       end\r\n%     end\r\n%     % add first point to end again\r\n%     P(end+1,:) = P(1,:);\r\n%   end\r\n%\r\n% This code walks forward (in the while loop) through the polygon vertices.\r\n% Each iteration of the while loop checks one vertex to see if it lies on\r\n% the line segment between the previous vertex and the next one. If so, the\r\n% code deletes that vertex.\r\n%\r\n% When I first formulated this problem, I wasn't certain whether a fully\r\n% vectorized solution was possible. I thought it might be necessary to\r\n% remove vertices one at a time, as Cris does here.\r\n%\r\n% Cris uses a few different techniques that I have often used in my own\r\n% code.\r\n%\r\n%% Handling Edge Cases\r\n%\r\n% I prefer to write code that handles edge cases naturally, without\r\n% conditional logic. However, when edge cases can't be handled smoothly by\r\n% the main algorithm without adding conditional logic, I often handle them\r\n% with special-case code and an early return at the beginning.\r\n%\r\n%   N = size(P,1);\r\n%   if N<=2\r\n%      return\r\n%   end\r\n%\r\n%% Preprocess and Postprocess the Vertex List\r\n%\r\n% For his algorithm, Cris didn't want the first polygon vertex to appear\r\n% again at the end of the list. So he removed it at the beginning and added\r\n% it back at the end.\r\n%\r\n%   P(end,:) = [];\r\n%   \r\n%       -SNIP-\r\n%   \r\n%   % add first point to end again\r\n%   P(end+1,:) = P(1,:);\r\n%\r\n%% Use the |mod| Function for Circular Indexing\r\n%\r\n% Suppose you have an index into a vector, and you want the \"next\" element\r\n% in the vector, where \"next\" means go back to the beginning if you are at\r\n% the end. One could use conditional logic to achieve this:\r\n%\r\n%   if i < length(v)\r\n%       i = i + 1;\r\n%   else\r\n%       i = 1;\r\n%   end\r\n%\r\n% Or you could use the |mod| (modulo) function. You just have to account for\r\n% 1-based indexing in MATLAB.\r\n%\r\n%   i = mod(i - 1,length(v)) + 1;\r\n%\r\n% The MATLAB function |circshift| is implemented using exactly this idea.\r\n% Here's the key part of |circshift|:\r\n%\r\n%   % Loop through each dimension of the input matrix to \r\n%   % calculate shifted indices\r\n%   for k = 1:numDimsA\r\n%     m      = sizeA(k);\r\n%     idx{k} = mod((0:m-1)-p(k), m)+1;\r\n%   end\r\n%   \r\n%   % Perform the actual conversion by indexing \r\n%   % into the input matrix\r\n%   b = a(idx{:});\r\n%\r\n%% Using the MATLAB File Compare Tool\r\n%\r\n% Have you ever used the MATLAB File Comparison Tool? It's can be very\r\n% useful.\r\n%\r\n% I was interested to see how the code changed when Cris submitted his\r\n% second correct solution. Here's what the File Comparison Tool (available\r\n% from the Current Folder Browser) showed:\r\n%\r\n% <<https:\/\/blogs.mathworks.com\/images\/steve\/2012\/simplify-polygon-file-compare.jpg>>\r\n%\r\n% I don't see any algorithm changes. It looks like Cris has started to\r\n% tweak his solution to make it smaller (as measured by the\r\n% <https:\/\/www.mathworks.com\/matlabcentral\/about\/cody\/ Cody solution scoring\r\n% system>).\r\n% \r\n%% A Solution by Sven\r\n%\r\n% The first correct solution was this one by <https:\/\/www.mathworks.com\/matlabcentral\/cody\/players\/1672378-sven \r\n% Sven>:\r\n%\r\n%   function Ps = simplify_polygon(P)\r\n%     % Handle degenerate cases!\r\n%     if size(P,1)<3\r\n%         Ps = P;\r\n%         return;\r\n%     end\r\n%     % Normalise the difference between successive points\r\n%     pdiff = diff(P([end-1 1:end],:)); % Append the 2nd-to-last\r\n%     npdiff = bsxfun(@rdivide, pdiff, sqrt(sum(pdiff.^2,2)));\r\n%     % Any successive normalised differences that don't change can be discarded\r\n%     keepIdxs = find(any(diff(npdiff),2));\r\n%     % Append the first\/last points (the question states that P(1,:)==P(end,:))\r\n%     Ps = P(keepIdxs([1:end 1]),:);\r\n%   end\r\n%\r\n% Sven uses |diff| and |bsxfun| to get a vectorized solution. He also\r\n% handles edge cases up front and postprocesses the vertex list.\r\n%\r\n%% A Solution by Richard\r\n%\r\n% Richard got into the game early with Cris and Sven. Here is his first\r\n% correct solution.\r\n%\r\n%   function Ps = simplify_polygon(P)\r\n%     if ismember(size(P, 1), [0 1])\r\n%       Ps = P;\r\n%       return\r\n%     end\r\n%   \r\n%     dP = diff(P);\r\n%     dP = bsxfun(@times, 1.\/hypot(dP(:, 1), dP(:, 2)), dP);\r\n%     idx = find(abs(1 - dot(dP, circshift(dP, 1), 2)) > 1e-10);\r\n%     Ps = P([idx; idx(1)], :);\r\n%   end\r\n%\r\n% This solution is somewhat similar to Sven's. Note the use of |hypot| and\r\n% |circshift|.\r\n%\r\n%% Tag Team Effort\r\n%\r\n% Sven and Richard engaged in a tag team effort to make their solutions\r\n% smaller and smaller. Their creative burst certainly contributed to one of\r\n% the highest \"average solutions per solver\" seen on Cody:\r\n%\r\n% <<https:\/\/blogs.mathworks.com\/images\/steve\/2012\/solutions-per-solver.png>>\r\n%\r\n% Here's the one of the smallest solutions (at least, it's one of the\r\n% smallest that doesn't use a Neural Networks toolbox function):\r\n%\r\n%   function P = simplify_polygon(P)\r\n%     try\r\n%     diag(sum(abs(diff(P)),2)) \\ diff(P);\r\n%     P(any(ans - circshift(ans,1),2),:);\r\n%     P = vertcat(ans, ans(1,:));\r\n%     end\r\n%\r\n% No, I wouldn't write production code like this. But it's clever, and\r\n% understanding how it works can teach us useful things about MATLAB.\r\n%\r\n%% Output Argument = Input Argument\r\n%\r\n% Did you know that you can use the same variable name in both the input\r\n% argument list and the output argument list of a function? In other words,\r\n% you can do this:\r\n%\r\n%    function P = simplify_polygon(P)\r\n%\r\n% The effect is to initialize the output argument value to the value of the\r\n% input argument. It's equivalent to this:\r\n%\r\n%    function P_out = simplify_polygon(P_in)\r\n%    P_out = P_in;\r\n%\r\n% My favorite example of using this technique shows up as a solution to\r\n% another of my Cody problems,\r\n% <https:\/\/www.mathworks.com\/matlabcentral\/cody\/problems\/262-swap-the-input-arguments\r\n% swapping two values>.\r\n%\r\n%    function [b,a] = swap(a,b)\r\n%\r\n% That's the entire function!\r\n%\r\n% Richard and Sven use this technique in combination with a |try| block to\r\n% avoid having to explicity write code to handle the special cases.\r\n%\r\n%% Automatic Output Variable, ans\r\n%\r\n% When a function returns an output argument and you don't assign it to a\r\n% variable, MATLAB automatically creates a variable called |ans| to hold\r\n% the result. You have probably seen this behavior in the Command Window:\r\n%\r\n%  >> magic(3)\r\n%  \r\n%  ans =\r\n%  \r\n%       8     1     6\r\n%       3     5     7\r\n%       4     9     2\r\n%  \r\n%  >> sum(ans)\r\n%  \r\n%  ans =\r\n%  \r\n%      15    15    15\r\n%\r\n% But this behavior also happens when you are running functions. The\r\n% behavior is exploited in these two lines:\r\n%\r\n%     diag(sum(abs(diff(P)),2)) \\ diff(P);\r\n%     P(any(ans - circshift(ans,1),2),:);\r\n%\r\n% The call to |diag| produces an output argument that isn't stored\r\n% explicitly in a variable. The next line can get that result by using the\r\n% automatic variable |ans|.\r\n%\r\n%% The Importance of Formulating Your Problem Carefully\r\n%\r\n% This Cody problem was originally inspired by the problem of\r\n% postprocessing the output of the Image Processing Toolbox function\r\n% |bwboundaries| in order to remove unneeded vertices. This function\r\n% produces polygons containing horizontal and vertical line segments\r\n% vertices whose coordinates are integers. My selection of test cases was\r\n% heavily influenced by this use case. However, I posed the problem on Cody\r\n% as a more general problem: \"Eliminate unnecessary polygon vertices.\" As I\r\n% pointed out\r\n% <https:\/\/blogs.mathworks.com\/steve\/2012\/08\/22\/visualizing-the-floating-point-behavior-of-the-point-on-line-test\/\r\n% last week>, solving this problem robustly in general can be quite\r\n% complicated because of floating-point arithmetic issues.\r\n%\r\n% Richard and Sven were very aware of this:\r\n%\r\n% <<https:\/\/blogs.mathworks.com\/images\/steve\/2012\/polygon-vertices-floating-point.png>>\r\n%\r\n%% Thanks to All the Solvers!\r\n%\r\n% Although I have focused on a few particular solutions from three\r\n% different people today, this problem sparked a very creative collection\r\n% of solutions from many people. I wish could have spent more time\r\n% analyzing and discussing all of the solutions.\r\n%\r\n% Thanks for giving it a try, everyone, and I hope you enjoyed it!\r\n%\r\n% Cody solvers, if you'd like to add a comment to this post, please tell us\r\n% about a particularly interesting Cody problem that you think we should go\r\n% look at.\r\n##### SOURCE END ##### d186be4bc57243079edacef15ef9493d\r\n-->","protected":false},"excerpt":{"rendered":"<!--introduction--><p>Today I'm wrapping up my analysis of the results of my Cody problem on <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/cody\/problems\/820-eliminate-unnecessary-polygon-vertices\">eliminating unnecessary polygon vertices.<\/a>... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/steve\/2012\/08\/28\/wrapping-up-the-analysis-of-cody-solutions\/\">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":[208,907,320,434,911,695,899,348,422,376,705,54,388,190,194,126,913],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/656"}],"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=656"}],"version-history":[{"count":6,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/656\/revisions"}],"predecessor-version":[{"id":3797,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/656\/revisions\/3797"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/media?parent=656"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/categories?post=656"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/tags?post=656"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}