检查三个点是否在同一条直线上

Question

我希望知道一段能够判断在二维空间中三个点是否在同一条直线上的代码。提供伪代码也可以，但是Python更好。

- Hossein

---

你的线是如何定义的？在二维平面上的函数吗？ - Daenyth

你具体得到了什么？三个点？还是三个点和一条线？ - John Smith

Answer 1

你可以检查ABC三角形的面积是否为0：

[ Ax * (By - Cy) + Bx * (Cy - Ay) + Cx * (Ay - By) ] / 2

当然，实际上你并不需要除以2。

- florin

---

这样更好，因为没有除以0的风险。 - John Smith

只是指出一件事情...从数学上讲，如果忽略掉除以2的部分，这与@dcp在上面给出的答案等价，但检查面积是否为0使得添加容差更容易...(即使用stuff < err_tolerance而不是像@dcp在上面所做的那样使用stuff1 == stuff2). - Joe Kington

+1 在数学上是相同的，但概念更简单、直观、易于理解（我喜欢它）。 - joaquin

@Hossein：你是在问绝对值还是符号？根据你的点和我的公式，我得到了-510。符号意味着你选择了某些点的顺序。你可以交换A和C或B，这样你会得到一个正面积，即使它是同一个三角形。 - florin

@Joe Kington：（1）你需要做-tolerance < stuff < tolerance。（2）@florin的公式需要3次乘法和5次加减法才能得出“应该为零”的结果。@dcp的公式通过将“==”更改为“-”，需要2次乘法和5次减法才能得出“应该为零”的结果。我会选择@dcp而不是@florin。 - John Machin

Answer 2

这是C++的代码，但你可以将它适应为Python：

bool collinear(int x1, int y1, int x2, int y2, int x3, int y3) {
  return (y1 - y2) * (x1 - x3) == (y1 - y3) * (x1 - x2);
}

基本上，我们正在检查点1和点2以及点1和点3之间的斜率是否匹配。斜率是y的变化量除以x的变化量，因此我们有：

y1 - y2     y1 - y3
-------  =  --------
x1 - x2     x1 - x3

对等式进行叉乘得到 (y1 - y2) * (x1 - x3) == (y1 - y3) * (x1 - x2)；

注意，如果你使用的是双精度浮点数，可以和一个 epsilon 做比较：

bool collinear(double x1, double y1, double x2, double y2, double x3, double y3) {
  return fabs((y1 - y2) * (x1 - x3) - (y1 - y3) * (x1 - x2)) <= 1e-9;
}

- dcp

---

不错的技巧。然而，检查浮点数是否相等并不安全。您可以测试绝对差异与预定义阈值之间的关系，该阈值取决于您想要实现的分辨率（灵敏度）。 - Boris Gorelik

一个斜率不能是正的而另一个是负的吗？我认为你应该比较它们的绝对值。 - Johannes Charra

@dtb - x1==x2可以正常工作，考虑这些情况：collinear(-2,0,-2,1,-1,1)返回false，而collinear(-2,0,-2,1,-2,2)返回true。我认为角落的情况已经覆盖了，如果您不同意，请告诉我。 - dcp

这个方案的计算量比@florin的答案少，即使它们是等价的（所以我投票支持它）。 - martineau

@georg - 实际上，它比较的是乘积之间的绝对差异，并确保该差异<= 1e-9。因此，产品本身接近或远离1都不重要。同样，我们只关心产品的绝对差异是否小于等于1e-9，这意味着我们可以假设产品相等，因此斜率匹配。希望有所帮助。 - dcp

Answer 3

y - y0 = a(x-x0)（1），其中 a = (y1 - y0)/(x1 - x0)，且 A(x0, y0)、B(x1, y1)、C(x2, y2)。查看 C 是否满足（1）。只需替换相应的值即可。

详情

- Dimitris Leventeas

Answer 4

阅读this，并使用它来找到通过前两个点的直线方程。按照说明找到m和b。然后对于您的第三个点，计算mx + b - y。如果结果为零，则第三个点与前两个点在同一条直线上。

- Douglas

Answer 5

规则1: 在任何线性二维空间中，两个点总是在同一条直线上。

取两个点并建立一个代表它们之间的直线方程。然后检查第三个点是否也在该直线上。

祝你好运。

- Rob Vermeulen