simplifyPolyline

SIMPLIFYPOLYLINE Douglas-Peucker simplification of a polyline.

   POLY2 = simplifyPolyline(POLY, TOL)
   Simplifies the input polyline using the Douglas-Peucker algorithm. 

   Example
     elli = [20 30 40 20 30];
     poly = ellipseToPolygon(elli, 500);
     poly2 = simplifyPolyline(poly, 1); % use a tolerance equal to 1
     figure; hold on;
     drawEllipse(elli);
     drawPoint(poly2, 'mo');

   See also
   polygons2d, simplifyPolygon, resamplePolyline, smoothPolyline

   References
   http://en.wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm

0001 function [poly2, keepInds] = simplifyPolyline(poly, tol)
0002 %SIMPLIFYPOLYLINE Douglas-Peucker simplification of a polyline.
0003 %
0004 %   POLY2 = simplifyPolyline(POLY, TOL)
0005 %   Simplifies the input polyline using the Douglas-Peucker algorithm.
0006 %
0007 %   Example
0008 %     elli = [20 30 40 20 30];
0009 %     poly = ellipseToPolygon(elli, 500);
0010 %     poly2 = simplifyPolyline(poly, 1); % use a tolerance equal to 1
0011 %     figure; hold on;
0012 %     drawEllipse(elli);
0013 %     drawPoint(poly2, 'mo');
0014 %
0015 %   See also
0016 %   polygons2d, simplifyPolygon, resamplePolyline, smoothPolyline
0017 %
0018 %   References
0019 %   http://en.wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm
0020 %
0021 
0022 % ------
0023 % Author: David Legland
0024 % e-mail: david.legland@inra.fr
0025 % Created: 2012-05-04,    using Matlab 7.9.0.529 (R2009b)
0026 % Copyright 2012 INRA - Cepia Software Platform.
0027 
0028 % number of vertices
0029 n = size(poly, 1);
0030 
0031 % initial call to the recursive function
0032 keepInds = recurseSimplify(1, n);
0033 
0034 % keep first and last vertices
0035 keepInds = [1 keepInds n];
0036 
0037 % create the resulting polyline
0038 poly2 = poly(keepInds, :);
0039 
0040 
0041     %% Inner function that is called recursively on polyline portions
0042     function innerInds = recurseSimplify(i0, i1)
0043         
0044         % find the furthest vertex
0045         mid = furthestPointIndex(i0, i1);
0046 
0047         % case of no further simplification
0048         if isempty(mid)
0049             innerInds = mid;
0050             return;
0051         end
0052         
0053         % recursively subdivide each portion
0054         mid1 = recurseSimplify(i0, mid);
0055         mid2 = recurseSimplify(mid, i1);
0056         
0057         % concatenate indices of all portions
0058         innerInds = [mid1 mid mid2];
0059     end
0060     
0061 
0062     %% Inner function for finding index of furthest point in POLY
0063     function ind = furthestPointIndex(i0, i1)
0064 
0065         % for single edges, return empty result
0066         if i1 - i0 < 2
0067             ind = [];
0068             return;
0069         end
0070         
0071         % vertices of the current edge
0072         v0 = poly(i0, :);
0073         v1 = poly(i1, :);
0074         
0075         % find vertex with the greatest distance
0076         dists = distancePointEdge(poly(i0+1:i1-1, :), [v0 v1]);
0077         [maxi, ind] = max(dists);
0078         
0079         % update index only if distance criterion is verified
0080         if maxi > tol
0081             ind = i0 + ind;
0082         else
0083             ind = [];
0084         end
0085     end
0086 
0087 end