-=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- (c) WidthPadding Industries 1987 0|712|0 -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=-
SoCoder -> Article Home -> Advanced Techniques

 
shroom_monk
Created : 03 October 2013
Edited : 03 October 2013

Maths 101 - Episode 5: Line Intersection

How to detect line intersections with vector maths!
Time for another practical application of vector maths! In this article, we'll look at how to use vectors to detect the intersection of rays and line segments in two dimensions.

Rays, Line Segments and y=m*x+c

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 y=m*x+c. If you wanted to intersect two rays, you would have equated the y coordinates to find x, then plugged x back in to find y.

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 y=m*x+c 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.

A Vector Representation

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 x in y=m*x+c to find y.

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:


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).

Distributive Property of the Dot Product

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:


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:

So, we seek to show that:

We do this as follows:


Ray-Ray Intersection

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 M, N, P and Q are all defined, we need to solve for s or for t. 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 y=m*x+c, simply equate our two equations, then rearrange them as follows:


This equation has two variables in it - s and t, so in order to solve it we need to find some way of removing one of these variables. Say we want to solve for s; how do we remove the t*Q 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 t*Q term by any vector perpendicular to Q, that term will become zero, and hence disappear, taking the scalar variable t 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 Q, which we shall call perp(Q), we get:


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 s out of our dot product.


We have now solved for s! By a very similar method, dot product-ing by a vector perpendicular to P instead of Q, we can derive an equation for t as follows:


Gimme Da Codez!

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 s, then use this to calculate the point of intersection. What follows is pseudocode.



What about Line Segments?

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:


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 t as well as s:


Summary

  • A 'ray' is infinitely long, while a 'line segment' is a finite portion of a ray.
  • r=M+s*P is a better representation of a ray than y=m*x+c when dealing with rays in code.
  • The dot product is distributive.
  • 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.

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!

 

Comments
Friday, 04 October 2013, 02:45
Krakatomato
 		I wrote a simple Line Intersect demo on PlayMyCode ages ago that may be of use too:

www.playmycode.com/build/edit/3202

//Andy
Saturday, 07 January 2017, 21:09
Pakz
 		I am going through the tutorial and wonder.

What is equating
What is scalar
What is an anchor

I never payed attention at math class at school. To busy being invisible becourse classmates were picking on me back then.
Sunday, 08 January 2017, 14:02
shroom_monk
 		Scalars
A 'scalar' is a value that consists of one number; as opposed to a 'vector', which is a value that consists of several numbers.

So, for example, if I say that the variable s is a 'scalar', what I mean is it can take any number as a value - e.g. 2, or -5, or 3.4, etc - but it cannot be a vector such as (6, 7).

Anchors
On its own, a vector can only describe a position, or a direction from the origin (0, 0) to that position. To be able to draw any ray / line we want, we need two vectors - in this article, I have called them the 'anchor' and the 'direction'.

For (what I have called) a 'ray', since it is infinitely long, the 'anchor' vector is simply a point that we have picked on the ray for the purpose of our equation. For 'line segments', you could think of the 'anchor' as one end of the line, and the 'direction' as the vector that takes you from the anchor to the other end of the line.

(I'm not sure if there is a better mathematical term for this - there probably is. I've always just called them anchors, because they 'hold down' our ray into a particular position.)

Equating
Say I have two equations that both describe a 'similar' value - for instance, x1 = a + b and x2 = c * d. To 'equate' these two equations is to take the two similar values - in this case x1 and x2 - as being equal. This lets us create a new equation - in this case a + b = c * d.

Of course, what makes two values 'similar' depends on the context. To help explain with a concrete example from the article, let's consider intersecting two rays defined as:

r1 = M + s*P
r2 = N + t*Q

For r1, the anchor vector is M and the direction vector is P. These have fixed values that describe this particular ray. s is a scalar value that can take any value we want, and each value describes a specific point on the ray. For a specific value of scalar s, we get a specific value of vector r1 that describes the particular point.

Similarly for r2, the anchor is N, the direction is Q, and t is a scalar giving some point on the ray.

So, say I want to find out where these two rays intersect. Assuming they aren't parallel, they must intersect at precisely one point in space - let's call this point I (which is of course a vector). Since the intersection point must lie on both rays (by definition), we must want to find r1 = I and r2 = I. Both values are equal, so we can equate them!

By equating r1 = r2 we generate a new equation: M + s*P = N + t*Q. If we solved this for s and t, we would know where the two lines cross! (But as discussed in the article, we only need to solve for one of them, and use a clever dot product trick to let us do that.)