判断三点共线的10种常见算法
1. 向量叉积法（最常用）
def is_colinear_cross(pt1, pt2, pt3, tol=1e-8):
# 原理：三点共线 ⇔ 向量 AB 与 AC 共线 ⇔ 向量叉积为0
x1, y1 = pt1
x2, y2 = pt2
x3, y3 = pt3
return abs((x2-x1)*(y3-y1) - (y2-y1)*(x3-x1)) < tol
解释：三点A(x1, y1)、B(x2, y2)、C(x3, y3)共线时，向量AB与AC平行，向量叉积为0。
2. 面积法（海伦公式）
def is_colinear_area(pt1, pt2, pt3, tol=1e-8):
# 原理：三角形面积为0说明三点共线
x1, y1 = pt1
x2, y2 = pt2
x3, y3 = pt3
area = 0.5 * abs((x1*(y2-y3) + x2*(y3-y1) + x3*(y1-y2)))
return area < tol
解释：三角形面积为零时三点共线。公式来源于平面三点组成的三角形面积公式。
3. 斜率法
def is_colinear_slope(pt1, pt2, pt3, tol=1e-8):
# 原理：三点的斜率相等说明共线
x1, y1 = pt1
x2, y2 = pt2
x3, y3 = pt3
dx1, dy1 = x2 - x1, y2 - y1
dx2, dy2 = x3 - x2, y3 - y2
if abs(dx1) < tol and abs(dx2) < tol:
return True # 都是竖线
if abs(dx1) < tol or abs(dx2) < tol:
return False
return abs(dy1/dx1 - dy2/dx2) < tol
解释：三点共线时，AB与BC的斜率必然相等。注意处理竖线（dx=0）时的特殊情况。
4. 向量线性相关法
def is_colinear_vector(pt1, pt2, pt3, tol=1e-8):
# 原理：AB=k*AC即线性相关
x1, y1 = pt1
x2, y2 = pt2
x3, y3 = pt3
dx1, dy1 = x2 - x1, y2 - y1
dx2, dy2 = x3 - x1, y3 - y1
if abs(dx1) < tol and abs(dx2) < tol:
return True
if abs(dx2) < tol:
return False
k = dx1 / dx2
return abs(dy1 - k * dy2) < tol
解释：三点共线时，向量AB是AC的某个倍数。若x方向都为0，则也共线（竖直）。
5. 行列式法
def is_colinear_det(pt1, pt2, pt3, tol=1e-8):
# 原理：三点齐次坐标的行列式为0
import numpy as np
m = np.array([
[pt1[0], pt1[1], 1],
[pt2[0], pt2[1], 1],
[pt3[0], pt3[1], 1]
])
return abs(np.linalg.det(m)) < tol
解释：三点齐次坐标组成3x3矩阵，行列式为0代表共线。
6. 距离法（中间点在线段两端点之间）
def is_colinear_dist(pt1, pt2, pt3, tol=1e-8):
# 原理：距离相加等于最远距离说明三点共线
from math import hypot
def dist(a, b): return hypot(a[0] - b[0], a[1] - b[1])
d12 = dist(pt1, pt2)
d23 = dist(pt2, pt3)
d13 = dist(pt1, pt3)
return abs((d12 + d23) - d13) < tol or abs((d12 + d13) - d23) < tol or abs((d13 + d23) - d12) < tol
解释：如果三点共线，其中一点在线段两端之间，则任意两段距离和等于第三段距离。
7. 点到直线距离法
def is_colinear_pt2line(pt1, pt2, pt3, tol=1e-8):
# 原理：第三点到前两点连线的距离为0
from math import hypot
x1, y1 = pt1
x2, y2 = pt2
x3, y3 = pt3
num = abs((y2 - y1)*x3 - (x2 - x1)*y3 + x2*y1 - y2*x1)
den = hypot(y2 - y1, x2 - x1)
if den < tol:
return hypot(x3 - x1, y3 - y1) < tol # 三点重合也算共线
return (num / den) < tol
解释：计算点3到点1-2连线的距离为0（或很小）则共线。
8. 方向余弦法
def is_colinear_cos(pt1, pt2, pt3, tol=1e-8):
# 原理：夹角为0或180度（cos值为1或-1）说明共线
from math import hypot, isclose
x1, y1 = pt1
x2, y2 = pt2
x3, y3 = pt3
vx1, vy1 = x2-x1, y2-y1
vx2, vy2 = x3-x2, y3-y2
len1 = hypot(vx1, vy1)
len2 = hypot(vx2, vy2)
if len1 < tol or len2 < tol:
return True
cos_theta = (vx1*vx2 + vy1*vy2) / (len1 * len2)
return isclose(abs(cos_theta), 1, abs_tol=tol)
解释：三点共线时，夹角为0°或180°，cos值为1或-1。
9. 多项式插值法
def is_colinear_poly(pt1, pt2, pt3, tol=1e-8):
# 原理：三点能被一次多项式准确插值
x = [pt1[0], pt2[0], pt3[0]]
y = [pt1[1], pt2[1], pt3[1]]
import numpy as np
coeffs = np.polyfit(x, y, 1) # 一次多项式拟合
y_fit = [coeffs[0]*xi + coeffs[1] for xi in x]
err = sum(abs(yi - yfi) for yi, yfi in zip(y, y_fit))
return err < tol
解释：三点在同一条直线上，拟合一次多项式误差为0。
10. 参数比例法
def is_colinear_param(pt1, pt2, pt3, tol=1e-8):
# 原理：第三点能被前两点参数表达
x1, y1 = pt1
x2, y2 = pt2
x3, y3 = pt3
if abs(x2 - x1) > tol:
t = (x3 - x1) / (x2 - x1)
y_pred = y1 + t * (y2 - y1)
return abs(y3 - y_pred) < tol
elif abs(y2 - y1) > tol:
t = (y3 - y1) / (y2 - y1)
x_pred = x1 + t * (x2 - x1)
return abs(x3 - x_pred) < tol
else:
return abs(x1 - x2) < tol and abs(x2 - x3) < tol and abs(y1 - y2) < tol and abs(y2 - y3) < tol
解释：如果三点共线，第三点坐标能用前两点的参数表达出来。
