Beautiful Code [349]
(defun y-intercept (px py qx qy)
(let ((m (slope px py qx qy)))
(if (not m)
nil
(- py (* m px)))))
Now, I also had to re-rig the calling procedure to handle the possibility that the slope m is not a number but a bogus value:
(defun less-naive-collinearp (px py qx qy rx ry)
(let ((m (slope px py qx qy))
(b (y-intercept px py qx qy)))
(if (numberp m)
(= ry (+ (* m rx) b))
(= px rx))))
If m is numeric—if the predicate (numberp m) returns t—then I proceed as before. Otherwise, I know that p and q share the same x-coordinate. It follows that the three points are collinear if r also has this same x value.
As the program evolved, the need to make special provisions for vertical lines was a continual irritation. It began to look like every procedure I wrote would have some ugly patch bolted on to deal with the possibility that a line is parallel to the y-axis. Admittedly, the patch was just an if expression, an extra line or two of code, not a major issue of software engineering. Conceptually, though, it seemed a needless complication, and perhaps a sign that I was doing something wrong or making life harder than it had to be. Vertical lines are not fundamentally any different from horizontal ones, or from lines that wander across the plane at any other angle. It's an arbitrary convention to measure slope with respect to the y-axis; the universe would look no different if we all adopted a different reference direction.
This observation suggests a way around the problem: rotate the whole coordinate frame. If a set of points are collinear in one frame, they must be collinear in all other frames as well. Tilt the axes by a few degrees one way or the other, and the divide-by-zero impasse disappears. The rotation is not difficult or computationally expensive; it's just a matrix multiplication. On the other hand, taking this approach means I still have to write that if expression somewhere, testing to see whether px is equal to qx. What I'd really prefer is to streamline the logic and get rid of the branch point altogether. Shouldn't it be possible to test for collinearity by means of some simple calculation on the coordinates of the points, without any kind of case analysis?
Here's a solution recommended (in a slightly different context) by one web site, which I shall allow to remain anonymous: when Δx is 0, just set Δy/Δx to 1010, a value "close enough to infinity." As a practical matter, I suspect that this policy might actually work quite well, most of the time. After all, if the input to the program derives in any way from measurements made in the real world, there will be errors far larger than 1 part in 1010. All the same, this is a strategy I did not consider seriously. I may not know what the Book version of collinear looks like, but I refuse to believe it has a constant defined as "close enough to infinity."
Writing Programs for "The Book" > The Slippery Slope
33.4. The Slippery Slope
Instead of drawing a line through two points and seeing whether the third point is on the line, suppose I drew all three lines and checked to see whether they are really the same line. Actually, I would need to draw only two of the lines, because if line is identical to line , it must also be equal to . Furthermore, it turns out I need to compare only the slopes, not the y-intercepts. (Do you see why?) Judging by eye whether two lines are really coincident or form a narrow scissors angle might not be the most reliable procedure, but in the computational world, it comes down to a simple comparison of two numbers, the m values (see Figure 33-3).
Figure 33-3. Testing collinearity by comparing slopes
I wrote a new version of collinear as follows:
(defun mm-collinear (px py qx qy rx ry)
(equalp (slope px py qx qy)
(slope qx qy rx ry)))
What an improvement! This looks much simpler. There's no if expression calling attention to the distinguished status of vertical lines; all sets of points are treated the same way.
I must confess, however,