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@inrae.fr
0032 % Created: 2009-06-15, using Matlab 7.7.0.471 (R2008b)
0033 % Copyright 2009-2024 INRA - Cepia Software Platform
0034 
0035 tol = 1e-14;
0036 
0037 % parse optional arguments
0038 while length(varargin) > 1
0039     pname = varargin{1};
0040     if ~ischar(pname)
0041         error('Expect optional arguments as name-value pairs');
0042     end
0043     
0044     if strcmpi(pname, 'tolerance')
0045         tol = varargin{2};
0046     else
0047         error(['Unknown parameter name: ' pname]);
0048     end
0049     varargin(1:2) = [];
0050 end
0051 
0052 % ensure the last point equals the first one
0053 if sum(abs(poly(end, :)-poly(1,:)) < tol) ~= 2
0054     poly = [poly; poly(1,:)];
0055 end
0056 
0057 % compute intersections by calling algo for polylines
0058 [points, pos1, pos2] = polylineSelfIntersections(poly, 'closed', 'tolerance', tol);
0059 
0060 % It may append that first vertex of polygon is detected as intersection,
0061 % the following tries to detect this.
0062 % (pos1 < pos2 by construction)
0063 n = size(poly, 1) - 1;
0064 inds = abs(pos1) < tol & abs(pos2 - n) < tol;
0065 points(inds, :) = [];
0066 pos1(inds)   = [];
0067 pos2(inds)   = [];
0068 
0069 
0070 %% Post-processing
0071 
0072 % process output arguments
0073 if nargout <= 1
0074     varargout = {points};
0075 elseif nargout == 3
0076     varargout = {points, pos1, pos2};
0077 end