Beautiful Code [352]
For the ease of exposition, we shall assume that no two endpoints have the same x-or y-coordinates. This, in particular, applies to the two endpoints of the same segment, and thus rules out the presence of vertical or horizontal segments…Our rationale is that the key ideas of the algorithm are best explained without having to worry about special cases every step of the way. Relaxing the assumptions is very easy (no new ideas are required) but tedious. That's for the theory. Implementing the algorithm so that the program works in all cases, however, is a daunting task. There are also numerical problems that alone would justify writing another paper. Following a venerable tradition, however, we shall try not to worry too much about it.
Perhaps the most important lesson learned from this foray into the literature was that others have also found meaty challenges in this field. It's not just that I'm a code wimp. This was a reassuring discovery; on the other hand, it did nothing to actually solve my problem.
Later, I wrote an item about line-segment intersection algorithms on my weblog at http://bit-player.org. This was essentially a plea for help, and help soon came pouring in—more than I could absorb at the time. One reader suggested polar coordinates as a remedy for undefined slopes, and another advocated rewriting the linear equations in parametric form, so that x-and y-coordinates are given as functions of a new variable t. Barry Cipra proposed a somewhat different parametric scheme, and then came up with yet another algorithm, based on the idea of applying an affine transformation to shift one of the segments onto the interval (–1 0),(1 0). David Eppstein advocated removing the problem from Euclidean geometry and solving it on the projective plane, where the presence of "a point at infinity" helps in dealing with singularities. Finally, Jonathan Richard Shewchuk gave me a pointer to his lecture notes, papers, and working code; I'll return to Shewchuk's ideas below.
I was impressed—and slightly abashed—by this flood of thoughtful and creative suggestions. There were several viable candidates for a segment-intersection procedure. Furthermore, I also found an answer to the collinearity problem. Indeed, I believe the solution that was handed to me may well be the Book algorithm.
Writing Programs for "The Book" > "Duh!"—I Mean "Aha!"
33.7. "Duh!"—I Mean "Aha!"
In cartoons, the moment of discovery is depicted as a light bulb turning on in a thought balloon. In my experience, that sudden flash of understanding feels more like being thumped in the back of the head with a two-by-four. When you wake up afterwards, you've learned something, but by then your new insight is so blindingly obvious that you can't quite believe you didn't know it all along. After a few days more, you begin to suspect that maybe you did know it; you must have known it; you just needed reminding. And when you pass the discovery along to the next person, you'll begin, "As everyone knows…."
That was my reaction on reading Jonathan Shewchuk's "Lecture Notes on Geometric Robustness." He gives a collinearity algorithm that, once I understood it, seemed so natural and sensible that I'm sure it must have been latent within me somewhere. The key idea is to work with the area of a triangle rather than the perimeter, as in triangle-collinear. Clearly, the area of a triangle is zero if and only if the triangle is a degenerate one, with collinear vertices. But measuring a function of the area rather a function of the perimeter has two big advantages. First, it can be done without square roots or other operations that would take us outside the field of rational numbers. Second, it is much less dependent on numerical precision.
Consider a family of isosceles triangles with vertices (0 0), (x 1), and (2x 0). As x increases, the difference between the length of the base