Understanding line segment intersections in 2d
July 19, 2011 5:51 PM   Subscribe

I need help understanding an algorithm for determining if two line segments intersect (and at which point).

I'm working on a game and I need an algorithm for knowing if two line segments intersect in 2d, and if so, what the point of intersection is. I found a few descriptions of how to do that but I don't really get it, and I'm pretty new to cross/dot products and matrix determinants which all seem to be involved. I guess assume I have a basic but not great understanding of those topics.

here's what I'm trying to figure out right now: http://paulbourke.net/geometry/lineline2d/

it's all fuzzy, but specifically the part where he turns these equations:

x1 + ua (x2 - x1) = x3 + ub (x4 - x3)
y1 + ua (y2 - y1) = y3 + ub (y4 - y3)

into ua and ub solutions (which are images so I can't paste them). can someone explain how he does that?

there's also this stack overflow question: http://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect

the top answer seems to be the same basic thing but I don't understand why he crosses both sides with s or how he gets the solutions for t and u. any more detailed breakdown would be helpful. if anyone could give a simpler overview of how the whole algorithm works, that would be great too. thanks!
posted by Post-it Goat to Education (10 answers total)
 
Best answer: It's all fuzzy, but specifically the part where he turns these equations [...] into ua and ub solutions (which are images so I can't paste them). Can someone explain how he does that?

A standard way to solve two equations for two unknowns, like these, is to turn one of the equations into the definition of one unknown in terms of the other unknown, and then substitute that into the other equation.

So for example, you can turn the second equation into the definition of ub:

ub (y4 - y3) = y1 + ua (y2 - y1) - y3
ub = (y1 + ua (y2 - y1) - y3) / (y4 - y3)

and then substitute that into the first equation:

x1 + ua (x2 - x1) = x3 + ub (x4 - x3)
x1 + ua (x2 - x1) = x3 + ( (y1 + ua (y2 - y1) - y3) / (y4 - y3)) * (x4 - x3)

Now you have a single equation for ua. Solve that and you should end up with the same thing he did.
posted by dfan at 6:19 PM on July 19, 2011


Best answer: It's a system of equations built from the slope intersect line form, y = m x + b. In this case, you have two equations because you're dealing with two dimensions.

The lines here are each defined by two points. (x1, y1) and (x2, y2) lie on the first line, and (x3, y3) and (x3, y3) lie on the second.

Breakdown of the first equation:

x1 + ua (x2 - x1) is the x component of the first line as a function of ua.

x3 + ua (x2 - x1) is the x component of the second line as a function of ub.

So the first equation is true only if ua and ub are such that the x components of the two lines meet. The second equation does the same thing, but for the y components.

This is a straight-up algebra approach, it doesn't need cross or dot products, although you can use those to get there as well (and doing this with vectors instead of scalars would simplify the notation a lot).
posted by qxntpqbbbqxl at 6:19 PM on July 19, 2011 [1 favorite]


Oops, x3 + ua (x4 - x3)
posted by qxntpqbbbqxl at 6:21 PM on July 19, 2011 [1 favorite]


ub


Copy and paste fail
posted by qxntpqbbbqxl at 6:22 PM on July 19, 2011 [1 favorite]


Back up just a moment: why are you studying this? If it's for your own education, great, but please don't think that writing a game means you have to write your own graphics library from scalar arithmetic! That's been done already, repeatedly and---no offense---by smarter people than you.
posted by d. z. wang at 6:42 PM on July 19, 2011


Response by poster: thanks a lot guys, in my head I had mixed up the cross-product solution with the algebraic solution and also forgotten how to do math. I think I get it now, or at least well enough to copy one of the algorithms without feeling like I'm cheating too much.

d. z. wang, don't worry, it's for educational purposes.
posted by Post-it Goat at 7:42 PM on July 19, 2011


Best answer: specifically the part where he turns these equations: [...] into ua and ub solutions

What dfan said.

(It seems probable that the author used Cramer's rule to obtain his expressions for ua and ub. But Cramer's rule is, pretty much, just a turnkey version of the procedure that dfan describes.)

As for the stackoverflow answer:

I don't understand why he crosses both sides with s

Their mission at that moment is to solve for t (and u, but they'll do that later). In the equation they have,
p + tr = q + us ,
everything is known except t and u. Their secret plan: first get rid of u, so that the only unknown is t; then isolate t on one side of the equation using algebra.

Crossing with s is a way of getting rid of u. Let me demonstrate in slow motion. First we cross both sides with s, getting
(p + tr)×s = (q + us)×s
Now we expand everything, getting
p×s + tr×s = q×s + us×s
And as they say in their post, s×s=0 (this is a weird but useful property of the cross product), so this simplifies to
p×s + tr×s = q×s
Now u is gone, and everything is known except t, hurrah. (The author anticipated all this when they crossed with s.)

how he gets the solutions for t and u

After the above, it's algebra to isolate t. How's your algebra?

The solution for u is what mathematicians call "similar": the same ideas and steps, just with all the variables playing different roles. Now we want to solve for u instead of t, so instead of getting rid of u, we want to get rid of t, so instead of crossing with s, we cross with...

a simpler overview of how the whole algorithm works

Hm. This is a little harder to answer without knowing where you are with the math. The broadest overview I can think of is this: Points on line A have coordinates satisfying a certain equation. Points on line B have coordinates satisfying another equation. A point where these lines intersect is on both lines, so it has to have coordinates satisfying both equations. So the problem is, given a couple equations, find numbers making them both true. Everything else is technique.

But maybe this kind of overview is not what you want. Please advise.
posted by stebulus at 7:45 PM on July 19, 2011


The advantage to a vector-based approach is that it doesn't privilege non-vertical lines. Which I suppose you know already.
posted by leahwrenn at 7:54 PM on July 19, 2011 [1 favorite]


Response by poster: thanks stebulus, that clarified it some more. a key realization was how the cross product was being used to eliminate a variable and not, as I had previously assumed, for black magic. I just went through the algebra of the cross product solution from stack overflow and ended up with the same equation from the first guy's method, which is exciting.

leahwrenn, sorry, I don't know what you mean by that...
posted by Post-it Goat at 8:22 PM on July 19, 2011


leahwrenn means that you can deal with vertical lines if you use vectors, as a vertical line has infinite slope and thus cannot be expressed as y = mx + b where m is a real number.
posted by wutangclan at 11:49 PM on July 19, 2011


« Older Wireless video to a projector?   |   Help an Aunt out Newer »
This thread is closed to new comments.