Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi test

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

MATLAB Academy

New to MATLAB?

Learn MATLAB today!

Problem 820. Eliminate unnecessary polygon vertices

Created by Steve Eddins

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.


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 ‎09-Jul-2012 blog post on MATLAB Central.

Problem Group

Solution Statistics

167 correct solutions 234 incorrect solutions
Last solution submitted on May 31, 2016

Problem Comments

Solution Comments