Circles are Confusion


Picture of the devil with the words High School Math overtop of him

Did you learn about domains in high school? A domain of a function is "what it is defined over"; i.e., a function f(x) may be defined for x between 0 and 1, but not outside that. Or for instance f(x) = 1/x is defined over (-inf...0) and (0...+inf) but not actually AT 0.

A range of a function on the other hand is what it might output, for instance f(x) = x * 2 defined only over 0..1 can only return values in the range 0..2, so it's range is 0..2.

Circle Groups

Think about the function sin(theta). You could define this over all real numbers, but because the function repeats itself you could also define it over [0..2pi).

Note: this is actually cos(theta), sorry!

If we think about this domain, we might realize that is most intuitive to think of it as a circle. In this case, sin(theta) would be the y coordinate of a point on this circle, and cos(theta) would be the x.

So now, let's think about the unit circle itself as a domain. Assuming the radius of the circle is r, and the point (1, 0) on this point is 0, then going counter clockwise we can trace out the distance from the starting point as theta, which will go from [0..2pi]. Once we reach 2pi, we are back at the start.

This is one (not very rigorous) way to define a particular group. A group is just a set of things (such as our domain above, a set of points) together with an operator, op(a, b) which has a domain and a range of the set of things. In our example, op(a, b) takes an angle a (in 0..2pi) and rotates it by b (also in 0..2pi) radians; it "adds" the two numbers, modulo (wrapping at) 2pi.

Collision

Suppose two bobsleds are travelling along the line -inf...inf, in the real numbers. Let's call bobsled A's position (in 1 dimension) A1, and bobsled B's position as B1; further, let's suppose that a moment ago bobsled A was at position A0, and bobsled B was at position B0. That is, in some small timeslice, bobsled A moved from A0 to A1, and B moved from B0 to B1.

Our task is to determine whether, during that recent timeslice, they would have run into each other. In fact, this is fairly simple to check: Suppose that they AREN'T colliding. Then either max(A0,A1) must be less than min(B0,B1), or min(A0,A1) must be greater than max(B0,B1). Otherwise, they are overlapping and so colliding. This is essentially a bounding box check in 1-D.

Collisions on the Circle Group

It is (to me) much less obvious how to detect this collision on the circle group. That is, suppose that our bobsleds are not moving along an infinite line, but on a circle. Their coordinates are still 1-D: each bobsled has only an A0 and A1, somewhere in between 0..2pi; they are not allowed a traditional 2-D "vector" representation.

The first complication is that it's not obvious, given only A0 and A1, which direction a bobsled is moving. In fact, it could be moving in either direction, as shown here:

But let's suppose, for a moment, that we can overcome this problem of direction. One "sensible" thing to do might be to check which of the two possible curve segments would be shorter; and indeed if T is small enough this will always work.

Even then, we are still left with the problem that the above inequality makes no sense. For instance, the number pi is greater than pi/2 on the real number line, but not on the unit circle. To see why this is so, think about starting at pi, and adding pi*3/2 to it, we will arrive at pi/2. I.e., we can start at either point, rotate counterclockwise, and end up at the other point. So there is no way to define which is smaller, at least not in a way that is consistent with our circle group.

Because you can add something to pi/2 to reach pi, and also add something to pi to reach pi/2, you can't define one as being greater than the other.

Naieve Approach

We might try and adapt our approach for the real number line by "unwrapping" the circle into a line segment. In some cases this will work without a problem. But what if our "unwrapping point" (i.e., where we take our scissors and cut the unit circle) cuts through one of the ranges in question, as well?

In this case we will have to do some additional checks. In practice, this will create ugly code with several conditionals. If this is the only solution we can immediately see, we might decide we don't have the energy to actually code it, and decide to write a blog post instead.

Now imagine TWO such line segments, possibly chopped in half, possibly overlapping, in all possible configurations. It's feasable to code that but not if you are lazy.

ACOS

A better solution would be to think about this problem natively; that is, try and work within a domain that is natural to it. This would mean treating theta as an angle. In fact, what we could do is find the midpoint of each angle A0->A1, B0->B1, and how far out they "sweep", and then check to see if there is overlap.

This might at first seem to be trivially similar to the collision solution on the real number line; it is not. The reason is that the collision solution above checks bounds, whereas here we are checking distances. One is the equivalent of an N-dimensional bounding box problem where N=1; this is rather the equivalent of checking whether two N-spheres collide.

In the first case, we are doing an ordering comparison. Is this greater than or less than that. But in the second case, we are computing distance between two points, which is not dependant on something being ordered. Realize that absolute value is the distance function on 1-D, just like sign(x) is the "normal vector" of x in 1-D.

There is one remaining detail, which is to compute the distance between two points on the unit circle. In general, we could say they have two different distances, depending on which way you go (A to B will be a different length than B to A.) In our case though it is pretty obvious that we want to the smaller of the two distances, because if the larger one collides then the smaller one will as well.

Native Representation?

Because our CPU does not have a native representation for these kind of values (it might be interesting to think what a native representation of this would look like, in binary!) we will at some point have to convert back to the real number line. However, it's a lot simpler task to convert just the resulting midpoints to the real number line than it would be to convert the entire ranges, as in our first "naieve" approach.

Circles Are Confusion

Hopefully this blog was interesting to read. If you are looking for a better understanding of some of the mathematics here, I would recommend reading about Group Theory. (wikipedia)

Read about Group Theory on Wikipedia.

TWEETER

Finally please let me share a funny twitter exchange (I have ordered it chronologically). Bask in my multi-layered puns:

Srsly, I'm on fire tonite!

2011-04-16


◀ Back