Python中检测共线点的循环代码加速方案求助

我有一组随机点，需要检测哪些点能被同一条直线连接。目前的做法是遍历所有点，为每个点生成不同角度的直线；之后再遍历每条直线，检查是否连接了3个及以上的点，符合条件的直线存入newLines列表。

但当前代码运行速度极慢：测试图要跑30分钟，实际场景跑了14小时还没完成。我知道可以用numpy加速循环，但找到的示例都是简单列表遍历，没涉及我代码里的变量赋值场景。求加速思路，不限于numpy方案。

原代码 #

# list for saving rotated lines
lines=[]

for point in points:
    # length of line is the diagonal of the point image so it still covers the whole image after rotation
    length = sqrt(image.shape[0]**2+image.shape[1]**2)
    start = Point(point)
    end = Point(start.x+length, start.y)
    line = LineString([start,end])
    # rotating the generated line for 5 degrees and appeding it to the list
    for a in range(0, 360, 5):
        angle = np.deg2rad(a)
        line = rotate(line, angle, origin=start, use_radians=True)
        lines.append(line)

multiLines = MultiLineString(lines)

# list for rotated lines which connect 3 or more points
newLines = []
start = ()

for multiLine in multiLines.geoms:
    lst = list(multiLine.coords)
    # a: starting point of line | b: ending point of line
    a = np.asarray(lst[0])
    b = np.asarray(lst[1])
    count = 0
    # again iterating over point array to check which point is on line
    for point in points:
        p = np.asarray(point)
        # check if point (p) is on line (a - b)
        if np.cross(p-a,b-a) == 0:
            if count == 0:
                start = point
                count += 1
            else:
                end = point
                count += 1
    if count >= 3:
        line = (start, end)
        newLines.append(line)

1. 重构核心逻辑：从暴力生成直线转为基于点对斜率分组 #

当前思路时间复杂度为O(N²×72)（N为点数），完全不适合大数据量。更高效的方式是利用共线点的斜率特性：

• 任意三个共线点，相对于其中某一点的斜率必然相同
• 遍历每个点作为基准，计算它到所有其他点的斜率+距离，将斜率相同的点归为一组
• 若组内点数≥3，说明这些点共线，直接生成对应直线

用numpy可批量计算斜率：将点转为N×2数组，对每个基准点用广播计算差值，再计算斜率（垂直直线用特殊标记，比如无穷大），之后用字典分组统计。

2. 消除冗余计算与重复直线 #

原代码会生成大量重复直线（不同点生成的同角度直线可能是同一条），导致重复验证。用斜率分组的方式，每个共线点组只会被处理一次，还可通过记录已处理点对避免重复。

3. 用numpy批量替代循环验证 #

将点转为numpy数组后，直线验证可批量完成，彻底去掉内层循环：

points_np = np.array(points)
# 假设a、b是直线端点（numpy数组）
# 批量计算所有点与直线的叉乘
cross_products = np.cross(points_np - a, b - a)
# 用阈值判断浮点精度问题，筛选共线点
on_line_indices = np.where(np.abs(cross_products) < 1e-6)[0]
count = len(on_line_indices)

这种批量操作的速度比循环快100~1000倍。

4. 优化直线生成逻辑（若坚持原思路） #

避免用shapely的rotate生成直线，直接用三角函数计算旋转后的端点，减少对象创建开销：

import numpy as np
length = np.hypot(image.shape[0], image.shape[1])
points_np = np.array(points)
lines = []

for x0, y0 in points_np:
    # 批量生成所有角度的终点坐标
    angles = np.deg2rad(np.arange(0, 360, 5))
    x1 = x0 + length * np.cos(angles)
    y1 = y0 + length * np.sin(angles)
    # 直接存储端点对，跳过shapely对象
    lines.extend([((x0, y0), (x1_i, y1_i)) for x1_i, y1_i in zip(x1, y1)])

5. 处理浮点精度问题 #

原代码用np.cross(...) == 0会因浮点误差漏掉共线点，改用np.abs(cross_products) < 1e-6这类阈值判断，适配浮点运算的精度问题。

内容的提问来源于stack exchange，提问作者jonsken