Discover MakerZone

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

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply 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.

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

Problem Group

Solution Statistics

151 correct solutions 186 incorrect solutions
Last solution submitted on Jan 30, 2014

Problem Comments

Solution Comments