共线性

我最近听格雷格·威尔逊讲了一个他很珍视的话题，漂亮的代码．他和安迪·奥兰(Andy Oran)就这个话题编辑了一本书，在书中程序员解释了他们的思维过程。这篇文章为“The Book”编写程序这本书确实引起了我的共鸣，部分原因是他讨论的实际问题，部分原因是他描述的顿悟时刻。Brian用Lisp语言编写代码。我将在MATLAB中编写类似的代码来说明这一点。

内容

问题描述

给定平面上的3个点，求出它们是否在一条直线上，也就是说，求出它们是否共线。这是我们用来测试算法的第一组点。

P1 = [1 1];P2 = [3.5 3.5];P3 = [-7.2 -7.2];

方法1 -看第三点是否服从相同的斜率

在这个变体中，我们计算连接2对点的直线，然后检查第三个点是否符合同一条直线。

collinear1 (p1, p2, p3)

Ans = 1

dbtypecollinear1

1函数tf = collinear1(p1,p2,p3) 2m =斜率(p1,p2);3b =截距(p1,p2);4 tf = (m*p3(1)+b) == p3(2);m = 5时6函数斜率(p1, p2) 7 m = (p2 (2) p1 (2)) / (p2 (1) p1 (1));8结束9函数b =截距(p1,p2) 10 m =斜率(p1,p2);11 b = -p1(2)+m*p1(1);12结束

方法2 -方法1修改

方法一在点共线且在垂直线上的情况下有一个缺陷，即有重复x值。那么我们计算的分母就是2的差值x相同的值，结果是除0和一个非有限的斜率。首先，让我们看看第一个算法和垂直对齐的点会发生什么。

Q1 = [0 1];Q2 = [0 3.5];Q3 = [0 -7.2];collinear1 (q1、q2、q3)

Ans = 0

第一个算法说这些点不是共线的。是时候修补算法了。

collinear2 (q1、q2、q3)

Ans = 1

dbtypecollinear2

1函数tf = collinear2(p1,p2,p3) 2m =斜率(p1,p2);3b =截距(p1,p2);如果m是有限的，则5%的点都在y轴上。6 if ~isfinite(m) 7 if (p3(1)==p1(1)) 8 tf = true;9 else 10 tf = false;11 end 12 else 13 tf = (m*p3(1)+b) == p3(2);16函数m =斜率(p1,p2) 17 m = (p2(2)-p1(2))/(p2(1)-p1(1));19函数b =截距(p1,p2) 20 m =斜率(p1,p2);21 b = -p1(2)+m*p1(1);22日结束

方法3和方法4 -仅比较两个斜率

布莱恩注意到的下一件事是，他真的不需要看第三个点是否符合同一条线。他真正需要确定的是两条直线的斜率是否相同。如果是这样的话，三条直线的斜率都是一样的(说服自己这是真的，至少对于欧几里得几何是这样)。

让我们在两组共线点上试试这个算法。

collinear3 (p1, p2, p3) collinear3 (q1、q2、q3)

Ans = 1 Ans = 0

dbtypecollinear3

1函数tf = collinear3(p1,p2,p3) 2 m1 =斜率(p1,p2);3 m2 =斜率(p1,p3);4 tf = isequal(m1,m2);5 end 6 function m = slope(p1,p2) 7 q = p2-p1;8 m = q(2)/q(1);9日结束

我们需要再次修改无限斜率的代码。

collinear4 (q1、q2、q3)

Ans = 1

dbtypecollinear4

1函数tf = collinear3(p1,p2,p3) 2 m1 =斜率(p1,p2);3 m2 =斜率(p1,p3);5 if isfinite(m1) = isequal(m1,m2);6 if ~isfinite(m2) 8 tf = true;9 else 10 tf = false;11端12端13端14函数m =斜率(p1,p2) 15 q = p2-p1;16 m = q(2)/q(1);17日结束

方法5和6 -三角形边长之和

Brian探索的下一个想法是利用3点定义的三角形边之间的关系。最长的一条腿比其他两条边的长度之和短，但当两点共线时除外。那么最长边的长度等于其他两条边的长度之和。让我们试一下。

collinear5 (p1, p2, p3) collinear5 (q1、q2、q3)

Ans = 0 Ans = 1

我们用Brian用过的点值。

Bh1 = [0 1];Bh2 = [14 5];Bh3 = [8 4];collinear5 (bh1 bh2 bh3);

dbtypecollinear5

1函数tf =共线性5(p1,p2,p3) 2边(3)=范数(p2-p1);3边(2)=范数(p3-p1);4边(1)=范数(p3-p2);5个长度= sort(side，' descent ');6 tf = isequal(长度(1)，…7(长度(2)+(3)长度));8日结束

到目前为止，一切顺利。不共线的点不会被认为是共线的。第一组是，结果是负的。让我们再试一组点来确定一下。

Bh4 = [0 0];Bh5 = [3 3];Bh6 = [5 5];collinear5 (bh1 bh2 bh3) collinear5 (bh1 * 1 e5, bh2 * 1 e5, bh3 * 1 e5)

Ans = 0 Ans = 0

啊哦!发生了什么事?回首往事collinear5，我们看到我们不再只是做加法、减法、乘法和除法。现在我们在计算规范这涉及到计算√6．因此，我们有更多的机会出现数值舍入问题，即使这些点被限制为有理数(包括整数)。

collinear6 (bh1 bh2 bh3) collinear6 (bh1 * 1 e5, bh2 * 1 e5, bh3 * 1 e5)

Ans = 0 Ans = 0

版本collinear6不再做精确的相等比较，而是寻找顺序上的差异每股收益对于合适的长度。

dbtypecollinear6

1函数tf = collinear6(p1,p2,p3) 2边(3)=范数(p2-p1);3边(2)=范数(p3-p1);4边(1)=范数(p3-p2);5个长度= sort(side，' descent ');6 tf =…7 abs(长度(1)-(长度(2)+长度(3)))…8 <= eps(长度(1));9日结束

方法7 -尤里卡，计算三角形面积!

最后，正如布莱恩所描述的，他意识到有一种完全不同的方法来判断三个点是否共线，那就是计算区域它们定义的三角形。

collinear7 (bh1 bh2 bh3) collinear7 (bh1 * 1 e5, bh2 * 1 e5, bh3 * 1 e5)

Ans = 0 Ans = 0

要计算面积，你可以计算底*高/ 2，但这也会涉及到平方根。三角方法会涉及到超越函数。另一种思考方法是将任意2对点看作一个平行四边形，三角形的面积是这个面积的一半。为了计算面积，把两边看成平移到原点的向量。那么面积的计算就很简单了，归结为与行列式如果结果为0，则这些点共线。

dbtypecollinear7

1函数tf = collinear7(p1,p2,p3) 2 mat = [p1(1)-p3(1) p1(2)-p3(2);．.．3 p2(1)-p3(1) p2(2)-p3(2)];4 tf = det(mat) == 0;

该算法需要进行6次算术运算后进行相等性检验。很简单,非常优雅，比其他算法更不容易出现数值问题。比上面所有其他代码都要好得多，不需要考虑单一行为。

注:2008年6月9日新增

如果您阅读了本博客的评论，您将发现一个依赖svd的更令人满意的解决方案。圣言会(及相关的排名函数)具有更好的数值属性依据．

你最近的顿悟时刻是什么?

你最近有过类似的顿悟吗?我们很想听听在这里．

获取MATLAB代码

使用MATLAB®7.6发布