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

Solution 132780

Submitted on 30 Aug 2012 by Aurelien Queffurust

Correct

189Size
Leading solution size is 36.
This solution is locked. To view this solution, you need to provide a solution of the same size or smaller.

Test Suite

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

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

                    
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));
N =
     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));
N =
     8
    -1     0
     1     0
     1     0
     1     0
     2     0
     1     0
     3     0
     1     0
     4     0
    -1     0
    -1     0
    -1     0
    -2     0
    -1     0
    -3     0
    -1     0
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));
N =
     4
    -4     0
     1     0
     1     0
     2     0
     3     0
     1     0
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));
N =
    10
     0    -1
     1     0
     1     0
     1     0
     2     0
     1     0
     3     0
     0     1
     0     1
     0     1
     0     2
    -1     0
    -1     0
    -1     0
    -2     0
    -1     0
    -3     0
     0    -1
     0    -1
     0    -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));
N =
    12
     0    -1
     0    -1
     0    -2
     1     0
     1     0
     0     1
     0     1
    -1     0
    -1     0
     0     1
     0     1
     0     1
     0     2
     0     1
     0     3
     1     0
     1     0
     0    -1
     0    -1
    -1     0
    -1     0
     0    -1
     0    -1
     0    -2
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));
N =
     6
    -2     0
     1     1
     1     1
     1     1
     2     2
    -2     0
    -2     0
     1    -1
     1    -1
     1    -1
     2    -2
    -2     0
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));
N =
     9
    -6     0
     1     1
     1     1
     1     1
     2     2
     1     1
     3     3
     1     1
     4     4
     0    -1
     0    -1
     1    -1
     1    -1
     2    -2
     3    -3
    -1     0
    -1     0
    -6     0
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));
N =
   199
    0.0100    0.6314
   -0.0100    0.6314
   -0.0100    0.6314
   -0.0299    0.6307
   -0.0299    0.6307
   -0.0498    0.6295
   -0.0498    0.6295
   -0.0696    0.6276
   -0.0696    0.6276
   -0.0894    0.6251
   -0.0894    0.6251
   -0.1091    0.6220
   -0.1091    0.6220
   -0.1287    0.6182
   -0.1287    0.6182
   -0.1481    0.6138
   -0.1481    0.6138
   -0.1674    0.6088
   -0.1674    0.6088
   -0.1866    0.6033
   -0.1866    0.6033
   -0.2055    0.5971
   -0.2055    0.5971
   -0.2243    0.5903
   -0.2243    0.5903
   -0.2428    0.5829
   -0.2428    0.5829
   -0.2611    0.5750
   -0.2611    0.5750
   -0.2791    0.5664
   -0.2791    0.5664
   -0.2968    0.5573
   -0.2968    0.5573
   -0.3143    0.5477
   -0.3143    0.5477
   -0.3314    0.5375
   -0.3314    0.5375
   -0.3482    0.5268
   -0.3482    0.5268
   -0.3647    0.5155
   -0.3647    0.5155
   -0.3808    0.5037
   -0.3808    0.5037
   -0.3965    0.4915
   -0.3965    0.4915
   -0.4118    0.4787
   -0.4118    0.4787
   -0.4267    0.4655
   -0.4267    0.4655
   -0.4412    0.4518
   -0.4412    0.4518
   -0.4552    0.4376
   -0.4552    0.4376
   -0.4688    0.4230
   -0.4688    0.4230
   -0.4819    0.4080
   -0.4819    0.4080
   -0.4946    0.3926
   -0.4946    0.3926
   -0.5067    0.3768
   -0.5067    0.3768
   -0.5184    0.3606
   -0.5184    0.3606
   -0.5295    0.3441
   -0.5295    0.3441
   -0.5401    0.3272
   -0.5401    0.3272
   -0.5501    0.3100
   -0.5501    0.3100
   -0.5597    0.2924
   -0.5597    0.2924
   -0.5686    0.2746
   -0.5686    0.2746
   -0.5770    0.2565
   -0.5770    0.2565
   -0.5848    0.2382
   -0.5848    0.2382
   -0.5920    0.2196
   -0.5920    0.2196
   -0.5987    0.2008
   -0.5987    0.2008
   -0.6047    0.1818
   -0.6047    0.1818
   -0.6101    0.1626
   -0.6101    0.1626
   -0.6150    0.1433
   -0.6150    0.1433
   -0.6192    0.1238
   -0.6192    0.1238
   -0.6228    0.1042
   -0.6228    0.1042
   -0.6258    0.0845
   -0.6258    0.0845
   -0.6281    0.0647
   -0.6281    0.0647
   -0.6299    0.0448
   -0.6299    0.0448
   -0.6310    0.0249
   -0.6310    0.0249
   -0.6314    0.0050
   -0.6314    0.0050
   -0.6313   -0.0150
   -0.6313   -0.0150
   -0.6305   -0.0349
   -0.6305   -0.0349
   -0.6291   -0.0548
   -0.6291   -0.0548
   -0.6270   -0.0746
   -0.6270   -0.0746
   -0.6244   -0.0943
   -0.6244   -0.0943
   -0.6211   -0.1140
   -0.6211   -0.1140
   -0.6172   -0.1336
   -0.6172   -0.1336
   -0.6126   -0.1530
   -0.6126   -0.1530
   -0.6075   -0.1722
   -0.6075   -0.1722
   -0.6018   -0.1913
   -0.6018   -0.1913
   -0.5954   -0.2102
   -0.5954   -0.2102
   -0.5885   -0.2289
   -0.5885   -0.2289
   -0.5810   -0.2474
   -0.5810   -0.2474
   -0.5729   -0.2656
   -0.5729   -0.2656
   -0.5642   -0.2836
   -0.5642   -0.2836
   -0.5550   -0.3012
   -0.5550   -0.3012
   -0.5452   -0.3186
   -0.5452   -0.3186
   -0.5349   -0.3356
   -0.5349   -0.3356
   -0.5240   -0.3524
   -0.5240   -0.3524
   -0.5126   -0.3687
   -0.5126   -0.3687
   -0.5007   -0.3847
   -0.5007   -0.3847
   -0.4883   -0.4003
   -0.4883   -0.4003
   -0.4754   -0.4156
   -0.4754   -0.4156
   -0.4621   -0.4304
   -0.4621   -0.4304
   -0.4483   -0.4447
   -0.4483   -0.4447
   -0.4340   -0.4587
   -0.4340   -0.4587
   -0.4193   -0.4721
   -0.4193   -0.4721
   -0.4042   -0.4851
   -0.4042   -0.4851
   -0.3887   -0.4977
   -0.3887   -0.4977
   -0.3728   -0.5097
   -0.3728   -0.5097
   -0.3565   -0.5212
   -0.3565   -0.5212
   -0.3399   -0.5322
   -0.3399   -0.5322
   -0.3229   -0.5427
   -0.3229   -0.5427
   -0.3056   -0.5526
   -0.3056   -0.5526
   -0.2880   -0.5619
   -0.2880   -0.5619
   -0.2701   -0.5708
   -0.2701   -0.5708
   -0.2520   -0.5790
   -0.2520   -0.5790
   -0.2336   -0.5867
   -0.2336   -0.5867
   -0.2149   -0.5937
   -0.2149   -0.5937
   -0.1961   -0.6002
   -0.1961   -0.6002
   -0.1770   -0.6061
   -0.1770   -0.6061
   -0.1578   -0.6114
   -0.1578   -0.6114
   -0.1384   -0.6161
   -0.1384   -0.6161
   -0.1189   -0.6202
   -0.1189   -0.6202
   -0.0993   -0.6236
   -0.0993   -0.6236
   -0.0795   -0.6264
   -0.0795   -0.6264
   -0.0597   -0.6286
   -0.0597   -0.6286
   -0.0398   -0.6302
   -0.0398   -0.6302
   -0.0199   -0.6311
   -0.0199   -0.6311
         0   -0.6314
         0   -0.6314
    0.0199   -0.6311
    0.0199   -0.6311
    0.0398   -0.6302
    0.0398   -0.6302
    0.0597   -0.6286
    0.0597   -0.6286
    0.0795   -0.6264
    0.0795   -0.6264
    0.0993   -0.6236
    0.0993   -0.6236
    0.1189   -0.6202
    0.1189   -0.6202
    0.1384   -0.6161
    0.1384   -0.6161
    0.1578   -0.6114
    0.1578   -0.6114
    0.1770   -0.6061
    0.1770   -0.6061
    0.1961   -0.6002
    0.1961   -0.6002
    0.2149   -0.5937
    0.2149   -0.5937
    0.2336   -0.5867
    0.2336   -0.5867
    0.2520   -0.5790
    0.2520   -0.5790
    0.2701   -0.5708
    0.2701   -0.5708
    0.2880   -0.5619
    0.2880   -0.5619
    0.3056   -0.5526
    0.3056   -0.5526
    0.3229   -0.5427
    0.3229   -0.5427
    0.3399   -0.5322
    0.3399   -0.5322
    0.3565   -0.5212
    0.3565   -0.5212
    0.3728   -0.5097
    0.3728   -0.5097
    0.3887   -0.4977
    0.3887   -0.4977
    0.4042   -0.4851
    0.4042   -0.4851
    0.4193   -0.4721
    0.4193   -0.4721
    0.4340   -0.4587
    0.4340   -0.4587
    0.4483   -0.4447
    0.4483   -0.4447
    0.4621   -0.4304
    0.4621   -0.4304
    0.4754   -0.4156
    0.4754   -0.4156
    0.4883   -0.4003
    0.4883   -0.4003
    0.5007   -0.3847
    0.5007   -0.3847
    0.5126   -0.3687
    0.5126   -0.3687
    0.5240   -0.3524
    0.5240   -0.3524
    0.5349   -0.3356
    0.5349   -0.3356
    0.5452   -0.3186
    0.5452   -0.3186
    0.5550   -0.3012
    0.5550   -0.3012
    0.5642   -0.2836
    0.5642   -0.2836
    0.5729   -0.2656
    0.5729   -0.2656
    0.5810   -0.2474
    0.5810   -0.2474
    0.5885   -0.2289
    0.5885   -0.2289
    0.5954   -0.2102
    0.5954   -0.2102
    0.6018   -0.1913
    0.6018   -0.1913
    0.6075   -0.1722
    0.6075   -0.1722
    0.6126   -0.1530
    0.6126   -0.1530
    0.6172   -0.1336
    0.6172   -0.1336
    0.6211   -0.1140
    0.6211   -0.1140
    0.6244   -0.0943
    0.6244   -0.0943
    0.6270   -0.0746
    0.6270   -0.0746
    0.6291   -0.0548
    0.6291   -0.0548
    0.6305   -0.0349
    0.6305   -0.0349
    0.6313   -0.0150
    0.6313   -0.0150
    0.6314    0.0050
    0.6314    0.0050
    0.6310    0.0249
    0.6310    0.0249
    0.6299    0.0448
    0.6299    0.0448
    0.6281    0.0647
    0.6281    0.0647
    0.6258    0.0845
    0.6258    0.0845
    0.6228    0.1042
    0.6228    0.1042
    0.6192    0.1238
    0.6192    0.1238
    0.6150    0.1433
    0.6150    0.1433
    0.6101    0.1626
    0.6101    0.1626
    0.6047    0.1818
    0.6047    0.1818
    0.5987    0.2008
    0.5987    0.2008
    0.5920    0.2196
    0.5920    0.2196
    0.5848    0.2382
    0.5848    0.2382
    0.5770    0.2565
    0.5770    0.2565
    0.5686    0.2746
    0.5686    0.2746
    0.5597    0.2924
    0.5597    0.2924
    0.5501    0.3100
    0.5501    0.3100
    0.5401    0.3272
    0.5401    0.3272
    0.5295    0.3441
    0.5295    0.3441
    0.5184    0.3606
    0.5184    0.3606
    0.5067    0.3768
    0.5067    0.3768
    0.4946    0.3926
    0.4946    0.3926
    0.4819    0.4080
    0.4819    0.4080
    0.4688    0.4230
    0.4688    0.4230
    0.4552    0.4376
    0.4552    0.4376
    0.4412    0.4518
    0.4412    0.4518
    0.4267    0.4655
    0.4267    0.4655
    0.4118    0.4787
    0.4118    0.4787
    0.3965    0.4915
    0.3965    0.4915
    0.3808    0.5037
    0.3808    0.5037
    0.3647    0.5155
    0.3647    0.5155
    0.3482    0.5268
    0.3482    0.5268
    0.3314    0.5375
    0.3314    0.5375
    0.3143    0.5477
    0.3143    0.5477
    0.2968    0.5573
    0.2968    0.5573
    0.2791    0.5664
    0.2791    0.5664
    0.2611    0.5750
    0.2611    0.5750
    0.2428    0.5829
    0.2428    0.5829
    0.2243    0.5903
    0.2243    0.5903
    0.2055    0.5971
    0.2055    0.5971
    0.1866    0.6033
    0.1866    0.6033
    0.1674    0.6088
    0.1674    0.6088
    0.1481    0.6138
    0.1481    0.6138
    0.1287    0.6182
    0.1287    0.6182
    0.1091    0.6220
    0.1091    0.6220
    0.0894    0.6251
    0.0894    0.6251
    0.0696    0.6276
    0.0696    0.6276
    0.0498    0.6295
    0.0498    0.6295
    0.0299    0.6307
    0.0299    0.6307
    0.0100    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));
N =
     8
     1     0
     1     0
     2     0
     0     1
     0     1
     0     1
     0     2
    -1     0
    -1     0
    -1     0
    -2     0
     0    -1
     0    -1
     0    -1
     0    -2
     2     0