如何寻找3D空间中到所有给定线段欧氏距离之和最小的三维点

问题本质 #

• 该问题属于无约束凸优化问题：三维点到单条线段的欧氏距离是凸函数，多个凸函数的和仍为凸函数，因此目标函数不存在局部极小值，求解得到的极小值就是全局最优值。

工程实现首选方案：次梯度下降法 #

因为目标函数在刚好落在线段上的点处不可导，使用次梯度替代梯度迭代，实现简单且收敛稳定：

1. 点到线段距离的计算 #

先定义点 p 到线段 S_i（两端点为a_i、b_i）的距离函数，同时返回线段上到p最近的点：

import numpy as np

def calc_dist_and_closest(p: np.ndarray, a: np.ndarray, b: np.ndarray) -> tuple[float, np.ndarray]:
    ab = b - a
    ap = p - a
    # 计算投影参数并截断到[0,1]区间保证最近点落在线段上
    t = np.dot(ap, ab) / (np.dot(ab, ab) + 1e-8) # 加小常数避免除以0
    t = np.clip(t, 0.0, 1.0)
    closest_point = a + t * ab
    dist = np.linalg.norm(p - closest_point)
    return dist, closest_point

2. 次梯度迭代流程 #

• 初始化最优解候选：取所有线段所有端点的均值作为初始点p0，避免初始位置偏差过大
• 步长设置：使用衰减步长eta_k = eta0 / sqrt(k)，其中k为当前迭代次数，eta0可初始设为1
• 迭代规则：
  1. 对当前点p，遍历所有线段，计算每个线段对应的次梯度项g_i：
     • 若p与该线段的最近点c_i不重合，g_i = (p - c_i) / (||p - c_i|| + 1e-8)
     • 若p与c_i重合，g_i取零向量即可
  2. 总次梯度g = sum(g_i for all i)
  3. 更新点：p = p - eta_k * g
• 终止条件：两次迭代点的欧氏距离小于1e-6，或迭代次数超过1e4，停止迭代得到的p就是近似最优解

其他可选方案 #

可以类比多点几何中位数的Weiszfeld算法，修改迭代权重适配线段场景，收敛速度比次梯度下降更快，适合线段数量极大的场景。

特殊场景简化 #

• 若所有线段存在公共交点，该交点就是最优解，总距离为0
• 若所有线段共面，最优解一定在该平面内，可降为2D问题求解，减少计算量

提示：由于目标函数是严格凸的，只要步长设置合理，任意迭代初始点都会收敛到同一个全局最优解，不需要尝试多个初始点。

内容的提问来源于stack exchange，提问作者Іван Манчур