Intersection and Non-intersection routines

More than once I have been asked to find the solution to a simple problem related to finding the intersection of two axis aligned boxes. Also more than once I’ve stumbled during the interview even though I knew the problem was easy. What was the problem? Why was I getting confused? Attempting to figure out why, I sat down and thoroughly solved the problem and figured out why I was having issues. It turns out that I was getting confused about whether I was solving the problem looking for the intersection of the two boxes, or looking for the non-intersection of two boxes. I’ll explore both and why you would use one or the other.

What is the difference? It is basically the difference between asking these two questions:
Are the two boxes intersecting?
Are the two boxes separated (not intersecting)?

I am going to post the solutions I came up with and then analyze what the differences are and why one might use one version or the other.

Here is the basic structure of the axis aligned boxes that I will assume we will be using. This seems to be the easiest rectangle structure to use.

After working through the problem, I came up with an intersection routine that looked similar to this:

And after taking another approach, I came up with this routine that determines if two objects are NOT intersecting.

One thing I immediately noticed was that the code was practically the same. So which one is better? Which one should you use? Why are they so similar?

Well if you remember “DeMorgan’s Law” and the rest of boolean logic laws, it’s possible to turn the Intersecting routine into the NonIntersecting routine and vise versa. It’s easier to see it when applied. Note the expression below:

This expression can be turned into the “non-intersecting” expression by a simple matter of applying a “not” operator ( ! ) to it, such as this:

Some people like to optimize this away by applying boolean algebraic laws to the expression resulting in this:

The question now is, should we use the intersection routine or the non-intersection routine? I believe it really comes down to probability in the application. Are the objects more likely to be intersecting or not intersecting? For example, lets say that objects spend a majority of their time NOT intersecting. It would be “cheaper” to use the “non-intersecting” routine. If on the other hand, we expect the objects to be consistently in contact, such as a particle simulation or fluid simulation that uses particles, it might be cheaper to use the “intersecting” routine. Why?

If we assume objects are not colliding very often, and (looking at the expression below) r1 is to the left of r2, then the non-intersection routine only has to check the first part of the expression to determine a failure condition.

Once this condition has failed, then the rest of the expression doesn’t have to be evaluated. (the other 3 lines). Lets assume that our player is a guy running around on the ground and a bunch of enemies are flying in the air and swoop down to hit the player. Lets say we have 100’s of these enemies in the air. One particular optimization in this case would be to rearrange the non-intersection expression like such:

This way, the y positions are tested first since most of the flying bad guys are probably going to be higher the player and thus not intersecting him. This way, only the first couple expressions in the larger expression usually have to be tested to determine a “false” condition.

Let us consider the opposite scenario. If the objects are constantly in contact, the “Intersecting” routine might be a better choice for the same kind of reasons. If two objects are constantly in contact, the “Intersecting” routine will drop out sooner rather than later.

If you look at the very first expression, we see that the expression immediately will drop out if they aren’t intersecting. In this case, if we look at the very first line, it is basically saying if the right edge of r1 is to the left of r2’s left edge, then drop out of the entire large expression. There is no need to check the other expressions because it has already failed. Again, the same sort of optimization can be applied by reorganizing the expressions around if you know something about the simulation you are dealing with, like the flying bad guys.

So as you can see, boolean algebra suggests that the two routines are equivalent, but this “case study” suggests that boolean algebra can be applied to optimize a routine for the scenario upon which it is to be applied. I believe the real issue lies in actually noticing when to apply the logic.


Leave a Reply

You must be logged in to post a comment.