Johan van Mol .org
HomeHome
ArticlesArticles
BlogBlog
Advanced SearchAdvanced Search
Home arrow Articles arrow Flash arrow Collision detection & bouncing part 1: intersection of line segments
Collision detection & bouncing part 1: intersection of line segments Print E-mail
Sunday, 23 April 2006
Article Index
Collision detection & bouncing part 1: intersection of line segments
Slope-Intercept form
Parametric form
Flash demo and sample code

Parametric form

A line segment can be represented in a parametric form:
point1 = (xp1, yp1), point2 = (xp2, yp2)
Ux = xp1 + t * (xp2 - xp1)
Uy = yp1 + t * (yp2 - yp1)

where 0 <= t <= 1

As you can see when t = 0, x = xp1 + 0 * (xp2 - xp1) = xp1
When t = 1, x = xp1 + 1*(xp2 - xp1) = xp2
In other words when t equals 0, x equals the the first point of our line segment. When t equals 1, x equals the last point of our line segment.
The same goes for y, so when t = 0, y = yp1 and when t = 1, y = yp2

Image

E.g. for a line with point1 = (2, 4) and point2 =  (10, 8)
Ux = 2 + t * (10 - 2) => Ux = 2 + t * 8
Uy = 4 + t *  (8 - 4) => Uy = 4 + t * 4

For 2 line segments:
point1 = (xp1, yp1), point2 = (xp2, yp2), S1x = xp2 - xp1, S1y = yp2 - yp1
Ux = xp1 + t * S1x
Uy = yp1 + t * S1y
point3 = (xp3, yp3), point4 = (xp4, yp4), S2x = xp4 - xp3, S2y = yp4 - yp3
Vx = xp3 + s * S2x
Vy = yp3 + s * S2y

To find the intersection Ux must equal Vx and Uy must equal Vy.
Ux = Vx =>
xp1 + t * S1x = xp3 + s * S2x =>
s * S2x - t * S1x = xp1 - xp3
and
Uy = Vy =>
yp1 + t * S1y = yp3 + s * S2y =>
s * S2y - t * S1y = yp1 - yp3

This gives us two equations, with two unknows, which can be resolved with Cramer's rule as:
s = (-S1y * (xp1 - xp3) + S1x * (yp1 - yp3)) / (-S2x*S1y + S1x*S2y)
t = (S2x * (yp1 - yp3) - S2y * (xp1 - xp3)) / (-S2x*S1y + S1x*S2y)

s and t must be in the range between 0 and 1 to be valid.  After checking that, we can determine the x and y-coordinates of the intersection by plugging s and t into the equation for Ux and Uy:

Ux = xp1 + t * S1x
Uy = yp1 + t * S1y

example

Step 1: make equations
segment 1: point1 = (2, 4) and point2 =  (10, 8)
S1x = xp2 - xp1 = 10 - 2 = 8
S1y = yp2 - yp1 = 8 - 4 = 4
Ux = xp1 + t * S1x = 2 + t * 8
Uy = yp1 + t * S1y = 4 + t * 4

segment 2: point3 = (3, 7) and point4 =  (12, 4)
S2x = xp4 - xp3 = 12 - 3 = 9
S2y = yp4 - yp3 = 4 - 7 = -3
Vx = xp3 + s * S2x = 3 + t * 9
Vy = yp3 + s * S2y = 7 + t * -3

Step 2: Resolve s and t

s = (-S1y * (xp1 - xp3) + S1x * (yp1 - yp3)) / (-S2x*S1y + S1x*S2y) =>
s = (-4 * (2 - 3) + 8 * (4 - 7)) / (-9 * 4 + 8 * -3) =>
s = 0.33333

t = (S2x * (yp1 - yp3) - S2y * (xp1 - xp3)) / (-S2x*S1y + S1x*S2y) =>
t = (9 * (4 - 7) - -3 * (2 - 3)) / (-9 * 4 + 8 * -3) =>
t = 0.5

Step 3: check if the intersection is valid
The intersection is valid if 0 <= s <= 1 and 0 <= t <= 1
0 <= 0.3333 <= 1 and 0 <= 0.5 <= 1 so our intersection is valid

Step 4: get the intersection point

Ux = xp1 + t * S1x = 2 + 0.5 * 8 = 6
Uy = yp1 + t * S1y = 4 + 0.5 * 4 = 6



Comments
Great work on collision detection! I was searching the net for a solution to collision detection with lines and this is the best site so far! The only difficulty i have is understanding the math, particularly Cramer's rule. Other than that, everything else is quite simply explained. Keep it with the good work! :D
  Posted by israel, on Saturday, 10 March 2007 at 4:20

Thank you. it has been much more useful than anything else I found googling around.
M

  Posted by Marco, on Wednesday, 23 May 2007 at 4:54


 1 
Page 1 of 1 ( 2 comments )
©2005 MosCom

You are not authorized to leave comments - please login.