Cody

Problem 820. Eliminate unnecessary polygon vertices

Solution 132780

Submitted on 30 Aug 2012 by Aurelien Queffurust
This solution is locked. To view this solution, you need to provide a solution of the same size or smaller.
Solve This Problem View on Solution Map

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

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

Suggested Problems

More from this Author5