polygonSelfIntersections

POLYGONSELFINTERSECTIONS Find self-intersection points of a polygon.

   PTS = polygonSelfIntersections(POLY)
   Return the position of self intersection points

   [PTS, POS1, POS2] = polygonSelfIntersections(POLY)
   Also return the 2 positions of each intersection point (the position
   when meeting point for first time, then position when meeting point
   for the second time).

   [...] = polygonSelfIntersections(POLY, 'tolerance', TOL)
   Specifies an additional parameter to decide whether two intersection
   points should be considered the same, based on their euclidean
   distance.  


   Example
       % use a '8'-shaped polygon
       poly = [10 0;0 0;0 10;20 10;20 20;10 20];
       polygonSelfIntersections(poly)
       ans = 
           10 10

   See also
   polygons2d, polylineSelfIntersections

0001 function varargout = polygonSelfIntersections(poly, varargin)
0002 %POLYGONSELFINTERSECTIONS Find self-intersection points of a polygon.
0003 %
0004 %   PTS = polygonSelfIntersections(POLY)
0005 %   Return the position of self intersection points
0006 %
0007 %   [PTS, POS1, POS2] = polygonSelfIntersections(POLY)
0008 %   Also return the 2 positions of each intersection point (the position
0009 %   when meeting point for first time, then position when meeting point
0010 %   for the second time).
0011 %
0012 %   [...] = polygonSelfIntersections(POLY, 'tolerance', TOL)
0013 %   Specifies an additional parameter to decide whether two intersection
0014 %   points should be considered the same, based on their euclidean
0015 %   distance.
0016 %
0017 %
0018 %   Example
0019 %       % use a '8'-shaped polygon
0020 %       poly = [10 0;0 0;0 10;20 10;20 20;10 20];
0021 %       polygonSelfIntersections(poly)
0022 %       ans =
0023 %           10 10
0024 %
0025 %   See also
0026 %   polygons2d, polylineSelfIntersections
0027 %
0028 
0029 % ------
0030 % Author: David Legland
0031 % e-mail: david.legland@nantes.inra.fr
0032 % Created: 2009-06-15,    using Matlab 7.7.0.471 (R2008b)
0033 % Copyright 2009 INRA - Cepia Software Platform.
0034 
0035 %   HISTORY
0036 %   2011-06-22 fix bug when removing origin vertex (thanks to Federico
0037 %       Bonelli)
0038 
0039 tol = 1e-14;
0040 
0041 % parse optional arguments
0042 while length(varargin) > 1
0043     pname = varargin{1};
0044     if ~ischar(pname)
0045         error('Expect optional arguments as name-value pairs');
0046     end
0047     
0048     if strcmpi(pname, 'tolerance')
0049         tol = varargin{2};
0050     else
0051         error(['Unknown parameter name: ' pname]);
0052     end
0053     varargin(1:2) = [];
0054 end
0055 
0056 % ensure the last point equals the first one
0057 if sum(abs(poly(end, :)-poly(1,:)) < tol) ~= 2
0058     poly = [poly; poly(1,:)];
0059 end
0060 
0061 % compute intersections by calling algo for polylines
0062 [points, pos1, pos2] = polylineSelfIntersections(poly, 'closed', 'tolerance', tol);
0063 
0064 % It may append that first vertex of polygon is detected as intersection,
0065 % the following tries to detect this.
0066 % (pos1 < pos2 by construction)
0067 n = size(poly, 1) - 1;
0068 inds = abs(pos1) < tol & abs(pos2 - n) < tol;
0069 points(inds, :) = [];
0070 pos1(inds)   = [];
0071 pos2(inds)   = [];
0072 
0073 
0074 %% Post-processing
0075 
0076 % process output arguments
0077 if nargout <= 1
0078     varargout = {points};
0079 elseif nargout == 3
0080     varargout = {points, pos1, pos2};
0081 end