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 *L _{1}* and

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 *L _{1}* to

*Θ _{L1L2}* =

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 *Q _{i}* (

*Θ _{L1Qi}* =

Now, we're done computing everything with *L _{1}*. We're half-way there. Next, we repeat the calculations against

*Θ _{L2L1}* =

Then, you'll calculate your angles for *Q* in regards to *L _{2}*:

*Θ _{L2Qi}* =

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}* >

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.