如何计算简单凹多边形自相交前的最大收缩/偏移量？

核心逻辑 #

无需试错，直接通过分析多边形所有非相邻边对的偏移临界值，找到不会引发自相交的最大偏移量——取所有非相邻边对偏移后刚好相交时的临界距离中的最小值，即为安全上限。

具体步骤 #

• 遍历非相邻边对：跳过相邻边（它们的偏移线相交是生成新顶点的正常操作，不会导致自相交），仅处理任意两组不相邻的边。
• 计算边对的临界偏移距离d：
  1. 根据偏移方向（收缩向内、膨胀向外），为每条边生成偏移d后的平行直线。
  2. 求解两条偏移直线刚好相交时的d值——这个d就是该边对偏移到自相交的临界距离。
• 筛选有效临界值：
  • 仅保留符合偏移方向的正d值，同时验证相交点落在两条偏移边的线段范围内（而非直线的无限延长线），避免误判。
• 取全局最小值：所有有效临界d中的最小值，就是多边形的最大安全偏移量。

关键细节说明 #

• 凹顶点的自动覆盖：凹多边形的自相交风险主要来自凹顶点附近的边偏移后与其他边的冲突，遍历非相邻边对的过程已包含这种情况，无需单独针对凹顶点做特殊处理。
• 直线偏移的计算：每条边的偏移直线可通过原直线方程结合法向量推导——比如原直线ax + by + c = 0，向内偏移d的直线为ax + by + c + d*sqrt(a²+b²) = 0（符号由多边形内部法向量方向决定）。
• 临界d的有效性验证：算出d后需确认，两条偏移边的线段确实会在该d值下相交，排除无限延长线相交的无效情况。

示例匹配 #

你提到的凹多边形案例中，最短边长度3，按旧方法得到的1.5会导致自相交，但通过上述方法计算，会得到临界d=0.5——这就是该多边形的最大安全收缩量，完全符合实际情况。

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