Problem 820. Eliminate unnecessary polygon vertices

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.