Safe Computations

My last blog about Convex Hulls involved an interesting topic; the safety of using math in a computer. The Jarvis March algorithm involves calculating the polar angle of each point from a reference point. Radians would be perfect except that it is computationally expensive to calculate the radian angle. (It involves inverse trig functions). However, as several of the convex hull articles point out, you don't actually need the angle; the tangent of the angle will do. This is true because as the angle increases so does the tangent. Or rather, if a > b then tan a > tan b. (So long as you stay within a quadrant). Since the only thing the Jarvis March does with an angle is to compare it to other angles, the tangent will do. This is good news because tangents are very easy to calculate: dy/dx.

The problem with tangents is that they range from -infinity to +infinity. You can detect the infinite case easily enough (dx == 0) but you still have to deal with numbers that can get very large. In a Convex Hull algorithm the chances that dx between two points will be small enough to explode the result is not insignificant. Besides, checking for the infinity case is a pain.

The argument could be made that the tangent (slope) is safe for this particular algorithm since the tangent can't really get any larger than dx can be small, so there can't really be any loss of precision. But I don't like it anyway. Dealing with functions that can roar off to infinity is inherently risky. So I decided to see if there might be a better solution.

I came up with the idea of mapping the angle to the perimeter of a square whose vertices were on the axes.

        |   *p
        *  /
      * | @
    *   |/  *
--*-----O-----*----
    *   |   *
      * | *
        *
        |

In the diagram above, the angle of the line OP from vertical is related to the permeter of the square from the topmost point of the square to the intersection (@) of OP with the square. How can we calculate this perimeter?

If we restrict our math to the first quadrant, then a little math shows that the square of the perimeter, D^2 = 2/(m+1)^2 where m is the slope of OP. What we want to do is get rid of m since it can roar off to infinity if OP gets close to vertical.

So: D^2 = 2/((m+1)^2)
    D   = sqrt(2)/(m+1)
        = sqrt(2)/(1+(dy/dx))
        = sqrt(2)/((dy+dx)/dx)
        = sqrt(2)*dx/(dy+dx)

Now since all we are after is a function that increases as the angle increases, the sqrt(2) is meaningless. So dx/(dy+dx) is good enough. Better yet this function has a range of [0,1] which keeps the floating point exponent very close to zero. The check for dx==0 is no longer necessary since the function yeilds zero if dx is zero and 1 if dy is zero, and is only undefined if the two points are coincident (which we can check for in a different way).

This is nice. The function is fast and well behaved. No infinities to worry about.

But was it really necessary, or should I have have just used m?

!commentForm -r