python - 如何检查所有给定点(空间中)是否位于同一条线上？

Question

我需要实现一个函数，该函数将任意数量的点的坐标作为输入数据，并根据这些点是否位于同一条线上或返回True或False不是。

我使用Python来解决这个问题，现在我有以下实现:

def are_colinear(points, tolerance): # variable "points" is a list of lists with points coordinates
    for i in range(2, len(points)):
        if (points[i][0] - points[i-2][0])/(points[i-1][0] - points[i-2][0]) - (points[i][1] - points[i-2][1])/(points[i-1][1] - points[i-2][1]) < tolerance and \
           (points[i][1] - points[i-2][1])/(points[i-1][1] - points[i-2][1]) - (points[i][2] - points[i-2][2])/(points[i-1][2] - points[i-2][2]) < tolerance:
            continue
        else:
            return False
    return True

该方法基于穿过两点的直线方程:

这种方法的缺点是，如果您想检查属于同一平面的点，它会引发错误(在这种情况下，三个坐标之一始终等于零，因此分母之一为零)。我需要更好的实现。预先感谢您!

Answer 1

取任意一个坐标，将其作为新的原点，相应地平移所有坐标。现在，将每个坐标视为位置向量。标准化每个向量。现在，如果任意两个向量平行，它们的点积就是 1。事实上，它们是同一个向量。如果两个向量反平行，则它们的点积为 -1，并且一个向量是另一个向量的负数。

当您将其全部展开时，您会发现不需要进行任何除法，可以避免任何平方根，并且不需要处理特殊的边缘情况。

1 ?= abs(dot(norm(u), norm(v)) 
   = abs(dot(u, v) / (mag(u) * mag(v)))
   = dot(u, v)^2 / (mag(u) * mag(v))^2

1 = (ux*vx + uy*vy + uz*vz)^2 / (sqrt(ux^2 + uv^2 + uz^2) * sqrt(vx^2 + vy^2 + vz^2))^2
1 = (ux*vx + uy*vy + uz*vz)^2 / ((ux^2 + uv^2 + uz^2) * (vx^2 + vy^2 + vz^2))

(ux^2 + uv^2 + uz^2) * (vx^2 + vy^2 + vz^2) = (ux*vx + uy*vy + uz*vz)^2

这很容易编码:

def are_parallel(points):
    points = set(points)  # dedupe
    if len(points) < 3:
        return True

    xo, yo, zo = points.pop()  # extract origin

    translated_points = [(x-xo, y-yo, z-zo) for x, y, z in points]
    ux, uy, uz = translated_points[0]  # first/reference vector
    u_mag_sqr = ux**2 + uy**2 + uz**2

    for vx, vy, vz in translated_points[1:]:  # rest of vectors
        v_mag_sqr = vx**2 + vy**2 + vz**2
        uv_dot_sqr = (ux*vx + uy*vy + uz*vz)**2
        if u_mag_sqr * v_mag_sqr != uv_dot_sqr:
            return False
    return True

再次强调，这避免了除法、平方根或任何会引入浮点比较的东西，否则可能是整数坐标，它更快，因为它只是乘法和加法，并且没有奇怪的边缘围绕特定坐标类别的情况。