intersectEdgePolygon

INTERSECTEDGEPOLYGON  Intersection point of an edge with a polygon.

   INTER = intersectEdgePolygon(EDGE, POLY)
   Computes intersection(s) point(s) between the edge EDGE and the polygon
   POLY. EDGE is given by [x1 y1 x2 y2]. POLY is a N-by-2 array of vertex
   coordinates.
   INTER is a M-by-2 array containing coordinates of intersection(s). It
   can be empty if no intersection is found.

   [INTER, INDS] = intersectEdgePolygon(EDGE, POLY)
   Also returns index/indices of edge(s) involved in intersections.

   Example
   % Intersection of an edge with a square
     poly = [0 0;10 0;10 10;0 10];
     edge = [9 2 9+3*1 2+3*2];
     exp = [10 4];
     inter = intersectEdgePolygon(edge, poly)
     ans =
         10   4

   See also
     edges2d, polygons2d, intersectLinePolygon, intersectRayPolygon

0001 function [intersects, inds] = intersectEdgePolygon(edge, poly, varargin)
0002 %INTERSECTEDGEPOLYGON  Intersection point of an edge with a polygon.
0003 %
0004 %   INTER = intersectEdgePolygon(EDGE, POLY)
0005 %   Computes intersection(s) point(s) between the edge EDGE and the polygon
0006 %   POLY. EDGE is given by [x1 y1 x2 y2]. POLY is a N-by-2 array of vertex
0007 %   coordinates.
0008 %   INTER is a M-by-2 array containing coordinates of intersection(s). It
0009 %   can be empty if no intersection is found.
0010 %
0011 %   [INTER, INDS] = intersectEdgePolygon(EDGE, POLY)
0012 %   Also returns index/indices of edge(s) involved in intersections.
0013 %
0014 %   Example
0015 %   % Intersection of an edge with a square
0016 %     poly = [0 0;10 0;10 10;0 10];
0017 %     edge = [9 2 9+3*1 2+3*2];
0018 %     exp = [10 4];
0019 %     inter = intersectEdgePolygon(edge, poly)
0020 %     ans =
0021 %         10   4
0022 %
0023 %   See also
0024 %     edges2d, polygons2d, intersectLinePolygon, intersectRayPolygon
0025 %
0026 
0027 % ------
0028 % Author: David Legland
0029 % e-mail: david.legland@inrae.fr
0030 % Created: 2012-02-24,    using Matlab 7.9.0.529 (R2009b)
0031 % Copyright 2012 INRA - Cepia Software Platform.
0032 
0033 % get computation tolerance
0034 tol = 1e-14;
0035 if ~isempty(varargin)
0036     tol = varargin{1};
0037 end
0038 
0039 % get supporting line of edge
0040 line = edgeToLine(edge);
0041 
0042 % compute all intersections of supporting line with polygon
0043 [intersects, inds, pos] = intersectLinePolygon(line, poly, tol);
0044 
0045 % keep only intersection points located on the edge
0046 if ~isempty(intersects)
0047     keep = pos >= -tol & pos <= (1+tol);
0048     intersects = intersects(keep, :);
0049     inds = inds(keep);
0050 end