Problem 820. Eliminate unnecessary polygon vertices

Created by Steve Eddins

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Suppose you have an n-point polygon represented as an n-by-2 matrix of polygon vertices, P. Assume that the polygon is closed; that is, assume that P(end,:) is the same as P(1,:).</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Remove as many vertices as possible from P to make a second polygon, P2, that has exactly the same shape as P. P2 must also be closed. Your vertices in P2 should be in the same direction as P. That is, if the vertices in P are in clockwise order, then the vertices in P2 should also be in clockwise order.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>If the first vertex in P is retained in the solution, it should be the first vertex in P2. If the first vertex in P needs to remove, then the first vertex in P2 should be the next retained vertex in P.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>You can test your solution graphically as follows:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[plot(P(:,1), P(:,2), 'r', 'LineWidth', 5);\nhold on\nplot(P2(:,1), P2(:,2), 'b');\nhold off]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The two plotted shapes should overlap exactly.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>EXAMPLE</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[P = [1 1\n 2 1\n 3 1\n 4 1\n 4 2\n 4 3\n 3 3\n 2 3\n 1 3\n 1 2\n 1 1];\n\nP2 = [1 1\n 4 1\n 4 3\n 1 3\n 1 1];]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This problem is related to my</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://blogs.mathworks.com/steve/2012/07/09/a-cody-problem-simplify-a-polygon/\"><w:r><w:t>09-Jul-2012 blog post</w:t></w:r></w:hyperlink><w:r><w:t> on MATLAB Central.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Suppose you have an n-point polygon represented as an n-by-2 matrix of polygon vertices, P. Assume that the polygon is closed; that is, assume that P(end,:) is the same as P(1,:).Remove as many vertices as possible from P to make a second polygon, P2, that has exactly the same shape as P. P2 must also be closed. Your vertices in P2 should be in the same direction as P. That is, if the vertices in P are in clockwise order, then the vertices in P2 should also be in clockwise order.If the first vertex in P is retained in the solution, it should be the first vertex in P2. If the first vertex in P needs to remove, then the first vertex in P2 should be the next retained vertex in P.You can test your solution graphically as follows:<pre class="language-matlab">plot(P(:,1), P(:,2), 'r', 'LineWidth', 5);
hold on
plot(P2(:,1), P2(:,2), 'b');
hold off
</pre>The two plotted shapes should overlap exactly.EXAMPLE<pre class="language-matlab">P = [1 1
 2 1
 3 1
 4 1
 4 2
 4 3
 3 3
 2 3
 1 3
 1 2
 1 1];
</pre><pre class="language-matlab">P2 = [1 1
 4 1
 4 3
 1 3
 1 1];
</pre>This problem is related to my <a href="http://blogs.mathworks.com/steve/2012/07/09/a-cody-problem-simplify-a-polygon/">‎09-Jul-2012 blog post</a> on MATLAB Central.

Suppose you have an n-point polygon represented as an n-by-2 matrix of polygon vertices, P. Assume that the polygon is closed; that is, assume that P(end,:) is the same as P(1,:).

Remove as many vertices as possible from P to make a second polygon, P2, that has exactly the same shape as P. P2 must also be closed. Your vertices in P2 should be in the same direction as P. That is, if the vertices in P are in clockwise order, then the vertices in P2 should also be in clockwise order.

If the first vertex in P is retained in the solution, it should be the first vertex in P2. If the first vertex in P needs to remove, then the first vertex in P2 should be the next retained vertex in P.

You can test your solution graphically as follows:

plot(P(:,1), P(:,2), 'r', 'LineWidth', 5);
  hold on
  plot(P2(:,1), P2(:,2), 'b');
  hold off

The two plotted shapes should overlap exactly.

*EXAMPLE*

P = [1 1
       2 1
       3 1
       4 1
       4 2
       4 3
       3 3
       2 3
       1 3
       1 2
       1 1];
  
  P2 = [1 1
        4 1
        4 3
        1 3
        1 1];

This problem is related to my <http://blogs.mathworks.com/steve/2012/07/09/a-cody-problem-simplify-a-polygon/ ‎09-Jul-2012 blog post> on MATLAB Central.

Solve

Solution Stats

407 Solutions
23 Solvers

Last Solution submitted on Apr 09, 2022

Last 200 Solutions

Problem Comments

9 Comments

9 Comments

Show 6 older comments

Steve Eddins on 9 Jul 2012

Thanks for Cris for pointing out a hole in my original test suite. I added a test case that has a removable vertex as the first row of P and rescored all entries.

Richard Brown on 10 Jul 2012

I think test case 7 is wrong - the starting vertex [1 2] can be removed can't it?

Steve Eddins on 10 Jul 2012

Thanks, Richard. I have updated test case 7, and the solutions are being rescored.

Richard Brown on 10 Jul 2012

And now I think the vertices for test case 7 are coming out in the wrong order (cyclic shifted)] :-)

Cris Luengo on 10 Jul 2012

I agree with Richard. I believe my solution is correct now, but test case 7 is failing it.

Steve Eddins on 10 Jul 2012

This is the second time I've gotten up in the middle of the night to try to fix this. ;-) In my previous attempt to fix test case 7, I was fooled by the diagram I drew.

I've modified test case 7 again. When I run your latest solution, Cris, it passes. We'll see what happens when the solutions all get rescored again.

Richard Brown on 10 Jul 2012

Sorry Steve! Hope you got some sleep in the end :)

James on 31 Aug 2012

Final discussion of the problem is up on the MATLAB blogs now:

http://blogs.mathworks.com/steve/2012/08/28/wrapping-up-the-analysis-of-cody-solutions/

Rafael S.T. Vieira on 14 Oct 2020

Mixing vertices, lines and polygons is not fair because vertices and lines are not polygons and their simplification algorithm is not the same (multiple vertices can be simplified by using the function unique for instance). The author should at least change the problem description imho to "Eliminate unnecessary vertices at any shape or form". Anyway, It's a good problem (having non-manifold polygons is hard enough even without non-polygons).

Solution Comments

Show comments

Problem Recent Solvers23

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!