%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% This file is part of NS2DDV.                                                      %
%                                                                                   %
% Copyright(C) 2011-2018    C. Calgaro  (caterina.calgaro@math.univ-lille1.fr)      %
%                           E. Creusé   (emmanuel.creuse@math.univ-lille1.fr)       %
%                           T. Goudon   (thierry.goudon@inria.fr)                   %
%                           A. Mouton   (alexandre.mouton@math.univ-lille1.fr)      %
%                                                                                   %
% NS2DDV is free software: you can redistribute it and/or modify it under the terms %
% of the GNU General Public License as published by the Free Software Foundation,   %
% either version 3 of the License, or (at your option) any later version.           %
%                                                                                   %
% NS2DDV is distributed in the hope that it will be useful, but WITHOUT ANY         %
% WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A   %
% PARTICULAR PURPOSE. See the GNU General Public License for more details.          %
%                                                                                   %
% You should have received a copy of the GNU General Public License along with      %
% NS2DDV. If not, see <http://www.gnu.org/licenses/>.                               %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function[P] = intersection(A, B, C, D)

	% INPUT
	% A, B, C, D	Four 2D points
	%
	% OUTPUT
	% P				The intersection of lines (A,B) and (C,D)

	II = B-A;
	JJ = D-C;
	if (abs(II(1)*JJ(2)-II(2)*JJ(1)) > 0.)
		m = -(-II(1)*A(2)+II(1)*C(2)+II(2)*A(1)-II(2)*C(1))/(II(1)*JJ(2)-II(2)*JJ(1));
		k = -(A(1)*JJ(2)-C(1)*JJ(2)-JJ(1)*A(2)+JJ(1)*C(2))/(II(1)*JJ(2)-II(2)*JJ(1));
		if ((min(m,k) >= 0.) && (max(m,k) <= 1.))
			% Intersection in segments [A,B] and [C,D]
			P = A + k*II;
		else
			% The segments [A,B] and [C,D] do not intersect but the lines (A,B) and (C,D) do
			P = A + k*II;
		end
	else
		% No intersection
		P = NaN(1)*ones(2,1);
	end

end