3D空间圆柱无重叠生成：现有检测算法缺陷及优化方案问询

我正在编写一个用于在3D空间中生成圆柱的脚本，希望生成的圆柱不会占据同一空间区域（避免重叠）。
圆柱由起点和终点定义，且所有圆柱的半径固定。
现有圆柱存储在名为listOfCylinders的n维数组中，其形状为(nCylinders, 2Points [start, end], {x,y,z} coordinates of each point)。

我编写了如下函数：

def detect_overlap(new_start, new_end, listOfCylinders):
    
    starts = listOfCylinders[:, 0]
    ends = listOfCylinders[:, 1]
    radius = 0.1
    
    # Calculate the distance between the new cylinder and all the existing cylinders
    dists = np.linalg.norm(np.cross(new_end - new_start, starts - new_start), axis=1) / np.linalg.norm(new_end - new_start)
    
    # Check if any of the distances are less than the sum of the radii
    if np.any(dists < (2*radius)):
        return True
    
    # If no overlap or intersection is found, return False
    return False

但该函数未覆盖侧向重叠的场景。请问是否有合适的算法可以解决这个问题？

你的当前代码只计算了新圆柱轴线到现有圆柱起点的垂直距离，这显然不全面——要判断两个有限长圆柱是否重叠，需要同时满足轴线最短距离小于2倍半径，且轴向投影区间有重叠，还要额外检查端点是否落在对方圆柱内部。

完整的检测逻辑需要分三步：

1. 计算两条轴线的最短距离
   对于两条线段（圆柱轴线）L1（新圆柱：P0-P1）和L2（现有圆柱：Q0-Q1），先计算它们的最短距离。如果这个距离大于2倍半径，直接判定不重叠。

   • 向量u = P1 - P0，v = Q1 - Q0，w = P0 - Q0
   • 分平行和非平行两种情况计算线段上的最近点，再得到最短距离。

2. 检查轴向投影区间的重叠性
   即使轴线距离足够近，还要验证两个圆柱的轴向投影是否有交集：

   • 将现有圆柱的端点投影到新圆柱的轴线方向，得到投影区间
   • 若该区间与新圆柱的投影区间[0,1]无交集，则两个有限长圆柱不会重叠

3. 端点区域的额外检查
   当其中一个圆柱的端点落在另一个圆柱内部时，也判定为重叠：

   • 检查现有圆柱的端点是否在新圆柱内部（垂直距离小于半径，且投影在轴线区间内）
   • 反过来检查新圆柱的端点是否在现有圆柱内部

整合后的代码实现 #

import numpy as np

def detect_overlap(new_start, new_end, listOfCylinders):
    radius = 0.1
    sum_radius = 2 * radius
    u = new_end - new_start
    u_norm_sq = np.dot(u, u)
    
    # 处理新圆柱是点的边界情况
    if u_norm_sq < 1e-10:
        for cyl in listOfCylinders:
            q0, q1 = cyl[0], cyl[1]
            v = q1 - q0
            v_norm_sq = np.dot(v, v)
            # 现有圆柱也是点
            if v_norm_sq < 1e-10:
                if np.linalg.norm(new_start - q0) < sum_radius:
                    return True
            # 现有圆柱是正常线段
            else:
                dist = np.linalg.norm(np.cross(v, new_start - q0)) / np.sqrt(v_norm_sq)
                proj = np.dot(new_start - q0, v) / v_norm_sq
                if dist < radius and 0 <= proj <= 1:
                    return True
        return False
    
    # 遍历所有现有圆柱
    for cyl in listOfCylinders:
        q0, q1 = cyl[0], cyl[1]
        v = q1 - q0
        v_norm_sq = np.dot(v, v)
        w = new_start - q0
        a = u_norm_sq
        b = np.dot(u, v)
        c = v_norm_sq
        d = np.dot(u, w)
        e = np.dot(v, w)
        denom = a * c - b * b
        
        # 计算线段上最近点的参数
        if denom != 0:
            # 非平行线段
            s = (b * e - c * d) / denom
            t = (a * e - b * d) / denom
            s_clamped = max(0.0, min(1.0, s))
            t_clamped = max(0.0, min(1.0, t))
        else:
            # 平行线段，取端点投影的中间值
            s0 = np.dot(w, u) / a
            s1 = np.dot(w + v, u) / a
            s_clamped = max(0.0, min(1.0, (s0 + s1)/2))
            t_clamped = 0.0
        
        # 计算最近点距离
        p_close = new_start + s_clamped * u
        q_close = q0 + t_clamped * v
        dist = np.linalg.norm(p_close - q_close)
        
        if dist > sum_radius:
            continue
        
        # 检查投影区间是否重叠
        proj_q0 = np.dot(q0 - new_start, u) / a
        proj_q1 = np.dot(q1 - new_start, u) / a
        proj_cyl_min = min(proj_q0, proj_q1)
        proj_cyl_max = max(proj_q0, proj_q1)
        
        if proj_cyl_max < 0 or proj_cyl_min > 1:
            # 投影无重叠，检查端点是否在对方圆柱内
            # 检查Q0/Q1是否在新圆柱内
            dist_q0 = np.linalg.norm(np.cross(u, q0 - new_start)) / np.sqrt(a)
            if dist_q0 < radius and 0 <= proj_q0 <= 1:
                return True
            dist_q1 = np.linalg.norm(np.cross(u, q1 - new_start)) / np.sqrt(a)
            if dist_q1 < radius and 0 <= proj_q1 <= 1:
                return True
            
            # 检查P0/P1是否在现有圆柱内
            if v_norm_sq < 1e-10:
                if np.linalg.norm(new_start - q0) < radius or np.linalg.norm(new_end - q0) < radius:
                    return True
            else:
                dist_p0 = np.linalg.norm(np.cross(v, new_start - q0)) / np.sqrt(v_norm_sq)
                proj_p0 = np.dot(new_start - q0, v) / v_norm_sq
                if dist_p0 < radius and 0 <= proj_p0 <= 1:
                    return True
                dist_p1 = np.linalg.norm(np.cross(v, new_end - q0)) / np.sqrt(v_norm_sq)
                proj_p1 = np.dot(new_end - q0, v) / v_norm_sq
                if dist_p1 < radius and 0 <= proj_p1 <= 1:
                    return True
            continue
        
        # 距离小于2r且投影有重叠，判定重叠
        return True
    
    return False

关键说明 #

• 加入了零长度圆柱（点）和平行轴线的边界情况处理，避免浮点计算错误。
• 使用1e-10作为精度阈值，抵消浮点运算的误差影响。
• 严格区分有限长圆柱和无限长圆柱的差异，确保所有重叠场景都被覆盖。

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