※ 引述《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 来求极值. -- その乾いた哀愁の瞳に去来するものは何か？ 失ったもの 得たもの そして广大なネットの狭间で彼が见たものとは？ 虚像と实存と记号の中に彼は今、何を想うのか？ ＜バトルプログラマーシラセ＞ --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 54.68.90.183 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Oversea_Job/M.1461801749.A.F86.html