intersectLinePolyline

INTERSECTLINEPOLYLINE Intersection points between a line and a polyline.

   P = intersectLinePolyline(LINE, POLY)
   Returns the intersection points of the lines LINE with polyline POLY. 
   LINE is a 1-by-4 row vector containing parametric representation of the
   line (in the format [x0 y0 dx dy], see the function 'createLine' for
   details). 
   POLY is a NV-by-2 array containing coordinates of the polyline vertices
   P is a K-by-2 array containing the coordinates of the K intersection
   points.

   P = intersectLinePolyline(LINE, POLY, TOL)
   Specifies the tolerance for geometric tests. Default is 1e-14.

   [P INDS] = intersectLinePolyline(...)
   Also returns the indices of edges involved in intersections. INDS is a
   K-by-1 column vector, such that P(i,:) corresponds to intersection of
   the line with the i-th edge of the polyline. If the intersection occurs
   at a polyline vertex, the index of only one of the two neighbor edges
   is returned. 
   Note that due to numerical approximations, the use of function
   'isPointOnEdge' may give results not consistent with this function.


   Examples
   % compute intersections between a square and an horizontal line
     poly = [0 0;10 0;10 10;0 10];
     line = [5 5 1 0];
     intersectLinePolyline(line, poly)
     ans =
           10     5
     % also return indices of edges
     [inters inds] = intersectLinePolyline(line, poly)
     inters =
           10     5
     inds =
           2
      
   % compute intersections between a square and a diagonal line
     poly = [0 0;10 0;10 10;0 10];
     line = [5 5 1 1];
     intersectLinePolyline(line, poly)
     ans =
            0     0
           10    10

   See Also
   lines2d, polylines2d, intersectLines, intersectLinePolygon

0001 function [intersects, edgeIndices] = intersectLinePolyline(line, poly, varargin)
0002 %INTERSECTLINEPOLYLINE Intersection points between a line and a polyline.
0003 %
0004 %   P = intersectLinePolyline(LINE, POLY)
0005 %   Returns the intersection points of the lines LINE with polyline POLY.
0006 %   LINE is a 1-by-4 row vector containing parametric representation of the
0007 %   line (in the format [x0 y0 dx dy], see the function 'createLine' for
0008 %   details).
0009 %   POLY is a NV-by-2 array containing coordinates of the polyline vertices
0010 %   P is a K-by-2 array containing the coordinates of the K intersection
0011 %   points.
0012 %
0013 %   P = intersectLinePolyline(LINE, POLY, TOL)
0014 %   Specifies the tolerance for geometric tests. Default is 1e-14.
0015 %
0016 %   [P INDS] = intersectLinePolyline(...)
0017 %   Also returns the indices of edges involved in intersections. INDS is a
0018 %   K-by-1 column vector, such that P(i,:) corresponds to intersection of
0019 %   the line with the i-th edge of the polyline. If the intersection occurs
0020 %   at a polyline vertex, the index of only one of the two neighbor edges
0021 %   is returned.
0022 %   Note that due to numerical approximations, the use of function
0023 %   'isPointOnEdge' may give results not consistent with this function.
0024 %
0025 %
0026 %   Examples
0027 %   % compute intersections between a square and an horizontal line
0028 %     poly = [0 0;10 0;10 10;0 10];
0029 %     line = [5 5 1 0];
0030 %     intersectLinePolyline(line, poly)
0031 %     ans =
0032 %           10     5
0033 %     % also return indices of edges
0034 %     [inters inds] = intersectLinePolyline(line, poly)
0035 %     inters =
0036 %           10     5
0037 %     inds =
0038 %           2
0039 %
0040 %   % compute intersections between a square and a diagonal line
0041 %     poly = [0 0;10 0;10 10;0 10];
0042 %     line = [5 5 1 1];
0043 %     intersectLinePolyline(line, poly)
0044 %     ans =
0045 %            0     0
0046 %           10    10
0047 %
0048 %   See Also
0049 %   lines2d, polylines2d, intersectLines, intersectLinePolygon
0050 %
0051 
0052 %   ---------
0053 %   author : David Legland
0054 %   INRA - TPV URPOI - BIA IMASTE
0055 %   created the 31/10/2003.
0056 %
0057 
0058 %   HISTORY
0059 %   2008-11-24 rename 'pi' as 'intersects', update doc
0060 %   2009-07-23 removed forgotten occurence of 'pi' variable (thanks to Bala
0061 %       Krishnamoorthy)
0062 %   2010-01-26 rewrite using vectorisation
0063 %   2011-05-20 returns unique results
0064 %   2011-07-20 returns intersected edge indices
0065 %   2012-11-33 add 'diag' option for linePosition
0066 
0067 % get computation tolerance
0068 tol = 1e-14;
0069 if ~isempty(varargin)
0070     tol = varargin{1};
0071 end
0072 
0073 % create the array of edges
0074 N = size(poly, 1);
0075 edges = [poly(1:N-1, :) poly(2:N, :)];
0076 
0077 % compute intersections with supporting lines of polyline edges
0078 supportLines = edgeToLine(edges);
0079 intersects = intersectLines(line, supportLines, tol);
0080 
0081 % find edges that are not parallel to the input line
0082 inds = find(isfinite(intersects(:, 1)));
0083 
0084 % compute position of intersection points on corresponding lines
0085 pos = linePosition(intersects(inds, :), supportLines(inds, :), 'diag');
0086 
0087 % and keep only intersection points located on edges
0088 b = pos > -tol & pos < 1+tol;
0089 inds = inds(b);
0090 intersects = intersects(inds, :);
0091 
0092 % remove multiple vertices (can occur for intersections located at polyline
0093 % vertices)
0094 [intersects, I, J] = unique(intersects, 'rows'); %#ok<ASGLU>
0095 
0096 if nargout > 1
0097     % return indices of edges involved in intersection
0098     % (in case of intersection located at a vertex, only one of the
0099     % neighbor edges is returned)
0100     edgeIndices = inds(I);
0101 end