# How do I find the intersection of two lines

I have a bounding box on my character, its position in the previous frame an the current frame. The bounding box is axis aligned.

My character is running around inside a cave, I have a list of points (lines) that represents the wall of the cave (not axis aligned)

I've got a coarse grained algorithm that tells me when some part of my character is likely to have collided with some part of the cave wall.

I do not have a fine grained algorithm to tell me specifically which line of the wall was collided with and at which point.

My current thought was that I could just create a line for each corner of the bounding box from its position in the previous frame, to its position in the current frame, then test each of these lines for intersections with any of the lines in the cave wall.

My google fu however hasn't shown me an easy formula for calculating intersections. Have I picked a bad way to do this, or am I just bad at search?

My game is written in scala, however I can read/translate most any c style language and many scripting languages, whatever you feel like answering in

googling " intersection test line segment line segment" produced this:

http://paulbourke.net/geometry/lineline2d/

• The solution is larger than just the intersection point between two lines. Trav has a number of lines describing terrain and any part of the character could be intersecting with any part of any terrain line. – doppelgreener May 13 '11 at 1:05
• That's just a repetition of the algorithm though. The formula to test for the presence of an intersection, whether it's in the segments I'm looking at, and then get the specific location is exactly what I'm after – The Trav May 13 '11 at 1:53
• The reason I responded to the answer is because yes, it is a repetition of the algorithm, and you can brute force it. I would expect there's more to it nowadays though. I don't think just pointing out the mathematical formula for line intersection does the problem justice. What about when your level gets decently large, and you're wasting cycles checking for intersection against a totally unrelated wall? – doppelgreener May 13 '11 at 2:46
• Jonathan: Well, from the question: "I've got a coarse grained algorithm that tells me when some part of my character is likely to have collided with some part of the cave wall." Although we don't know if that coarse detail algorithm is any good or not... – Olhovsky May 13 '11 at 3:11

You can do that with different approaches;

• segment vs segment using parametric lines plus some verifications (because lines are not segments).

• segment vs box

• segment vs circle (this one would be my favorite)

. But as you request for a segment vs segment intersection test, here is a pseudo C++ example extracted from the very interesting book "Real time collision detection":

float Signed2DTriArea(Point a, Point b, Point c)
{
return (a.x - c.x) * (b.y - c.y) - (a.y - c.y) * (b.x - c.x);
}

int Test2DSegmentSegment(Point a, Point b, Point c, Point d, float &t, Point &p)
{
// signs of areas correspond to which side of ab points c and d are
float a1 = Signed2DTriArea(a,b,d); // Compute winding of abd (+ or -)
float a2 = Signed2DTriArea(a,b,c); // To intersect, must have sign opposite of a1

// If c and d are on different sides of ab, areas have different signs
if( a1 * a2 < 0.0f ) // require unsigned x & y values.
{
float a3 = Signed2DTriArea(c,d,a); // Compute winding of cda (+ or -)
float a4 = a3 + a2 - a1; // Since area is constant a1 - a2 = a3 - a4, or a4 = a3 + a2 - a1

// Points a and b on different sides of cd if areas have different signs
if( a3 * a4 < 0.0f )
{
// Segments intersect. Find intersection point along L(t) = a + t * (b - a).
t = a3 / (a3 - a4);
p = a + t * (b - a); // the point of intersection
return 1;
}
}

// Segments not intersecting or collinear
return 0;
}


Software license agreement of the book ask to include the following credit to use the code examples:

code example "from Real-Time Collision Detection by Christer Ericson, published by Morgan Kaufmaan Publishers, © 2005 Elvesier Inc"

Although someone has already provided an answer deemed satisfactory, I'm unsure the method you described will yield an accurate time of impact (TOI). My first inclination is that to find an exact answer to the question, "how far can the player move before colliding with a part of the cave, if a collision occurs at all?" requires resorting to continuous collision detection techniques (CCD).

Specifically, there is a technique whereby you can effectively "shrink" your AABB into a single point, and at the same time "grow" the line segments of the cave by the same amount by using Minkowski Addition. Then, the problem can be seen as casting a ray against a convex object, or set of convex objects (since a point moving through time with constant velocity becomes a ray). The earliest distance along the ray that intersects with the "bloated" cave will represent the earliest time of impact (TOI).

Most commonly literature on how to accomplish this deals with three dimensions, but still applies to two dimensions, and ought to transfer easily. I don't have time at the moment to spell out all the details or provide psuedo code, but maybe someone else will be able to verify and expand upon what I'm referring to. For now, here are a couple of papers that explain the process, and some terms you might be interested in Googling.

In an attempt to help others who find this in their travels, here is a 2D line intersection test using the methods as found at https://stackoverflow.com/a/1968345/431528.

inline bool lines_intersect_2d(Vector2 const& p0, Vector2 const& p1, Vector2 const& p2, Vector2 const& p3, Vector2* i const = 0) {
Vector2 const s1 = p1 - p0;
Vector2 const s2 = p3 - p2;

Vector2 const u = p0 - p2;

float const ip = 1.f / (-s2.x * s1.y + s1.x * s2.y);

float const s = (-s1.y * u.x + s1.x * u.y) * ip;
float const t = ( s2.x * u.y - s2.y * u.x) * ip;

if (s >= 0 && s <= 1 && t >= 0 && t <= 1) {
if (i) *i = p0 + (s1 * t);
return true;
}

return false;
}