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 even mentioned. As a bonus, this version of the procedure also gives consistent and sensible answers when two or three of the points are coincident: all such point sets are considered collinear.

Unfortunately, there is a heavy price to be paid for this simplicity. Up to this point, all computations have been done with exact arithmetic. If the original coordinates are specified by means of integers or rational numbers, then the slopes and intercepts are calculated without round-off or other error. For example, the line passing through (1 1) and (4 2) has slope m=1/3 and y-intercept b=2/3 (not decimal approximations such as 0.33 and 0.67). With numbers represented in this way, comparisons are guaranteed to give the mathematically correct answer. But exactness is unattainable in measuring distances. The procedure distance invoked by triangle-collinear is defined like this:

	(defun distance (px py qx qy)
	  (sqrt (+ (square (- qx px))
	           (square (- qy py)))))

The square root is the culprit, of course. If sqrt returns an irrational result, there's no hope of finding an exact, finite, numeric representation. When distances are calculated with double-precision IEEE floating-point arithmetic, triangle-collinear gives trustworthy answers for points whose coordinates are no larger than about 10⁵. Go much beyond that threshold, and the procedure inevitably starts to mistake very skinny triangles for degenerate ones, incorrectly reporting that the vertices are collinear.

There is no quick and easy fix for this failing. Tricks like rotating or scaling the coordinate frame will not help. It's just a bug (or feature?) of our universe: rational points can give rise to irrational distances. Getting exact and reliable results under these circumstances is not quite impossible, but it takes an industrial-strength effort. Where the three points really are collinear, this fact can be proved algebraically without evaluating the square roots. For example, given the collinear points (0 0), (3 3), and (5 5), the distance equation is sqrt(50) = sqrt(18) + sqrt(8), which reduces to 5 xsqrt(2) = 3 xsqrt(2) + 2 xsqrt(2). When the points are not collinear, numerical evaluation will eventually reveal an inequality, if you calculate enough digits of the roots. But I don't relish the idea of implementing a symbolic algebra system and an adaptive multiprecision arithmetic module just to test trios of points for collinearity. There's gotta be an easier way. In the Book version of the algorithm, I expect greater economy of means.