Cody

# Problem 820. Eliminate unnecessary polygon vertices

Solution 132791

Submitted on 30 Aug 2012
This solution is locked. To view this solution, you need to provide a solution of the same size or smaller.

### Test Suite

Test Status Code Input and Output
1   Pass
%% Edge case: no vertices P = zeros(0,2); P2 = zeros(0,2); assert(isequal(simplify_polygon(P), P2));

``` ans = Empty matrix: 0-by-2 ```

2   Fail
%% Edge case: one vertex P = [1 1]; P2 = [1 1]; assert(isequal(simplify_polygon(P), P2));

```Error: Assertion failed. ```

3   Pass
%% Edge case: three vertices (a single line segment) P = [... 1 1 1 2 1 1 ]; P2 = [... 1 1 1 2 1 1]; assert(isequal(simplify_polygon(P), P2));

``` ans = 1 1 1 2 ```

4   Pass
%% Single line segment with multiple vertices P = [ ... 1 1 2 1 3 1 4 1 5 1 4 1 3 1 2 1 1 1]; P2 = [ ... 1 1 5 1 1 1]; assert(isequal(simplify_polygon(P), P2));

``` ans = 1 1 5 1 ```

5   Pass
%% Single line segment, different spacing P = [ ... 1 1 2 1 4 1 5 1 1 1]; P2 = [ ... 1 1 5 1 1 1]; assert(isequal(simplify_polygon(P), P2));

``` ans = 1 1 5 1 ```

6   Pass
%% Rectangle 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]; assert(isequal(simplify_polygon(P), P2));

``` ans = 1 1 4 1 4 3 1 3 ```

7   Pass
%% Two rectangles separated by line segment P = [ ... 1 2 1 1 2 1 2 2 1 2 1 3 1 4 1 5 2 5 2 4 1 4 1 3 1 2]; P2 = [ ... 1 1 2 1 2 2 1 2 1 5 2 5 2 4 1 4 1 1]; assert(isequal(simplify_polygon(P), P2));

``` ans = 1 1 2 1 2 2 1 2 1 5 2 5 2 4 1 4 ```

8   Pass
%% Nonsimple polygon (figure eight) P = [ ... 1 1 2 2 3 3 1 3 2 2 3 1 1 1]; P2 = [ ... 1 1 3 3 1 3 3 1 1 1]; assert(isequal(simplify_polygon(P), P2));

``` ans = 1 1 3 3 1 3 3 1 ```

9   Pass
%% P = [ ... 1 1 2 2 3 3 4 4 5 5 5 4 6 3 8 1 7 1 1 1]; P2 = [ ... 1 1 5 5 5 4 8 1 1 1]; assert(isequal(simplify_polygon(P), P2));

``` ans = 1 1 5 5 5 4 8 1 ```

10   Pass
%% Circle; no points should be removed theta = linspace(0,2*pi,200); theta(end) = 0; x = 20*cos(theta); y = 20*sin(theta); P = [x', y']; P2 = P; assert(isequal(simplify_polygon(P), P2));

``` ans = 20.0000 0 19.9900 0.6314 19.9601 1.2621 19.9103 1.8916 19.8407 2.5192 19.7513 3.1443 19.6422 3.7662 19.5135 4.3844 19.3654 4.9983 19.1979 5.6071 19.0113 6.2104 18.8058 6.8074 18.5815 7.3977 18.3388 7.9806 18.0777 8.5556 17.7986 9.1220 17.5017 9.6793 17.1875 10.2270 16.8560 10.7645 16.5078 11.2912 16.1431 11.8067 15.7624 12.3105 15.3659 12.8019 14.9541 13.2806 14.5274 13.7461 14.0862 14.1978 13.6310 14.6354 13.1622 15.0585 12.6802 15.4665 12.1857 15.8591 11.6789 16.2358 11.1606 16.5964 10.6311 16.9405 10.0910 17.2676 9.5409 17.5776 8.9812 17.8700 8.4126 18.1446 7.8356 18.4012 7.2508 18.6394 6.6588 18.8590 6.0601 19.0598 5.4554 19.2416 4.8452 19.4042 4.2303 19.5475 3.6111 19.6713 2.9883 19.7755 2.3625 19.8600 1.7344 19.9247 1.1045 19.9695 0.4736 19.9944 -0.1579 19.9994 -0.7891 19.9844 -1.4196 19.9496 -2.0487 19.8948 -2.6757 19.8202 -3.3001 19.7259 -3.9212 19.6118 -4.5383 19.4783 -5.1510 19.3253 -5.7585 19.1531 -6.3602 18.9617 -6.9557 18.7515 -7.5441 18.5226 -8.1251 18.2752 -8.6980 18.0096 -9.2622 17.7260 -9.8172 17.4248 -10.3623 17.1062 -10.8972 16.7705 -11.4212 16.4182 -11.9338 16.0494 -12.4345 15.6647 -12.9228 15.2644 -13.3982 14.8488 -13.8603 14.4184 -14.3086 13.9737 -14.7426 13.5150 -15.1619 13.0429 -15.5661 12.5578 -15.9547 12.0601 -16.3275 11.5504 -16.6840 11.0292 -17.0239 10.4970 -17.3468 9.9544 -17.6524 9.4018 -17.9404 8.8399 -18.2105 8.2691 -18.4625 7.6901 -18.6960 7.1035 -18.9109 6.5097 -19.1070 5.9095 -19.2840 5.3033 -19.4419 4.6919 -19.5803 4.0758 -19.6992 3.4557 -19.7985 2.8321 -19.8780 2.2057 -19.9377 1.5771 -19.9776 0.9469 -19.9975 0.3157 -19.9975 -0.3157 -19.9776 -0.9469 -19.9377 -1.5771 -19.8780 -2.2057 -19.7985 -2.8321 -19.6992 -3.4557 -19.5803 -4.0758 -19.4419 -4.6919 -19.2840 -5.3033 -19.1070 -5.9095 -18.9109 -6.5097 -18.6960 -7.1035 -18.4625 -7.6901 -18.2105 -8.2691 -17.9404 -8.8399 -17.6524 -9.4018 -17.3468 -9.9544 -17.0239 -10.4970 -16.6840 -11.0292 -16.3275 -11.5504 -15.9547 -12.0601 -15.5661 -12.5578 -15.1619 -13.0429 -14.7426 -13.5150 -14.3086 -13.9737 -13.8603 -14.4184 -13.3982 -14.8488 -12.9228 -15.2644 -12.4345 -15.6647 -11.9338 -16.0494 -11.4212 -16.4182 -10.8972 -16.7705 -10.3623 -17.1062 -9.8172 -17.4248 -9.2622 -17.7260 -8.6980 -18.0096 -8.1251 -18.2752 -7.5441 -18.5226 -6.9557 -18.7515 -6.3602 -18.9617 -5.7585 -19.1531 -5.1510 -19.3253 -4.5383 -19.4783 -3.9212 -19.6118 -3.3001 -19.7259 -2.6757 -19.8202 -2.0487 -19.8948 -1.4196 -19.9496 -0.7891 -19.9844 -0.1579 -19.9994 0.4736 -19.9944 1.1045 -19.9695 1.7344 -19.9247 2.3625 -19.8600 2.9883 -19.7755 3.6111 -19.6713 4.2303 -19.5475 4.8452 -19.4042 5.4554 -19.2416 6.0601 -19.0598 6.6588 -18.8590 7.2508 -18.6394 7.8356 -18.4012 8.4126 -18.1446 8.9812 -17.8700 9.5409 -17.5776 10.0910 -17.2676 10.6311 -16.9405 11.1606 -16.5964 11.6789 -16.2358 12.1857 -15.8591 12.6802 -15.4665 13.1622 -15.0585 13.6310 -14.6354 14.0862 -14.1978 14.5274 -13.7461 14.9541 -13.2806 15.3659 -12.8019 15.7624 -12.3105 16.1431 -11.8067 16.5078 -11.2912 16.8560 -10.7645 17.1875 -10.2270 17.5017 -9.6793 17.7986 -9.1220 18.0777 -8.5556 18.3388 -7.9806 18.5815 -7.3977 18.8058 -6.8074 19.0113 -6.2104 19.1979 -5.6071 19.3654 -4.9983 19.5135 -4.3844 19.6422 -3.7662 19.7513 -3.1443 19.8407 -2.5192 19.9103 -1.8916 19.9601 -1.2621 19.9900 -0.6314 ```

11   Pass
%% Starting vertex can be removed P = [ ... 2 1 3 1 3 2 3 3 2 3 1 3 1 2 1 1 2 1]; P2 = [ ... 3 1 3 3 1 3 1 1 3 1]; assert(isequal(simplify_polygon(P), P2));

``` ans = 3 1 3 3 1 3 1 1 ```