% POINTINCONVEXPOLY Determine if a 2D point is within a convex polygon
%
% Usage:  v = pointinconvexpoly(p, poly)
%
% Arguments:   p - 2D point.
%           poly - Convex polygon defined as a series of vertices in
%                  sequence, clockwise or anticlockwise around the polygon as
%                  a 2 x N array.
%
% Returns:    v - +1 if within the polygon
%                 -1 if outside
%                  0 if on the boundary
%
% Warning:  There is no check to see if the polygon is indeed convex.

% Strategy: Determine whether, in traveling from p to a vertex and then to the
% following vertex, we turn clockwise or anticlockwise.  If for every vertex we
% turn consistently clockwise, or consistently anticlockwise we are inside the
% polygon.  If for one of the vertices we did not turn clockwise or
% anticlockwise then we must be on the boundary.

% Peter Kovesi
% pk@peterkovesi.com
% May 2015

function v = pointinconvexpoly(p, poly)
    
    [dim, N] = size(poly);
    
    if length(p) ~= 2 || dim ~= 2
        error('Data must be 2D');
    end
    
    % Append a copy of the first vertex to the end for convenience
    poly = [poly poly(:,1)];  % We now have N+1 vertices
    
    % Determine whether, in traveling from p to a vertex and then to the
    % following vertex, we turn clockwise or anticlockwise
    c = zeros(N,1);
    for n = 1:N
        c(n) = clockwise(p, poly(:,n), poly(:,n+1));
    end
    
    % If for every vertex we turn consistently clockwise, or consistently
    % anticlockwise we are inside the polygon.  If for one of the vertices we
    % did not turn clockwise or anticlockwise then we must be on the
    % boundary. 
    if all(c >= 0) || all(c <= 0)
        if any(c==0)  % We are on the boundary
            v = 0;
        else          % We are inside
            v = 1;
        end
    else              % We are outside
        v = -1;
    end
    
%----------------------------------------------------------------------
% Determine whether, in traveling from p1 to p2 to p3 we turn clockwise or
% anticlockwise.  Returns +1 for clockwise, -1 for anticlockwise, and 0 for
% p1, p2, p3 in a straight line.
    
function v = clockwise(p1, p2, p3)
    
    % Form vectors p1->p2 and p2->p3 with z component = 0, form cross product
    % if the resulting z value is -ve the vectors turn clockwise, if +ve
    % anticlockwise, and if 0 the points are in a line.
        
    v = -sign((p2(1)-p1(1))*(p3(2)-p2(2)) - (p2(2)-p1(2))*(p3(1)-p2(1)));