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 % E-mail: david.legland@inrae.fr
0055 % Created: 2003-10-31
0056 % Copyright 2003-2024 INRA - TPV URPOI - BIA IMASTE
0057 
0058 % get computation tolerance
0059 tol = 1e-14;
0060 if ~isempty(varargin)
0061     tol = varargin{1};
0062 end
0063 
0064 % create the array of edges
0065 N = size(poly, 1);
0066 edges = [poly(1:N-1, :) poly(2:N, :)];
0067 
0068 % compute intersections with supporting lines of polyline edges
0069 supportLines = edgeToLine(edges);
0070 intersects = intersectLines(line, supportLines, tol);
0071 
0072 % find edges that are not parallel to the input line
0073 inds = find(isfinite(intersects(:, 1)));
0074 
0075 % compute position of intersection points on corresponding lines
0076 pos = linePosition(intersects(inds, :), supportLines(inds, :), 'diag');
0077 
0078 % and keep only intersection points located on edges
0079 b = pos > -tol & pos < 1+tol;
0080 inds = inds(b);
0081 intersects = intersects(inds, :);
0082 
0083 % remove multiple vertices (can occur for intersections located at polyline
0084 % vertices)
0085 [intersects, I, J] = unique(intersects, 'rows'); %#ok<ASGLU>
0086 
0087 if nargout > 1
0088     % return indices of edges involved in intersection
0089     % (in case of intersection located at a vertex, only one of the
0090     % neighbor edges is returned)
0091     edgeIndices = inds(I);
0092 end