Math Is Fun Forum / Post a reply

You are not logged in.

Index
» Coder's Corner
» Intersecting line segments algorithm

Post a reply

Write your message and submit

Name

E-mail

Enter Answer:

Message

[quote=luca-deltodesco]define your two line segments as A[sub]0[/sub] to A[sub]1[/sub] and B[sub]0[/sub] to B[sub]1[/sub] so that you can imagine them as a couple of rays [math] V = A_1-A_0, \ Q = B_1-B_0 [/math]
so that you have [math] A_t = A + Vt,\  B_s = B + Qs\  :\  0 \leq t,s \leq 1 [/math] removing the 0 index for easier reading

then you have the condition:

[math] A + Vt = B + Qs : 0 \leq t,s \leq 1 [/math]

this isn't nice to work with, so lets look at it a different way:

as you move along the B ray, and take a vector from A[0] to B[s] the point at which the two rays intersect, is when this vector is parallel to V, or that its perpendicular vector is perpendicular to V: the reason for this is that to find if two vectors are parallel, you have to dot them, and check that the value of the dot product is plus-minus the product of the two magnitudes, whereas checking for perpendicular vectors, no matter what their magnitudes are, the dot product is 0 if they are perpendicular, so you don't need to work out their lengths

if we define a unary operator [math] (x\vec{i} + y\vec{j})_\perp = (y\vec{i} - x\vec{j})[/math] which is just the same as having the vector transformed by a 90 degree rotation matrix, so all rules apply the same as multiplying with a matrix

So we have:

[math]
\\(B + Qs - A)_\perp\cdot V = 0
\\(B-A)_\perp\cdot V + Q_\perp\cdot V s = 0
\\Q_\perp\cdot V s = (A-B)_\perp\cdot V
\\
\\ s = \frac{(A-B)_\perp\cdot V}{Q_\perp\cdot V} = \frac{V_x(A_y-B_y) + V_y(B_x-A_x)}{V_xQ_y - V_yQ_x}
[/math]

similarly working for t you get
[math]
t = \frac{Q_x(A_y-B_y) + Q_y(B_x-A_x)}{V_xQ_y - V_yQ_x}
[/math]

note that the denominators are the same, so you can pre-compute the inverse of the denominator for faster execution time:
the only time this fails is if Q and V are parallel, in which case the denominator is 0, but in this case it is either that they never intersect (even going past limits of line segment) or that they are the same line segment

then you would do it like this:

[code]calculate inverse of denominator
calculate s
if (s < 0 || s > 1) return false
calculate t
return (t >= 0 && t<=1)[/code]
so with this you can find if they intersect, and if they do intersect, use either the value for s or t to calculate the exact intersection point[/quote]

BBCode: on
[img] tag: on
Smilies: on

Options

Never show smilies as icons for this post

Go back

Topic review (newest first)

bossk171: 2007-11-06 09:39:06

I think it's the vector notation I'm getting hung up on. The explanation: "In otherwords, he is defining two infinite lines, finding where they intersect, and then seeing if the lines fall within the boundaries of the line segments." really helps though.

Thanks for really breaking it down for me guys, and especially thanks for posting that fla.

luca-deltodesco: 2007-11-06 02:48:34

here is a flash (i have CS3 so i could only export at minimum to flash 8) http://ngup.net/uploads/217476_mif.fla

and heres the corresponding swf for it: http://ngup.net/uploads/mif.swf (drag points)

mikau: 2007-11-05 04:26:03

luca is creating parametrically defined lines. suppose you have the line from (a,b) to (c,d). This consists of all points of the form (x,y) = (a, b) + t[(c,d) - (a,b)] for any t you pick, this gives you the point you reach if you start at (a, b) and walk t times the distance from (a,b) to (c,d), walking directly towards (c,d). Note, if you chose t= 1/2, you have (a,b) + 1/2(c,d) - 1/2(a,b) = 1/2[(a,b) + (c,d)] which is the midpoint between the two, which is what we'd expect. Further, if we walk 1 times the distance from (a,b) to (c,d) we should end up at (c,d), and indeed (a,b) + 1[(c,d) - (a,b)] = (a,b) + 1(c,d) - 1(a,b) = (c,d).

The point is, if you pick a t greater than 1 or less than zero, you are no longer finding a point that lies partway between the two. What luca is doing is finding two parametrically defined lines that define the two given line segments. In one line, the parameter is t, in the other it is s, he is then finding for what values of t and s these two lines intersect. If either of them are greater than 1 or less than zero, then you have to 'walk outside' the two line segments in order to reach the intersection point. Why? if t > 1, then we are talking about a point that lies further than the whole distance from (a,b) to (c,d), which means they do not intersect within those boundaries. Further, if t < 0, then t is negative, which means we are starting at (a,b) and walking backwards, away from (c,d) which certainly means the intersection point does not lie somewhere between (a,b) and (c,d).

In otherwords, he is defining two infinite lines, finding where they intersect, and then seeing if the lines fall within the boundaries of the line segments.

Does that make sense? Do you understand the vector notation luca is using?

bossk171: 2007-11-04 14:23:22

I really hate to say this but... what?

Am I missing something here? That still seems really confusing.

luca-deltodesco: 2007-11-03 23:09:35

define your two line segments as A₀ to A₁ and B₀ to B₁ so that you can imagine them as a couple of rays

so that you have removing the 0 index for easier reading

then you have the condition:

this isn't nice to work with, so lets look at it a different way:

as you move along the B ray, and take a vector from A[0] to B[s] the point at which the two rays intersect, is when this vector is parallel to V, or that its perpendicular vector is perpendicular to V: the reason for this is that to find if two vectors are parallel, you have to dot them, and check that the value of the dot product is plus-minus the product of the two magnitudes, whereas checking for perpendicular vectors, no matter what their magnitudes are, the dot product is 0 if they are perpendicular, so you don't need to work out their lengths

if we define a unary operator which is just the same as having the vector transformed by a 90 degree rotation matrix, so all rules apply the same as multiplying with a matrix

So we have:

similarly working for t you get

note that the denominators are the same, so you can pre-compute the inverse of the denominator for faster execution time:
the only time this fails is if Q and V are parallel, in which case the denominator is 0, but in this case it is either that they never intersect (even going past limits of line segment) or that they are the same line segment

then you would do it like this:

Code:

calculate inverse of denominator
calculate s
if (s < 0 || s > 1) return false
calculate t
return (t >= 0 && t<=1)

so with this you can find if they intersect, and if they do intersect, use either the value for s or t to calculate the exact intersection point

bossk171: 2007-11-03 13:45:28

I'm working on a Flash game, and I can't come up with a simple algorithm to test if to line segments intersect.

I know I can do it, but as I go along things get more and more complicated (which means: more room for bugs) and I keep thinking there's got to be and easier way of doing it.

So I googled it, and came across this essay on a "sweep line algorithm" but that seems even more complicated then the way I was doing it.

Is there an easier way to do it? I know Actionscript isn't a very popular programming language (unless you're into game design) so if someone can just give me the theory, or maybe an example in C++ (that's the only other language I know) I would really appreciate it.

I really feel like I'm missing something here, this should be real easy, and yet...

Ads

Menu

Post a reply

Topic review (newest first)

Code:

Board footer

Login

Ads

Menu

Post a reply

Topic review (newest first)

Code:

Board footer