Beautiful Code [353]
Figure 33-5. Testing collinearity by measuring area
How to measure the area? The Euclidean formula 1/2bh is not the best answer, and neither is the trigonometric approach. A far better plan is to regard the sides of a triangle as vectors; the two vectors emanating from any one vertex define a parallelogram, whose area is given by the cross product of the vectors. The area of the triangle is just one-half of the area of the parallelogram. Actually, this computation gives the "signed area": the result is positive if the vertices of the triangle are taken in counterclockwise order, and negative if taken in clockwise order. What's most important for present purposes, the signed area is zero if and only if the vertices are collinear.
The vector formula for the area is expressed most succinctly in terms of the determinant of a two-by-two matrix:
Because I'm interested only in the case where the determinant is zero, I can ignore the factor of 1/2 and code the collinearity predicate in this simple form:
(defun area-collinear (px py qx qy rx ry)
(= (* (- px rx) (- qy ry))
(* (- qx rx) (- py ry))))
So, here it is: a simple arithmetical function of the x-and y-coordinates, requiring four subtractions, two multiplications, and an equality predicate, but nothing else—no ifs, no slopes, no intercepts, no square roots, no hazard of divide-by-zero errors. If executed with exact rational arithmetic, the procedure always produces exact and correct results. Characterizing the behavior with floating-point arithmetic is more difficult, but it is far superior to the version based on comparing distances on the perimeter. Shewchuk provides highly tuned C code that uses floating-point when possible and switches to exact arithmetic when necessary.
Writing Programs for "The Book" > Conclusion
33.8. Conclusion
My adventures and misadventures searching for the ideal collinearity predicate do not make a story with a tidy moral. In the end, I believe I stumbled upon the correct solution to my specific problem, but the larger question of how best to find such solutions in general remains unsettled.
One lesson that might be drawn from my experience is to seek help without delay: some-body out there knows more than you do. You may as well take advantage of the cumulative wisdom of your peers and predecessors. In other words, Google can probably find the algorithm you want, or even the source code, so why waste time reinventing it?
I have mixed feelings about this advice. When an engineer is designing a bridge, I expect her to have a thorough knowledge of how others in the profession have solved similar problems in the past. Yet expertise is not merely skill in finding and applying other people's bright ideas; I want my bridge designer to have solved a few problems on her own as well.
Another issue is how long to keep an ailing program on life support. In this chapter, I have been discussing the tiniest of programs, so it cost very little to rip it up and start over whenever I encountered the slightest unpleasantness. For larger projects, the decision to throw one away is never so easy. And doing so is not necessarily prudent: you are trading known problems for unknown ones.
Finally, there is the question of just how much the quest for "beautiful code" should be allowed to influence the process of programming or software development. The mathematician G. H. Hardy proclaimed, "There is no permanent place in the world for ugly mathematics." Do aesthetic principles carry that much weight in computer science as well? Here's another way of asking the same question: do we have any guarantee that a Book-quality