Calculating intersections between two lines in 2D space is a common problem, at least for me. One possible approach to find out if there is an intersection and, if yes, where the collision exactly is uses vector analysis.
Speaking in vectors, a line between two points A and B can be defined the following way:
a is the support vector. It is measured from the origin of the coordinate system to point A (A1 stands for the x-coordinate, A2 for the y-coordinate).
b is the direction vector. It can be calculated by subtracting the coordinates of B and A.
Together these two vectors form the equation of the line between A and B:
This means that every point on the line can be described as a plus any multiple r of b. Of course points not "between" A and B are also included. To let two lines collide, one just has to equalize the two lines in the above style.
Example
Say we have two lines g and h.
The overall aim is to get a solution for the two factors r and s, as these determine if there was a collision and where it occured. After equalizing g and h and doing some calculation, one might come up with the following equations:
As one can see, the denominator is equal for both r and s. It is advisable to check it before, as it can be zero when the two lines are parallel.
Just by looking at r and s, one can now determine whether a "real" collision occured: If they both lie between 0 and 1, the lines collided. If one or both of them equal 0 or 1 exactly, one of the defining points lies on the other line. It depends on the situation whether one wants this to count as a collision.
Implementation
A possible implementation in Javascript could look like this:
Code (Javascript):
function intersectLines(ax, ay, bx, by,
cx, cy, dx, dy)
{
//calculate the direction vectors
bx -= ax;
by -= ay;
dx -= cx;
dy -= cy;
//are they parallel?
var denominator = by * dx - bx * dy;
if (denominator == 0)
return false;
//calculate point of intersection
var r = (dy * (ax-cx) - dx * (ay-cy)) / denominator;
var s = (by * (ax-cx) - bx * (ay-cy)) / denominator;
if ((s >= 0) && (s <= 1) && (r >= 0) && (r <= 1))
return {
x: (ax + r * bx),
y: (ay + r * by)
};
else
return false;
}
//Test it!
var point;
if (!(point = intersectLines(100,100,200,200,200,100,100,200)))
alert('No intersection!');
else
alert('Intersection at ('+point.x+'/'+point.y+')');
It takes 8 parameters (2 coordinates per point) and returns either false, if the lines are parallel or not intersecting, or an object containing the coordinates of the intersection. The case of identical lines is ignored here, as it is in the whole article.
Demo
I hope some people may find all this useful and I did not incorporate too many mistakes. :-)
