Box-Line Intersections
Or, "A Line walks into a Box"

You know, when I was more young and naïve, I thought there was so much that you had to be a wizard in order to accomplish on a computer. Now, either I've become a wizard, or, with adequate time, anybody can learn this crap.

Now, I've talked ad nauseam about 3D graphics. Raytracing and vector-style. Now, for my next trick, I'll show you how to determine mathematically if line passes through an arbitrary closed polygon.

Why's this important? I'm thinking (more and more seriously) about writing a primitive 3D space-shooting game, and in order to have a combat system work, I need to figure if the laser-cannons are colliding with the binding box of a ship. To eliminate the need for a tracking system, the lasers fire instantly and work as straight lines projecting from the front of a ship.

Let me be more precise: I want an arbitrary line to pass into or through an arbitrary polygon. We'll call the line L and the polygon Q, for quadrilateral. The line is defined by two points L1 and L2. The quadrilateral (though, you can use any shape you damn-well want), is made of four points: Q1 through Q4.

Testing for the line-shape intersection could be done a couple ways. We could ensure Q isn't rotated, and iterate a bunch of test points along L to see if the x and y values of the test point are within the bounds of the box, using > and < operators. This is only silly for a dozen or so reasons. Namely, we're not raytracing. We don't care about the distance at the intersection, just if there is one. Next, it would take a lot of those calculations. Lastly, having a box that "isn't rotated" sounds like the box isn't really arbitrary, and that's one of my requirements.

Instead, we'll turn to trigonometry. I'll introduce the idea in English and then throw some math symbols at you.

This English description is probably best if you drew a picture of a square on a piece of paper. Draw a diagonal line cutting through it. Now draw a dashed line from one of the points of the square to the left-most point of the first line. Repeat making these dashed lines through for all of the points of the square to the left-most point of the original line. You'll notice that they fall on both the right and left of the original diagonal line. This is how we're going to be able to tell if the line actually goes through the square. For mathematical certainty, we have to do the same thing from the right-most point of the line.

The idea can be pretty easily expanded into three dimensions, but we won't talk about that here. It's just adding more variables and doing the same thing.

Mathematically speaking, we find the angles with our old friend atan or, as the kids write these days, tan-1. Given a proportion, it returns an angle.

We'll call our line L and our square Q (for 'quadrilateral'), through this works mathematically for any polygon, not just a plain, old square.

First, we find the angle of L1 to L2 against the X-axis. We'll call it ΘL1L2.

ΘL1L2 = atan( (L2y - L1y) / (L2x - L1x) ) + π if L2x - L1x < 0, or
ΘL1L2 = atan( (L2y - L1y) / (L2x - L1x) ) otherwise.

In most programming languages, there's an atan2 function that accepts the numerator and denominator as arguments, and there's no longer a conditional.

Next, we need the angle to all Qi (i ∈ {1,2,3,4} in this case):

ΘL1Qi = atan( (Qiy - L1y) / (Qix - L1x) ) + π if Qix - L1x < 0, or
ΘL1Qi = atan( (Qiy - L1y) / (Qix - L1x) ) otherwise.

Now, we're done computing everything with L1. We're half-way there. Next, we repeat the calculations against L2. First, the line itself:

ΘL2L1 = atan( (L1y - L2y) / (L1x - L2x) ) + π if L1x - L2x < 0, or
ΘL2L1 = atan( (L1y - L2y) / (L1x - L2x) ) otherwise.

Then, you'll calculate your angles for Q in regards to L2:

ΘL2Qi = atan( (Qiy - L2y) / (Qix - L2x) ) + π if Qix - L2x < 0, or
ΘL2Qi = atan( (Qiy - L2y) / (Qix - L2x) ) otherwise.

So, now we've got all these Θs running around. We need to compare them to each other. We can quickly say that for our test to pass:

i,j,k,l : ΘL1L2 > ΘL1QiΘL1L2ΘL1QjΘL2L1 > ΘL2QkΘL2L1ΘL2Ql

Doing it in three dimensions (C source code available here) is about double the effort. Q contains eight rather than four points for a simple bounding box. All the Θs are doubled, since we have to deal with a pitch and a yaw. This is the general idea, though.

Now you, too, can mathematically prove if a line intersects a polygon like a pro! From here, you can go back to Writings.