Cody

# Problem 820. Eliminate unnecessary polygon vertices

Solution 170867

Submitted on 30 Nov 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));

``` ```

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

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

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 = 0 1 0 -1 ans = 1 1 1 2 1 1 ```

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 0 1 0 1 0 1 0 -1 0 -1 0 -1 0 -1 0 ans = 1 1 5 1 1 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 0 1 0 1 0 -1 0 ans = 1 1 5 1 1 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 0 1 0 1 0 0 1 0 1 -1 0 -1 0 -1 0 0 -1 0 -1 ans = 1 1 4 1 4 3 1 3 1 1 ```

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

```Error: Assertion failed. ```

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

```Error: Assertion failed. ```

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 = 0.707106781186547 0.707106781186547 0.707106781186547 0.707106781186547 0.707106781186547 0.707106781186547 0.707106781186547 0.707106781186547 0 -1.000000000000000 0.707106781186547 -0.707106781186547 0.707106781186547 -0.707106781186547 -1.000000000000000 0 -1.000000000000000 0 ans = 1 1 5 5 5 4 8 1 1 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 = -0.015786242013634 0.999875389517657 -0.047342989971558 0.998878691984444 -0.078852545407478 0.996886290447793 -0.110283498911278 0.993900170976887 -0.141604519424951 0.989923310200557 -0.172784385474099 0.984959672340111 -0.203792016290151 0.979014205257715 -0.234596502792371 0.972092835524256 -0.265167138398679 0.964202462511612 -0.295473449634665 0.955350951515196 -0.325485226510213 0.945547125913667 -0.355172552633427 0.934800758373599 -0.384505835032010 0.923122561107861 -0.413455833652136 0.910524175197461 -0.441993690505580 0.897018158987463 -0.470090958436004 0.882617975568546 -0.497719629475683 0.867337979356715 -0.524852162764470 0.851193401784493 -0.551461512003104 0.834200336117920 -0.577521152413588 0.816375721414399 -0.603005107179615 0.797737325637519 -0.627887973340860 0.778303727945529 -0.652144947115185 0.758094300171247 -0.675751848623609 0.737129187511778 -0.698685145993307 0.715429288447371 -0.720921978814716 0.693016233909333 -0.742440180929284 0.669912365717854 -0.763218302525168 0.646140714311210 -0.783235631518891 0.621724975788495 -0.802472214201577 0.596689488288858 -0.820908875129265 0.571059207730691 -0.838527236237376 0.544859682935072 -0.855309735160412 0.518117030158077 -0.871239642738459 0.490857907057594 -0.886301079693208 0.463109486120349 -0.900479032456750 0.434899427575797 -0.913759368137437 0.406255851823789 -0.926128848607842 0.377207311403574 -0.937575143700826 0.347782762531980 -0.948086843500510 0.318011536239237 -0.957653469715928 0.287923309131171 -0.966265486126022 0.257548073806896 -0.973914308085538 0.226916108961586 -0.980592311082403 0.196057949203982 -0.986292838338003 0.165004354618796 -0.991010207442792 0.133786280104479 -0.994739716020657 0.102434844516615 -0.997477646416339 0.070981299648016 -0.999221269401276 0.039456999076252 -0.999968846894156 0.007893366909716 -0.999719633693478 -0.023678133536623 -0.998473878220378 -0.055226031104513 -0.996232822271007 -0.086718878163552 -0.992998699778670 -0.118125281958903 -0.988774734587002 -0.149413935904264 -0.983565137236370 -0.180553650788900 -0.977375100766707 -0.211513385867820 -0.970210795540986 -0.242262279803783 -0.962079363094463 -0.272769681430602 -0.952988909015839 -0.303005180306874 -0.942948494867437 -0.332938637029760 -0.931968129152436 -0.362540213278623 -0.920058757338174 -0.391780401558495 -0.907232250945480 -0.420630054613787 -0.893501395714876 -0.449060414482917 -0.878879878861460 -0.477043141164890 -0.863382275431222 -0.504550340869179 -0.847024033772301 -0.531554593820898 -0.829821460135725 -0.558028981593441 -0.811791702421020 -0.583947113941307 -0.792952733082779 -0.609283155106517 -0.773323331215340 -0.634011849572238 -0.752923063833378 -0.658108547238037 -0.731772266367075 -0.681549227991636 -0.709892022391333 -0.704310525652672 -0.687304142609185 -0.726369751264638 -0.664031143110432 -0.747704915711708 -0.640096222927107 -0.768294751637971 -0.615523240908178 -0.788118734647193 -0.590336691936526 -0.807157103761987 -0.564561682511920 -0.825390881121975 -0.538223905724291 -0.842801890901349 -0.511349615642326 -0.859372777426912 -0.483965601142840 -0.875087022478593 -0.456099159207014 -0.889928961755181 -0.427778067710213 -0.903883800488822 -0.399030557732339 -0.916937628192790 -0.369885285416544 -0.929077432527732 -0.340371303404114 -0.940291112272675 -0.310518031874170 -0.950567489387783 -0.280355229217013 -0.959896320156857 -0.249912962370313 -0.968268305398506 -0.219221576847687 -0.975675099735775 -0.188311666489719 -0.982109319914980 -0.157214042967250 -0.987564552165524 -0.125959705067719 -0.992035358593258 -0.094579807794848 -0.995517282601106 -0.063105631312673 -0.998006853331493 -0.031568549764811 -0.999501589126174 0 -1.000000000000000 0.031568549764812 -0.999501589126174 0.063105631312673 -0.998006853331493 0.094579807794842 -0.995517282601106 0.125959705067723 -0.992035358593257 0.157214042967250 -0.987564552165524 0.188311666489716 -0.982109319914981 0.219221576847692 -0.975675099735773 0.249912962370307 -0.968268305398508 0.280355229217013 -0.959896320156857 0.310518031874170 -0.950567489387782 0.340371303404114 -0.940291112272675 0.369885285416550 -0.929077432527730 0.399030557732338 -0.916937628192790 0.427778067710208 -0.903883800488824 0.456099159207019 -0.889928961755179 0.483965601142835 -0.875087022478596 0.511349615642327 -0.859372777426912 0.538223905724292 -0.842801890901348 0.564561682511917 -0.825390881121977 0.590336691936529 -0.807157103761985 0.615523240908178 -0.788118734647193 0.640096222927107 -0.768294751637971 0.664031143110431 -0.747704915711709 0.687304142609185 -0.726369751264639 0.709892022391332 -0.704310525652673 0.731772266367076 -0.681549227991634 0.752923063833377 -0.658108547238037 0.773323331215338 -0.634011849572240 0.792952733082780 -0.609283155106515 0.811791702421021 -0.583947113941306 0.829821460135725 -0.558028981593441 0.847024033772300 -0.531554593820900 0.863382275431223 -0.504550340869178 0.878879878861460 -0.477043141164890 0.893501395714873 -0.449060414482922 0.907232250945482 -0.420630054613783 0.920058757338175 -0.391780401558492 0.931968129152433 -0.362540213278629 0.942948494867439 -0.332938637029756 0.952988909015838 -0.303005180306875 0.962079363094462 -0.272769681430605 0.970210795540986 -0.242262279803786 0.977375100766708 -0.211513385867817 0.983565137236370 -0.180553650788902 0.988774734587002 -0.149413935904263 0.992998699778670 -0.118125281958904 0.996232822271007 -0.086718878163551 0.998473878220378 -0.055226031104513 0.999719633693478 -0.023678133536623 0.999968846894156 0.007893366909716 0.999221269401276 0.039456999076247 0.997477646416338 0.070981299648021 0.994739716020657 0.102434844516614 0.991010207442792 0.133786280104481 0.986292838338004 0.165004354618794 0.980592311082404 0.196057949203980 0.973914308085538 0.226916108961589 0.966265486126022 0.257548073806894 0.957653469715930 0.287923309131164 0.948086843500507 0.318011536239246 0.937575143700826 0.347782762531978 0.926128848607842 0.377207311403575 0.913759368137436 0.406255851823791 0.900479032456755 0.434899427575787 0.886301079693207 0.463109486120350 0.871239642738460 0.490857907057593 0.855309735160410 0.518117030158080 0.838527236237378 0.544859682935069 0.820908875129265 0.571059207730691 0.802472214201575 0.596689488288860 0.783235631518890 0.621724975788495 0.763218302525169 0.646140714311209 0.742440180929283 0.669912365717855 0.720921978814720 0.693016233909328 0.698685145993306 0.715429288447372 0.675751848623608 0.737129187511780 0.652144947115186 0.758094300171246 0.627887973340861 0.778303727945528 0.603005107179613 0.797737325637521 0.577521152413590 0.816375721414398 0.551461512003108 0.834200336117917 0.524852162764469 0.851193401784494 0.497719629475684 0.867337979356714 0.470090958436002 0.882617975568548 0.441993690505576 0.897018158987465 0.413455833652137 0.910524175197461 0.384505835032011 0.923122561107861 0.355172552633430 0.934800758373598 0.325485226510212 0.945547125913667 0.295473449634667 0.955350951515196 0.265167138398678 0.964202462511612 0.234596502792374 0.972092835524256 0.203792016290154 0.979014205257714 0.172784385474097 0.984959672340111 0.141604519424954 0.989923310200557 0.110283498911271 0.993900170976888 0.078852545407479 0.996886290447793 0.047342989971562 0.998878691984443 0.015786242013634 0.999875389517657 ans = 20.000000000000000 0 19.990031782523477 0.631370995296211 19.960137066629869 1.262112626253473 19.910345652022119 1.891596155896899 19.840707171865155 2.519194101354351 19.751291043310474 3.144280859345016 19.642186398299607 3.766233329794357 19.513501994715472 4.384431536953826 19.365366107970143 4.998259247406168 19.197926403137139 5.607104584340288 19.011349787755659 6.210360637483376 18.805822245453513 6.807426068082256 18.581548650554613 7.397705708330936 18.338752563855778 7.980611154646819 18.077676009776471 8.555561354204192 17.798579235103606 9.121983184140319 17.501740449571873 9.679312022856775 17.187455548538239 10.226992312846534 16.856037818027012 10.764478114485769 16.507817622439525 11.291233650238361 16.143142075239709 11.806733838730567 15.762374692943848 12.310464818163585 15.365895032759415 12.801924458542143 14.954098314234184 13.280622862208624 14.527395025292789 13.746082852183685 14.086210513053443 14.197840447826657 13.630984559832676 14.635445327341536 13.162170944760753 15.058461276667540 12.680236991444772 15.466466624306781 12.185663102130333 15.859054661655572 11.678942278826126 16.235834048420415 11.160579631868803 16.596429202714514 10.631091876418029 16.940480675445976 10.091006817383549 17.267645508624465 9.540862823297791 17.577597577229206 8.981208289658403 17.870027914297481 8.412601092275688 18.144645018909628 7.835608031169863 18.401175146763492 7.250804265572491 18.639362583048698 6.658772740595226 18.858969897348739 6.060103606137455 19.059778180316783 5.455393628612065 19.241587261889258 4.845245596075664 19.404215910819726 4.230267717356381 19.547502015334143 3.611073015778046 19....```

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

```Error: Assertion failed. ```