1## Copyright (C) 2021 David Legland 2## All rights reserved. 3## 4## Redistribution and use in source and binary forms, with or without 5## modification, are permitted provided that the following conditions are met: 6## 7## 1 Redistributions of source code must retain the above copyright notice, 8## this list of conditions and the following disclaimer. 9## 2 Redistributions in binary form must reproduce the above copyright 10## notice, this list of conditions and the following disclaimer in the 11## documentation and/or other materials provided with the distribution. 12## 13## THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ''AS IS'' 14## AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 15## IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 16## ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE FOR 17## ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 18## DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 19## SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 20## CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 21## OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 22## OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 23## 24## The views and conclusions contained in the software and documentation are 25## those of the authors and should not be interpreted as representing official 26## policies, either expressed or implied, of the copyright holders. 27 28function loops = expandPolygon(poly, dist, varargin) 29%EXPANDPOLYGON Expand a polygon by a given (signed) distance. 30% 31% POLY2 = expandPolygon(POLY, DIST); 32% Associates to each edge of the polygon POLY the parallel line located 33% at distance DIST from the current edge, and compute intersections with 34% neighbor parallel lines. The input polygon POLY must be oriented 35% counter-clockwise. Otherwise, distance is computed inside the polygon. 36% The resulting polygon is simplified to remove inner "loops", and can 37% eventually be disconnected. 38% The result POLY2 is a cell array, each cell containing a simple linear 39% ring. 40% 41% This is a kind of dilation, but behaviour on corners is different. 42% This function keeps angles of polygons, but there is no direct relation 43% between the lengths of each polygon. 44% 45% It is also possible to specify negative distance, and get all points 46% inside the polygon. If the polygon is convex, the result equals 47% morphological erosion of polygon by a ball with radius equal to the 48% given distance. 49% 50% Example: 51% % Computes the negative offset of a non-convex polygon 52% poly = [10 10;30 10;30 30;20 20;10 30]; 53% poly2 = expandPolygon(poly, -3); 54% figure; 55% drawPolygon(poly, 'linewidth', 2); 56% hold on; drawPolygon(poly2, 'm') 57% axis equal; axis([0 40 0 40]); 58% 59% See also: 60% polygons2d, polygonLoops, polygonSelfIntersections 61% 62 63% --------- 64% author : David Legland 65% INRA - TPV URPOI - BIA IMASTE 66% created the 14/05/2005. 67% 68 69% HISTORY: 70% 31-07-2005 change algo for negative distance: use clipping of polygon 71% by half-planes 72 73% default options 74cleanupLoops = false; 75 76% process input argument 77while length(varargin) > 1 78 paramName = varargin{1}; 79 switch lower(paramName) 80 case 'cleanuploops' 81 cleanupLoops = varargin{2}; 82 otherwise 83 error(['Unknown parameter name: ' paramName]); 84 end 85 varargin(1:2) = []; 86end 87 88% eventually copy first point at the end to ensure closed polygon 89if sum(poly(end, :) == poly(1,:)) ~= 2 90 poly = [poly; poly(1,:)]; 91end 92 93% number of vertices of the polygon 94N = size(poly, 1)-1; 95 96% find lines parallel to polygon edges located at distance DIST 97lines = zeros(N, 4); 98for i = 1:N 99 side = createLine(poly(i,:), poly(i+1,:)); 100 lines(i, 1:4) = parallelLine(side, dist); 101end 102 103% compute intersection points of consecutive lines 104lines = [lines;lines(1,:)]; 105poly2 = zeros(N, 2); 106for i = 1:N 107 poly2(i,1:2) = intersectLines(lines(i,:), lines(i+1,:)); 108end 109 110% split result polygon into set of loops (simple polygons) 111loops = polygonLoops(poly2); 112 113% keep only loops whose distance to original polygon is correct 114if cleanupLoops 115 distLoop = zeros(length(loops), 1); 116 for i = 1:length(loops) 117 distLoop(i) = distancePolygons(loops{i}, poly); 118 end 119 loops = loops(abs(distLoop-abs(dist)) < abs(dist)/1000); 120end 121