require('pathfinding/vertex');

--[[
	Finds the point along two segments (points vertex1,vertex2 and vertex3,vertex4) that intersect.
	If constrain is true, then the two segments must overlap. Otherwise, the intersection point may be outside of the segments.

	Returns a Vertex at the point of intersection if one is available, otherwise returns nil
]]
function lineIntersection(vertex1, vertex2, vertex3, vertex4, constrain)
	assert(vertex1 and vertex2 and vertex3 and vertex3);
	assert(vertex1.x and vertex1.y);
	assert(vertex2.x and vertex2.y);
	assert(vertex3.x and vertex3.y);
	assert(vertex4.x and vertex4.y);

	local line1 = {x1 = vertex1.x, y1 = vertex1.y, x2 = vertex2.x, y2 = vertex2.y};
	local line2 = {x1 = vertex3.x, y1 = vertex3.y, x2 = vertex4.x, y2 = vertex4.y};
	local denominator = (line1.x2 - line1.x1)*(line2.y2 - line2.y1) - (line2.x2 - line2.x1)*(line1.y2 - line1.y1);

	-- If denominator is 0, lines are parallel
	if( denominator == 0 ) then
		return nil;
	end

	local nA	=	(line2.x2 - line2.x1)*(line1.y1 - line2.y1) - (line2.y2 - line2.y1)*(line1.x1 - line2.x1);
	local nB	=	(line1.x2 - line1.x1)*(line1.y1 - line2.y1) - (line1.y2 - line1.y1)*(line1.x1 - line2.x1);

	-- Calculate intermediate fractional point
	local uA	=	nA / denominator;
	local uB	=	nB / denominator;

	-- We could check if fractional point (both uA and uB) is between (or includes) 0 and 1
	-- to check if the segments overlap
	if( constrain ) then
		if( uA < 0 or uA > 1 or uB < 0 or uB > 1 ) then
			return nil;
		end
	end

	local nX	=	line1.x1 + (uA * (line1.x2 - line1.x1));
	local nY	=	line1.y1 + (uA * (line1.y2 - line1.y1));
	return Vertex(nX, nY);
end