是否存在复杂度优于O(N²)的三维空间N条线段相交检测算法？

是有的，核心思路是通过空间剪枝去掉绝大多数不可能有接触的线段对，平均时间复杂度可以降到O(N log N)，远优于O(N²)的朴素比对，适合线段数量较大的场景。具体实现可以按粗筛→精检两步走：

第一步：AABB粗筛剪枝 #

先为每一条线段生成轴向包围盒（AABB）：对每个线段的两个端点，分别取x、y、z三个维度的最大值和最小值，构成一个刚好包裹住线段的长方体。两个线段的AABB如果不相交，那么线段本身绝对不可能有任何接触，直接跳过后续比对，这一步可以过滤掉90%以上的无效比对。
粗筛阶段可以搭配以下任意一种空间划分方法进一步降低比对量：

• 均匀网格划分：根据所有线段的整体空间范围，将三维空间切分为尺寸均等的立方体网格，网格尺寸推荐取所有线段平均长度的1~2倍。每个线段只需要和它穿过的网格内的其他线段做比对，不需要和全局所有线段比对。
• 八叉树划分：如果线段空间分布极不均匀，用八叉树动态递归拆分空间，将线段挂载到其覆盖的树节点上，比对时仅需要和同一节点、相邻节点内的线段做校验，适配性更强。
• 轴扫掠算法：任选一个轴（比如x轴），将所有线段AABB的该维度起止边界做排序，沿轴扫掠的过程中维护当前激活的线段集合（即AABB的该维度范围和当前线段重叠的线段），仅激活集合内的线段需要进入后续校验，排序复杂度为O(N log N)，扫掠过程平均复杂度为O(N)。

第二步：精确几何校验 #

只有通过粗筛的线段对才需要做精确几何判断，按照你的规则，校验逻辑按以下顺序执行（可以提前设置浮点误差阈值比如1e-8，避免精度问题导致的误判）：

1. 共面判断：计算两个线段方向向量的叉乘，再和两个线段任意一对端点的连线向量做点积，结果绝对值大于阈值说明不共面，不可能有接触，直接判定合法。
2. 端点接触判断：如果两个线段的任意两个端点坐标差的模长小于阈值，属于合法的端点接触，直接跳过后续校验。
3. 非端点相交判断：将两个线段参数化为 P(t) = A + t*(B-A)、Q(s) = C + s*(D-C)（t、s ∈ [0,1]），求解线性方程组，若存在解落在(0,1)开区间内，属于非法相交。
4. 共线重叠判断：如果线段共线，将所有端点投影到线段的方向向量上得到四个标量值，若两个线段的投影区间重叠长度大于阈值，属于非法重叠。

额外说明 #

如果你的线段数量不大（比如小于1000条），O(N²)的朴素算法反而更实用，实现逻辑简单，不容易出现几何计算的边界bug，优化算法的额外开销甚至可能高于朴素比对。只有当线段数量超过1万条时，才推荐使用上述空间剪枝的优化方案。

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