expandPolygon

EXPANDPOLYGON Expand a polygon by a given (signed) distance.

   POLY2 = expandPolygon(POLY, DIST);
   Associates to each edge of the polygon POLY the parallel line located
   at distance DIST from the current edge, and compute intersections with
   neighbor parallel lines. The input polygon POLY must be oriented
   counter-clockwise. Otherwise, distance is computed inside the polygon.
   The resulting polygon is simplified to remove inner "loops", and can
   eventually be disconnected. 
   The result POLY2 is a cell array, each cell containing a simple linear
   ring. 
   
   This is a kind of dilation, but behaviour on corners is different.
   This function keeps angles of polygons, but there is no direct relation
   between the lengths of each polygon.

   It is also possible to specify negative distance, and get all points
   inside the polygon. If the polygon is convex, the result equals
   morphological erosion of polygon by a ball with radius equal to the
   given distance.

   Example:
   % Computes the negative offset of a non-convex polygon
     poly = [10 10;30 10;30 30;20 20;10 30];
     poly2 = expandPolygon(poly, -3);
     figure;
     drawPolygon(poly, 'linewidth', 2);
     hold on; drawPolygon(poly2, 'm')
     axis equal; axis([0 40 0 40]);

   See also:
   polygons2d, polygonLoops, polygonSelfIntersections

0001 function loops = expandPolygon(poly, dist, varargin)
0002 %EXPANDPOLYGON Expand a polygon by a given (signed) distance.
0003 %
0004 %   POLY2 = expandPolygon(POLY, DIST);
0005 %   Associates to each edge of the polygon POLY the parallel line located
0006 %   at distance DIST from the current edge, and compute intersections with
0007 %   neighbor parallel lines. The input polygon POLY must be oriented
0008 %   counter-clockwise. Otherwise, distance is computed inside the polygon.
0009 %   The resulting polygon is simplified to remove inner "loops", and can
0010 %   eventually be disconnected.
0011 %   The result POLY2 is a cell array, each cell containing a simple linear
0012 %   ring.
0013 %
0014 %   This is a kind of dilation, but behaviour on corners is different.
0015 %   This function keeps angles of polygons, but there is no direct relation
0016 %   between the lengths of each polygon.
0017 %
0018 %   It is also possible to specify negative distance, and get all points
0019 %   inside the polygon. If the polygon is convex, the result equals
0020 %   morphological erosion of polygon by a ball with radius equal to the
0021 %   given distance.
0022 %
0023 %   Example:
0024 %   % Computes the negative offset of a non-convex polygon
0025 %     poly = [10 10;30 10;30 30;20 20;10 30];
0026 %     poly2 = expandPolygon(poly, -3);
0027 %     figure;
0028 %     drawPolygon(poly, 'linewidth', 2);
0029 %     hold on; drawPolygon(poly2, 'm')
0030 %     axis equal; axis([0 40 0 40]);
0031 %
0032 %   See also:
0033 %   polygons2d, polygonLoops, polygonSelfIntersections
0034 %
0035 
0036 %   ---------
0037 %   author : David Legland
0038 %   INRA - TPV URPOI - BIA IMASTE
0039 %   created the 14/05/2005.
0040 %
0041 
0042 %   HISTORY:
0043 %   31-07-2005 change algo for negative distance: use clipping of polygon
0044 %   by half-planes
0045 
0046 % default options
0047 cleanupLoops = false;
0048 
0049 % process input argument
0050 while length(varargin) > 1
0051     paramName = varargin{1};
0052     switch lower(paramName)
0053         case 'cleanuploops'
0054             cleanupLoops = varargin{2};
0055         otherwise
0056             error(['Unknown parameter name: ' paramName]);
0057     end
0058     varargin(1:2) = [];
0059 end
0060 
0061 % eventually copy first point at the end to ensure closed polygon
0062 if sum(poly(end, :) == poly(1,:)) ~= 2
0063     poly = [poly; poly(1,:)];
0064 end
0065 
0066 % number of vertices of the polygon
0067 N = size(poly, 1)-1;
0068 
0069 % find lines parallel to polygon edges located at distance DIST
0070 lines = zeros(N, 4);
0071 for i = 1:N
0072     side = createLine(poly(i,:), poly(i+1,:));
0073     lines(i, 1:4) = parallelLine(side, dist);
0074 end
0075 
0076 % compute intersection points of consecutive lines
0077 lines = [lines;lines(1,:)];
0078 poly2 = zeros(N, 2);
0079 for i = 1:N
0080     poly2(i,1:2) = intersectLines(lines(i,:), lines(i+1,:));
0081 end
0082 
0083 % split result polygon into set of loops (simple polygons)
0084 loops = polygonLoops(poly2);
0085 
0086 % keep only loops whose distance to original polygon is correct
0087 if cleanupLoops
0088     distLoop = zeros(length(loops), 1);
0089     for i = 1:length(loops)
0090         distLoop(i) = distancePolygons(loops{i}, poly);
0091     end
0092     loops = loops(abs(distLoop-abs(dist)) < abs(dist)/1000);
0093 end