Cody

# Problem 820. Eliminate unnecessary polygon vertices

Solution 130485

Submitted on 23 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   Fail
%% Edge case: no vertices P = zeros(0,2); P2 = zeros(0,2); assert(isequal(simplify_polygon(P), P2));

```Error: Attempted to access P(2,:); index out of bounds because size(P)=[0,2]. ```

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

```Error: Attempted to access P(2,:); index out of bounds because size(P)=[1,2]. ```

3   Fail
%% 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));

```Error: Assertion failed. ```

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));

``` P = 1 1 3 1 4 1 5 1 4 1 3 1 2 1 1 1 2 1 P = 1 1 4 1 5 1 4 1 3 1 2 1 1 1 2 1 P = 1 1 5 1 4 1 3 1 2 1 1 1 2 1 P = 1 1 5 1 3 1 2 1 1 1 2 1 P = 1 1 5 1 2 1 1 1 2 1 P = 1 1 5 1 1 1 2 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));

``` P = 1 1 4 1 5 1 1 1 2 1 P = 1 1 5 1 1 1 2 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));

``` P = 1 1 3 1 4 1 4 2 4 3 3 3 2 3 1 3 1 2 1 1 2 1 P = 1 1 4 1 4 2 4 3 3 3 2 3 1 3 1 2 1 1 2 1 P = 1 1 4 1 4 3 3 3 2 3 1 3 1 2 1 1 2 1 P = 1 1 4 1 4 3 2 3 1 3 1 2 1 1 2 1 P = 1 1 4 1 4 3 1 3 1 2 1 1 2 1 P = 1 1 4 1 4 3 1 3 1 1 2 1 ```

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));

``` P = 1 2 1 1 2 1 2 2 1 2 1 4 1 5 2 5 2 4 1 4 1 3 1 2 1 1 P = 1 2 1 1 2 1 2 2 1 2 1 5 2 5 2 4 1 4 1 3 1 2 1 1 P = 1 2 1 1 2 1 2 2 1 2 1 5 2 5 2 4 1 4 1 2 1 1 P = 1 2 1 1 2 1 2 2 1 2 1 5 2 5 2 4 1 4 1 1 ```

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));

``` P = 1 1 3 3 1 3 2 2 3 1 1 1 2 2 P = 1 1 3 3 1 3 3 1 1 1 2 2 ```

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));

``` P = 1 1 3 3 4 4 5 5 5 4 6 3 8 1 7 1 1 1 2 2 P = 1 1 4 4 5 5 5 4 6 3 8 1 7 1 1 1 2 2 P = 1 1 5 5 5 4 6 3 8 1 7 1 1 1 2 2 P = 1 1 5 5 5 4 8 1 7 1 1 1 2 2 P = 1 1 5 5 5 4 8 1 1 1 2 2 ```

10   Fail
%% 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));

```Error: Assertion failed. ```

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));

``` P = 2 1 3 1 3 3 2 3 1 3 1 2 1 1 2 1 3 1 P = 2 1 3 1 3 3 1 3 1 2 1 1 2 1 3 1 P = 2 1 3 1 3 3 1 3 1 1 2 1 3 1 P = 2 1 3 1 3 3 1 3 1 1 3 1 ```