2009年2月26日星期四

判断三点共线问题的最佳程序

此问题与解答源于《Beautiful Code》,这里只是精炼地表达书上的解答。

问题:如何判断平面上三个点(x1,y1),(x2,y2),(x3,y3)是否在一条直线上。
思路:
这个问题的难度不在于如何解决它,而在于如何“完美”地解决它。“完美”,可以理解为代码必须正确,美观,简洁,高效而且不容易受到计算误差的影响。

判断三点共线的方法有很多。如果采用与斜率有关的方法(比如使用直线的截斜式),那么必然要对斜率无穷大或者说没有斜率的情况做特殊处理。也可以考虑计算第三点到另外两点所确立的直线的距离,如果用这种方法,那么会涉及到求直线方程Ax+By+C=0和开平方,这样做运算效率较底。

最终的解决方案是求三点所确立的三角形的面积,三点共线当且仅当三角形的面积为0。而计算面积最简单高效的方法是使用矢量法,即三角形面积的行列式公式,面积等于
| x1-x3 y1-y3|
| x2-x3 y2-y3| / 2

[ (x1-x3)*(y2-y3) -(X2-X3)*(y1-y3)] / 2
利用这个公式可以保证在无论三点是否互不相同都可以判断共线。

Lisp代码:
(defun area-collinear (x1 y1 x2 y2 x3 y3)
(= (* (- x1 x3) (- y2 y3))
(* (- x2 x3) (- y1 y3))))

没有评论: