求解两条曲线间全域可容纳的最大半径圆的最优方法

首先明确核心需求：我们要找的是最大半径R，使得半径为R的圆可以完全被包含在两条离散化正弦曲线的区域内——换句话说，这个圆在曲线区间的任意位置放置时，都不会超出上、下曲线的边界。

你之前考虑的逐点迭代放大圆的方法确实效率偏低，尤其是离散点数量较多时。下面是更高效的实现思路：

1. 核心原理：基于曲线法向间隙的计算 #

圆要能被两条曲线容纳，最大的限制来自两条曲线在局部的法向最小间隙——因为圆的边缘需要同时不触碰两条曲线，而法向是圆的半径方向（圆的切线与曲线切线平行时，半径方向就是曲线的法向）。对于任意位置，能容纳的最大圆半径等于该位置两条曲线法向间隙的一半；而我们要找的全局最大R，就是所有位置法向间隙一半中的最小值（这个R能满足所有位置的容纳要求）。

2. 高效计算步骤 #

（1）预处理曲线的切线斜率 #

对于离散化的曲线点，用中心差分法计算每个点的切线斜率（精度比前向/后向差分更高）：

• 对于下曲线第i个点$(x_i, y1_i)$，斜率$k1_i = \frac{y1_{i+1} - y1_{i-1}}{x_{i+1} - x_{i-1}}$
• 首尾点可以用前向/后向差分近似，比如第一个点$k1_0 = \frac{y1_1 - y1_0}{x_1 - x_0}$

如果是解析形式的正弦曲线（比如$y = A\sin(\omega x + \phi) + B$），直接用导数计算斜率：$k = A\omega\cos(\omega x + \phi)$，这比离散差分更准确高效。

（2）计算局部法向间隙 #

对于每个离散点$x_i$：

• 写出下曲线的切线方程$L1: y - y1_i = k1_i(x - x_i)$
• 写出上曲线的切线方程$L2: y - y2_i = k2_i(x - x_i)$
• 计算两条切线之间的距离：
  • 若两条切线平行（$k1_i = k2_i$），距离$d = \frac{|y2_i - y1_i|}{\sqrt{k1_i^2 + 1}}$，这就是该位置的法向间隙
  • 若两条切线相交，说明局部区域的间隙没有被切线限制，此时需要取该点上下曲线的y方向间隙$|y2_i - y1_i|$，同时结合相邻点的情况判断（因为相交切线的区域是发散的，限制可能来自曲线的弯曲部分）

（3）补充检查区间内的最小间隙 #

离散点之间可能存在更小的间隙，尤其是曲线弯曲度变化大的位置。可以用二分法在相邻离散点的区间内细分查找：

• 对区间$[x_i, x_{i+1}]$，取中点$x_m$，用插值（线性或样条）得到两条曲线在$x_m$处的y值和斜率，计算法向间隙
• 比较中点与两端点的间隙大小，逐步缩小范围找到该区间的最小间隙

（4）确定全局最大半径 #

把所有离散点和细分区间计算得到的法向间隙收集起来，取其中的最小值，除以2就是最终的最大R。

3. 为什么比逐点迭代更快？ #

这种方法的时间复杂度是$O(n)$（离散点数量为n），如果加上区间细分，最多是$O(n\log n)$，远低于逐点迭代的$O(n \times k)$（k是每个点的迭代次数）。而且直接基于几何计算，不需要反复进行圆与曲线的碰撞检测，避免了冗余计算。

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