Time for another practical application of [url=http://www.socoder.net/index.php?article=37007]vector maths[/url]! In this article, we'll look at how to use vectors to detect the intersection of rays and line segments in two dimensions.
[h2]Rays, Line Segments and y=m*x+c[/h2]
First up, some quick definitions: a 'line segment' is what you might traditionally think of as just a 'line' - a straight line between two points! But really a line, which we shall call a 'ray', is infinitely long. A line segment can be thought of as a finite section of a ray.
When you've used rays in the past, you will probably have represented them on a graph with a formula like [i]y=m*x+c[/i]. If you wanted to intersect two rays, you would have equated the [i]y[/i] coordinates to find [i]x[/i], then plugged [i]x[/i] back in to find [i]y[/i].
There are two problems with this. First, it is annoying to write a program to solve equations in the same way a person would. Secondly, and more damningly, the [i]y=m*x+c[/i] representation cannot represent all rays! Vertical rays do not have a defined gradient, so cannot be represented in this way.
For these reasons, we shall seek a different way of defining rays and line segments.
[h2]A Vector Representation[/h2]
We can do it with vectors! It is important to remember that all vectors are 'cast' from the origin, so we can't just use a single vector. Also, what we require is an equation describing all vectors from the origin to points on the ray we wish to define, so we will need a variable scalar quantity to find individual points on the ray, in the same way we vary [i]x[/i] in [i]y=m*x+c[/i] to find [i]y[/i].
Given this, we shall represent any 2D vector using two vectors and a scalar. The first vector should be any point on the ray - an 'anchor' point to cast the rest of the ray from. The second vector should point in the direction of the ray, and by multiplying this by our scalar variable and adding it to the anchor, we can then get any point on the ray.
This would look something like this:
[thumb]http://socoder.net/uploads/56/ep5_raydef.JPG[/thumb]
That gives us a nice way of representing any ray using two vectors and a scalar. But what about line segments? Well, since a line segment is simply a section of a ray, we can define a line segment by specifically making the anchor vector one end of the line, and the direction vector the length and direction of the line. By restricting our scalar to be between 0 and 1 inclusive, we have defined a line segment. This method of defining a line segment from a ray will be important later.
Note that there are an unlimited number of ways of defining a particular ray using this method, since the anchor vector can be anywhere on the line and the direction vector may have any non-zero magnitude. However, there is only one way of defining a line segment in the way we described (or two, if you count two similar line segments in opposite directions as equivalent).
[h2]Distributive Property of the Dot Product[/h2]
Before we go on to produce the equations we need to find a point of intersection, we need to know about the 'distributive property' of the dot product.
A binary operator is 'distributive' if applying it to a sum of variables yields the same result as applying it individually to each term, then summing these results. For instance, multiplication is distributive:
[code]a * (b + c) = (a * b) + (a * c) = (b + c) * a[/code]
The dot product is also distributive, which I shall now prove. Recall that the dot product of two vectors (a,b) and (c,d) is defined as:
[code](a,b) . (c,d) = a*c + b*d[/code]
So, we seek to show that:
[code]
(a,b) . ( (c,d) + (e,f) ) = ( (a,b) . (c,d) ) + ( (a,b) . (e,f) )
= ( (c,d) + (e,f) ) . (a.b)[/code]
We do this as follows:
[code](a,b) . ( (c,d) + (e,f) ) = (a,b) . (c + e, d + f)
= (a * (c + e)) + (b * (d + f))
[*] = a*c + a*e + b*d + b*f
= (a*c + b*d) + (a*e + b*f)
= ( (a,b) . (c,d) ) + ( (a,b) . (e,f) )
{Now back to [*]}
= a*c + a*e + b*d + b*f
= ((c + e) * a) + ((d + f) * b)
= (c + e, d + f) . (a,b)
= ( (c,d) + (e,f) ) . (a,b)[/code]
[h2]Ray-Ray Intersection[/h2]
So, say we have two rays:
r1 = M + s*P
r2 = N + t*Q
Since the rays are infinitely long, they are guaranteed to intersect somewhere so long as they are not parallel. Since [i]M[/i], [i]N[/i], [i]P[/i] and [i]Q[/i] are all defined, we need to solve for [i]s[/i] or for [i]t[/i]. We could solve for both, but since we are searching for an intersection, they will both give the same position in the vector space! We will derive equations for both anyway, since they are similar.
Assuming that the rays intersect (we will deal with the parallel case momentarily), we can, as with [i]y=m*x+c[/i], simply equate our two equations, then rearrange them as follows:
[code]M + s*P = N + t*Q
s*P - t*Q = N - M[/code]
This equation has two variables in it - [i]s[/i] and [i]t[/i], so in order to solve it we need to find some way of removing one of these variables. Say we want to solve for [i]s[/i]; how do we remove the [i]t*Q[/i] term?
You will remember from the vectors tutorial that one of the properties of the dot product is that the dot product of any two perpendicular vectors is zero. It should hence be clear that if we dot product the [i]t*Q[/i] term by any vector perpendicular to [i]Q[/i], that term will become zero, and hence disappear, taking the scalar variable [i]t[/i] with it. Of course, we have to apply this dot product to the entire equation, but the distributive property of dot products introduced earlier takes care of that. Using any vector perpendicular to [i]Q[/i], which we shall call [i]perp(Q)[/i], we get:
[code]s*P - t*Q = N - M
(s*P - t*Q) . perp(Q) = (N - M) . perp(Q)
(s*P).perp(Q) - (t*Q).perp(Q) = (N - M) . perp(Q)
(s*P).perp(Q) - 0 = (N - M) . perp(Q)
(s*P) . perp(Q) = (N - M) . perp(Q)[/code]
Since the dot product gives a scalar quantity, we now have both sides of the equation as scalars rather than vectors, which means we can divide one side by the other. Before dividing, we shall first use the properties of scalar multiplication with the dot product to extract [i]s[/i] out of our dot product.
[code](s*P) . perp(Q) = (N - M) . perp(Q)
s * (P . perp(Q)) = (N - M) . perp(Q)
s = ((N - M) . perp(Q)) / (P . perp(Q))[/code]
We have now solved for [i]s[/i]! By a very similar method, dot product-ing by a vector perpendicular to [i]P[/i] instead of [i]Q[/i], we can derive an equation for [i]t[/i] as follows:
[code]M + s*P = N + t*Q
t*Q - s*P = M - N
(t*Q - s*P) . perp(P) = (M - N) . perp(P)
(t*Q).perp(P) - (s*P).perp(P) = (M - N) . perp(P)
(t*Q).perp(P) - 0 = (M - N) . perp(P)
(t*Q) . perp(P) = (M - N) . perp(P)
t * (Q . perp(P)) = (M - N) . perp(P)
t = ((M - N) . perp(P)) / (Q . perp(P))[/code]
[h2]Gimme Da Codez![/h2]
In order to convert this into code, we need to consider a few things. Firstly, do the rays even intersect? We mentioned before that if the rays are parallel, there will be no intersection. How can we test for this? Well, remember that perpendicular lines have zero dot product; hence, if our two lines are parallel, taking the dot product of the direction of one and a vector perpendicular to the direction of the other will give zero! This is convenient, since it is the denominator in both of the equations we just derived, and if that had value zero, we would be unable to solve our equation!
The second thing to consider is how to calculate a vector perpendicular to another. This is actually fairly straightforward: the vector (x,y) has (y,-x) perpendicular to it. Alternatively you could use (-y,x), or any scalar multiple of either, but it helps to be consistent.
If you wished, you could implement a vector class in the language you are using, and then implement the earlier equations directly. However, on the assumption that you'd rather just have the straight maths using scalars, here is the final code. We first check that our rays are not parallel, then calculate a value for [i]s[/i], then use this to calculate the point of intersection. What follows is pseudocode.
[code]function detectIntersection(mX, mY, pX, pY, nX, nY, qX, qY)
{
// Calculate divisor and ensure it is non-zero
divisor = pX * qY - pY * qX
if divisor == 0
// Lines are parallel! Terminate here!
return null
endif
// Calculate point of intersection
s = ((nX-mX) * qY - (nY-mY) * qX) / divisor
intersectX = mX + s * pX
intersectY = mY + s * pY
return Vector(intersectX, intersectY)
}[/code]
[h2]What about Line Segments?[/h2]
We now know how to easily find where two rays intersect, but what about line segments? Well, remember how we defined line segments to be like rays, but with their scalar variable restricted to be between 0 and 1 inclusive? We can use this to make a simple modification to our function to check that our calculated point of intersection lies on our line segment.
To intersect a line segment and a ray, the modification is simple. Taking the line segment to be the first 'ray', and the ray to be second:
[code]function detectIntersection(mX, mY, pX, pY, nX, nY, qX, qY)
{
// Calculate divisor and ensure it is non-zero
divisor = pX * qY - pY * qX
if divisor == 0
// Lines are parallel! Terminate here!
return null
endif
// Calculate point of intersection
s = ((nX-mX) * qY - (nY-mY) * qX) / divisor
if s >= 0 && s <= 1
// Intersection is within line segment
intersectX = mX + s * pX
intersectY = mY + s * pY
return Vector(intersectX, intersectY)
else
// Intersection is outside line segment, so there is no intersection
return null
endif
}[/code]
If we want to intersect two line segments, we will need to perform this check for both segments, which means we will need to calculate [i]t[/i] as well as [i]s[/i]:
[code]function detectIntersection(mX, mY, pX, pY, nX, nY, qX, qY)
{
// Calculate both divisors and ensure segments are not parallel (we need only check one divisor, since divisorS = -divisorT)
divisorS = pX * qY - pY * qX
divisorT = qX * pY - qY * pX
if divisorS == 0
// Lines are parallel! Terminate here!
return null
endif
// Calculate point of intersection
s = ((nX-mX) * qY - (nY-mY) * qX) / divisorS
t = ((mX-nX) * pY - (mY-nY) * pX) / divisorT
if s >= 0 && s <= 1 && t >= 0 && t <= 1
// Intersection is within both line segments
intersectX = mX + s * pX
intersectY = mY + s * pY
return Vector(intersectX, intersectY)
else
// Intersection is outside one or both line segments, so there is no intersection
return null
endif
}[/code]
[h2]Summary[/h2]
[ul][li]A 'ray' is infinitely long, while a 'line segment' is a finite portion of a ray.[/li]
[li][i]r=M+s*P[/i] is a better representation of a ray than [i]y=m*x+c[/i] when dealing with rays in code.[/li]
[li]The dot product is distributive.[/li]
[li]Ray-ray, lineseg-ray, and lineseg-lineseg intersection can all be determined fairly simply, once we have derived the equation for doing so using vector maths.[/li][/ul]
So yeah, this tutorial has been somewhat delayed since my last one, but is probably the most practical of them thus far. I've pretty much exhausted my ideas for useful programming maths now, but if anyone has any topics they'd like me to tackle, I'm open to requests! Til next time! :)
This post is from -- http://socoder.net/index.php?topic=0