※ 引述《peter26194 (啦啦哼哈)》之铭言：
: ※ 引述《FRAXIS (喔喔)》之铭言：
: : 我被问过一个问题：在三维空间中有两个相同大小的圆盘位于不同位置
: : （朝向也可能不同），求这两圆盘间的最短距离。除了暴力法我还真想
: : 不出来怎么作..
: 最近也在面试，看到那道题目，试着想了一下解法：
: 给定两圆c1, c2
: 找出两圆各自所在的平面p1, p2
: 把两圆圆心连线得到L线段
: 将L投影到p1上，得到L1线段
: L1的一端点是c1圆心，
: 1)另一端点如果在圆c1之内，那么此端点就设为a1;
: 2)另一端点如果在圆c1之外，那么则把a1定为L1和c1的交点
: 用同样方法，将L投影到p2上，得到L2线段，再找出a2
: 则a1, a2连线就是最短距离
: 灵感是从“平面上的两圆，要找最短距离，要找圆心连线和两圆的交点”而来的，
: 我也不太确定这是对的，大家觉得呢？
: (虽然在这里讨论怪怪的，不过应该是可以的吧？)
先厘清一下问题的定义, 确定大家讨论的是同一个问题.
圆盘的定义是在某平面上距离圆心小于某半径的点集合对吧?
如果是两个圆周找最近点的话问题就简单得多.
首先先简化问题. 由于对空间进行旋转跟平移不影响问题的答案(证明留给读者),
所以先假设两圆盘的半径为 1, 其中一个圆盘位于 XY 平面上,
(i.e. 即圆心为原点 {0, 0, 0} , 法向量平行 Z 轴 {0, 0, 1}),
另一个圆盘圆心向量 C, 法向量 N.
于是这个问题可以写成求
argmin[A,B](|A - B|),
A · {0, 0, 1} = 0 (1. A 点位于 XY 平面)
|A × {0, 0, 1}| <= 1 (2. A 点限制在半径 1 的 Z 轴圆柱)
B · N = C · N (3. B 点与 C 共平面, 法向量 N)
|(B - C) × N| <= 1 (4. B 点限制在半径 1 的 CN 圆柱)
由于条件 1 跟 3 可以简化一维的自由度, 即已知
Az = 0
Bz = (C · N - BxNx - ByNy) / Nz
问题可简化为四元二次的 optimization with boundary condition.
当然这样还是太复杂, 我们必须进一步简化问题.
一个观察是, 当两个圆盘的法向量平行的时候这个问题有 degenerate solution,
可以直接将两个圆盘投影到任意一个平行平面上,
若有重叠则重叠范围内的任一对点皆是最短距离.
若无重叠则可选圆心投影连线与两个圆周的交点.
现在考虑两个圆盘法向量不平行的情形,
可以证明两点至少有一个点位于圆周上. 利用归谬法, 假设两点皆非位于圆周,
则两点连线必然与其中一个圆盘的法向量不平行,
因此可以移动该圆盘上的点往连线方向移动而使得连线缩短.
在此我们将问题再次简化成空间中一圆盘与一圆周求最近两点. (三元二次最佳化问题.)
现在我们再考虑简化问题, 求空间中一点与圆盘间最短距离.
这个问题可以写成简单函数. 我们再次经由空间变换把圆盘换到以原点为圆心,
法向量平行 Z 轴, 半径 1, 输入点为 P.
若 P 点在 XY 平面的投影落在圆内, 则答案为 Pz.
不然则取投影点与圆心连线在圆周上的交点, 即 hypot(hypot(Px, Py)-1, Pz).
Lemma 1: 空间中一点 P 与单位圆盘的最短距离为
f(P) = if hypot(Px, Py) < 1, Pz
else, hypot(hypot(Px, Py)-1, Pz)
回到原问题, 求空间中一圆周与单位圆盘之最短距离, 可以改写为
argmin[P](f(P))
P · N = C · N
|(P - C) × N| = 1
由于 P 点的自由度只有一维, 其实可以视为一元最佳化问题, 可以经由微分 f 来求极值.