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

Solution 111016

6 Comments

6 Comments

Show 3 older comments

Richard Brown on 12 Jul 2012

Aargh ... sorry, used a function from the neural network toolbox without realising it. Didn't know it existed (normr)

Richard Brown on 12 Jul 2012

If there's any way this one could be deleted I'd like it to be, because I think it's cheating (and Sven and I had a good competition going on!)

Sven on 12 Jul 2012

It's alright Richard... when I get home I'll just add normr=@(x)normaliseVector3d(x) to the top of my script and we'll be back in business... we might be near an optimised business but business nonetheless. As long as we don't resort to hacking the test suite via some huge regexp string then I'm still in the game.

Richard Brown on 13 Jul 2012

No, gaming the test suite is out! Although Steve could yet make a mess of all this by using a polygon with floating point vertices ...

Sven on 13 Jul 2012

Hehe... yep I'm sure that would send us scrambling to add a tolerance to whatever-the-current-best-solution-was. But if this were intended for a bwboundaries(BW,'noholes','minimal') type option to bwboundaries, then all coordinates could be assumed integers and even the normalisation would be an unnecessary step since bwboundaries never skips a pixel.

Steve Eddins on 13 Jul 2012

Hey guys ... Don't worry, I'm not going to mess with you by adding new test cases that are subject floating-point round-off error. This will be in interesting point to discuss when I post a follow-up on my blog.

Solution 110965

7 Comments

7 Comments

Show 4 older comments

Richard Brown on 12 Jul 2012

Nicely done! Do you think we've converged on the optimum yet?

Sven on 12 Jul 2012

Cheers, obviously I shamelessly adopted your favourite function.
I honestly thought we'd converged to an optimum (although a slightly distorted use of that word) back at around 64, then 55, then 48... so I only tentatively think we've reached the end. I'd certainly be relieved to call it a draw :)

Sven on 12 Jul 2012

I thought that maybe we could get rid of the extra arguments to sum(,2) and any(,2) by converting to a row matrix, but doing so would add arguments circshift(), so that way may not have any improvements left.

I do know that *every single line* of our function generates an M-Lint warning :) Oh, except the function name now.

Richard Brown on 12 Jul 2012

Yeah, I tried all sorts of ways to do that too! I was trying to figure out a better way to normalise the matrix. I discovered normr, posted my solution, and then realised that it was actually a toolbox function. I'd be happy to have that entry removed :| If you replace the normalisation line with normr(diff(P)) you can get the 36

Sven on 12 Jul 2012

Hah, "Undefined function or variable 'normr'." A while back I had a version with normalizeVector3d(), part of the geom3d() package I use all the time...
I'd be interested to see under the hood of normr... I hope it's vectorized via bsxfun()

Richard Brown on 13 Jul 2012

no it doesn't! it does something like:
n = sqrt(sum(x.^2,2));
x = x ./ n(:, ones(1, size(x,2)));

Sven on 13 Jul 2012

Well then, I bet that the following would run faster and work on any dimensioned data (such as a [10,2,50] sized matrix representing 50 sets of 10 XY vectors):

normr = @(v)bsxfun(@rdivide, v, sqrt(sum(v.^2, 2)));

Solution 110870

2 Comments

2 Comments

Richard Brown on 11 Jul 2012

This one uses the best tool in MATLAB :)

Sven on 12 Jul 2012

Ha! I just knew I'd come back from soccer and see you drop the score a bit. Nice one. Best tool in MATLAB? I like bsxfun, but that's already there... maybe it's an anonymous function... we'll see...

Solution 110846

1 Comment

1 Comment

Richard Brown on 11 Jul 2012

Never give up, never surrender!

Solution 110421

2 Comments

2 Comments

Anton Semechko on 12 Jul 2012

any hints on how to reduce the size of this thing?

Sven on 12 Jul 2012

Hi Anton, here's a hint: You're chopping down P then taking the difference between itself and its circshift. This is very close to just a simple diff() command. Circshift is a useful function, but not quite where you've got it ;)

Think of it this way:
A diff() will get vectors from one point to the next. If any neighbouring vectors point in the exact same direction, they are fair game to remove. More specifically, whenever the direction of the line *changes*, you've found a vertex you want to keep. How can you detect that?

Solution 110339

1 Comment

1 Comment

Sven on 11 Jul 2012

Richard, this one's a team effort indeed!

Solution 109911

4 Comments

4 Comments

Show 1 older comment

Richard Brown on 11 Jul 2012

stealing another one of Sven's tricks

Sven on 11 Jul 2012

Ahaha... I was hoping that silly ans trick was the on you used... turns out there's another somewhere!

Richard Brown on 11 Jul 2012

The ans trick was the one I used ... to go from 54 to 52 ...

Sven on 11 Jul 2012

Yeah, there's one more you'll find that should get you to 51... unless it's already there :)

Solution 109908

1 Comment

1 Comment

Richard Brown on 11 Jul 2012

I didn't know you could do that!

Solution 109905

1 Comment

1 Comment

Richard Brown on 11 Jul 2012

Haha - speak of horrible cody tweaks - I found another!

Solution 109877

4 Comments

4 Comments

Show 1 older comment

Sven on 11 Jul 2012

Hah, Richard, this one's just a sneaky tweak to the only bit I could see that was left... I think you deserve the better score with some improvements that you made that I hadn't thought of (using circshift instead of indexing was a nice touch). I think we left the realm of "nice robust solution" at around the 74/75 mark, and now we've entered the "cody-driven tweak" shadowy underworld that I hope nobody ventures into when making real products :)

Richard Brown on 11 Jul 2012

aargh! what did you do this time!

Richard Brown on 11 Jul 2012

OK, figured it (except I used length!). Ther emust be something else :)

Richard Brown on 11 Jul 2012

Oh, and thanks! But my score is only going down largely thanks to your tweaks. I think it's very much a team effort at this point.

Solution 109705

1 Comment

1 Comment

Richard Brown on 10 Jul 2012

Cheating a bit - assuming exact cancellation. So this method is only suitable for integer coordinates, and I'm not even convinced that that will always work!

Problem Recent Solvers23

Problem Tags

Community Treasure Hunt

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

Start Hunting!

Problem 820. Eliminate unnecessary polygon vertices

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers23

Suggested Problems

More from this Author5

Problem Tags

Community Treasure Hunt

Problem 820. Eliminate unnecessary polygon vertices

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers23

Suggested Problems

More from this Author5

Problem Tags

Community Treasure Hunt

Players