function inside = polygon_contains_point ( px, py, qx, qy )

%*****************************************************************************80
%
%% polygon_contains_point() finds if a point is inside a simple polygon.
%
%  Discussion:
%
%    A simple polygon is one whose boundary never crosses itself.
%    The polygon does not need to be convex.
%
%  Licensing:
%
%    This code is distributed under the MIT license.
%
%  Modified:
%
%    06 May 2020
%
%  Author:
%
%    John Burkardt
%
%  Reference:
%
%    M Shimrat,
%    Position of Point Relative to Polygon,
%    ACM Algorithm 112,
%    Communications of the ACM,
%    Volume 5, Number 8, page 434, August 1962.
%
%  Input:
%
%    real PX(N), PY(N): the coordinates of the vertices of the polygon.
%
%    real QX, QY: the coordinates of the point to be tested.
%
%  Output:
%
%    logical INSIDE: TRUE if the point is inside the polygon.
%
  inside = false;

  n = length ( px );

  x1 = px(n);
  y1 = py(n);

  for i = 1 : n

    x2 = px(i);
    y2 = py(i);

    if ( ( y1 < qy && qy <= y2 ) || ( qy <= y1 && y2 < qy ) )
      if ( ( qx - x1 ) - ( qy - y1 ) * ( x2 - x1 ) / ( y2 - y1 ) < 0.0 )
        inside = ~ inside;
      end
    end

    x1 = x2;
    y1 = y2;

  end

  return
end
