Beautiful Code [350]
(defun typed-mm-collinear (px py qx qy rx ry)
(let ((pq-slope (slope px py qx qy))
(qr-slope (slope qx qy rx ry)))
(or (and (numberp pq-slope)
(numberp qr-slope)
(= pq-slope qr-slope))
(and (not pq-slope)
(not qr-slope)))))
This is not nearly as pretty, although even in this more-explicit form, the logic seems to me less tortured than the "naïve" version. The reasoning is that and are the same line if the slopes are both numbers and those numbers are equal, or if both slopes are nil. And, anyway, should one penalize a clever Lisp program just because other languages can't do the same trick?
I would have been willing to call it quits at this point and accept mm-collinear as the final version of the program, but for another anomaly that turned up in testing. Both mm-collinear and less-naive-collinear could successfully discriminate between collinear points and near misses; a case like p=(0 0), q=(1 0), r=(1000000 1) was not a challenge. But both procedures failed on this set of points: p=(0 0), q=(0 0), r=(1 1).
A first question is what should happen in this instance. The program is supposed to be testing the collinearity of three points, but here p and q are actually the same point. My own view is that such points are indeed collinear because a single line can be drawn through all of them. I suppose the opposite position is also defensible, on the grounds that a line of any slope could be drawn through two coincident points. Unfortunately, the two procedures, as written, do not conform to either of these rules. They return nil for the example given above but t for the points p=(0 0), q=(0 0), and r=(0 1). Surely this is pathological behavior by anyone's standards.
I could solve this problem by edict, declaring that the three arguments to the procedure must be distinct points. But then I'd have to write code to catch violations of the rule, raise exceptions, return error values, scold criminals, etc. It's not worth the bother.
Writing Programs for "The Book" > The Triangle Inequality
33.5. The Triangle Inequality
Here's yet another way of rethinking the problem. Observe that if p, q, and r are not collinear, they define a triangle (Figure 33-4). It's a property of any triangle that the longest side is shorter than the sum of the smaller sides. If the three points are collinear, however, the triangle collapses on itself, and the longest "side" is exactly equal to the sum of the smaller "sides."
Figure 33-4. Testing collinearity by the triangle inequality
(For the example shown in this figure, the long side is shorter than the sum of the other two sides by about 0.067.)
The code for this version of the function is not quite so compact as the others, but what's going on inside is simple enough:
(defun triangle-collinear (px py qx qy rx ry)
(let ((pq (distance px py qx qy))
(pr (distance px py rx ry))
(qr (distance qx qy rx ry)))
(let ((sidelist (sort (list pq pr qr) #'>)))
(= (first sidelist)
(+ (second sidelist) (third sidelist))))))
The idea is to calculate the three side lengths, put them in a list, sort them in descending order of magnitude, and then compare the first (longest) side with the sum of the other two. If and only if these lengths are equal are the points collinear. This approach has a lot to recommend it. The calculation depends only on the geometric relations among the points themselves; it's independent of their position and orientation on the plane. Slopes and intercepts are not