Python中2D/3D网格直线交点去重的精度与性能优化问题

一、精度问题核心解决：彻底消除浮点误差 #

• 分数运算存储交点：规则网格的坐标均为有理数，所有直线交点的坐标必然也是有理数。用Python内置的fractions.Fraction存储交点的每个坐标，完全避免浮点舍入误差。相同交点的Fraction元组哈希值完全一致，直接用集合去重即可。
• 直线方程整数归一化：用整数系数(a, b, c)表示2D直线ax + by + c = 0，通过最大公约数归一化系数并统一符号，确保同一直线只会被存储一次，避免重复计算交点。3D场景同理，用整数向量表示直线的方向向量和点，计算交点时全程用分数运算。

二、性能优化：减少冗余计算 #

• 利用网格对称性：
  • 2D网格：仅计算第一象限（或对称子区域）的点对生成的直线，其余直线通过镜像、旋转等对称变换推导，避免重复计算。比如3x3网格，只需处理一半的点对，再通过对称补全所有直线。
  • 3D网格：利用坐标轴对称性，只处理x≤y≤z的点对，其余点对生成的直线可通过坐标置换得到，大幅减少直线生成数量。
• 跳过重复直线：生成直线时，将归一化后的直线标识存入集合，自动过滤重复直线，避免对同一直线进行多次交点计算。
• 批量过滤平行直线：对于同方向的直线组，直接判定无交点，跳过后续计算。比如2D中斜率相同的直线、3D中方向向量共线的直线，无需计算交点。

三、2D/3D通用实现示例（简化版） #

from fractions import Fraction
from itertools import combinations
import math

def normalize_line_2d(p1, p2):
    # 返回归一化的整数直线系数(a, b, c)，对应ax + by + c = 0
    x1, y1 = p1
    x2, y2 = p2
    a = y2 - y1
    b = x1 - x2
    c = x2 * y1 - x1 * y2
    
    # 用最大公约数归一化
    gcd_val = math.gcd(math.gcd(abs(a), abs(b)), abs(c))
    if gcd_val != 0:
        a //= gcd_val
        b //= gcd_val
        c //= gcd_val
    
    # 统一符号，确保同一直线唯一标识
    if a < 0 or (a == 0 and b < 0):
        a = -a
        b = -b
        c = -c
    return (a, b, c)

def compute_intersection_2d(line1, line2):
    a1, b1, c1 = line1
    a2, b2, c2 = line2
    det = a1 * b2 - a2 * b1
    if det == 0:
        return None  # 平行或重合，无唯一交点
    x = Fraction(b1 * c2 - b2 * c1, det)
    y = Fraction(a2 * c1 - a1 * c2, det)
    return (x, y)

# 3x3网格测试
grid = [(i, j) for i in range(3) for j in range(3)]
unique_lines = set()
for p1, p2 in combinations(grid, 2):
    unique_lines.add(normalize_line_2d(p1, p2))

unique_intersections = set()
for l1, l2 in combinations(unique_lines, 2):
    pt = compute_intersection_2d(l1, l2)
    if pt is not None:
        unique_intersections.add(pt)

print(f"唯一交点数量：{len(unique_intersections)}")  # 输出61，符合预期

四、3D场景适配要点 #

• 用整数向量表示直线的方向向量和经过的点，计算两条直线的共面性时，用混合积（整数运算）判断是否为0；
• 若共面且相交，用分数运算求解交点坐标，存储为Fraction三元组，通过集合去重；
• 同样利用3D网格的对称性减少直线生成量，比如仅处理x轴、y轴、z轴方向的对称点对。

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