您可以使用中轴变换

如果变换是离散的，则变换中的每个点都表示从该点到最近两条边的半径。将其加倍给出宽度。为了处理噪音，你可以取这些点的 95% 以上，然后取平均值。

您还可以查看旋转卡尺方法：

尽管我怀疑这不太适合您的用例。

我确信有比这更好的解决方案，但由于没有其他人回答这一点，我会抛出一个这就是我要做的答案。

1. 对多边形进行三角剖分如果你的多边形没有太多的点，一个简单的$\mathcal{O}(N^2)$ 剪耳法可能是可行的。对于大型多边形，这可能是一个低效的解决方案。对下一步很重要的是，此三角剖分仅使用现有顶点并且不引入任何新的内部点。
2. 求三角形高度每个只有一个外边的三角形都保证跨越多边形，所以计算从外边到三角形相对顶点的正交距离。
3. 减少到一个数字由于每个允许的三角形都有一个值，因此您需要将其减少到一个数字。最小值、最大值、平均值、中值？也许在你抛出异常值后取平均值？

虽然上述内容应该适用于您的“蠕虫状”多边形，但有很多病理情况会使输出值变得毫无意义。

我将假设我们有代表弯曲多边形的顶部和底部曲线的边缘数组，边缘从左到右。还将$n$作为该多边形中的边总数。现在考虑以下几何图形的可视化，其中我们使用凹多边形的两个“边”构造某个点：

很明显，如果我们从该点射出任何光线，给定方向是指向多边形两个“边”的方向的任意凸组合，那么光线将恰好与两条边相交。让我们假设存在一些辅助方法，可以采用两条线段并返回它们之间的最大距离。

确定性算法

如果您想要一个确定性算法，这里有一个想法，它使用基于上述假设和光线材料的想法。假设我们从顶部边界固定一些边$e = (v_1, v_2)$ 。我们可以查看从底部边界到在绘制到$e$的两个顶点的射线之间至少有一个顶点的所有边，并计算它们与$e$之间的最大距离，使用此结果更新整体最大宽度多边形。如果我们从左到右扇出多边形，我们可以在$O(n)$时间内完成所有这些工作，因为当我们检查上边界的新边时，我们可以从下边界停止的地方开始而不是从头开始。下面是事物如何分区的视觉效果

随机算法

鉴于早期的假设，以下蒙特卡洛风格的随机算法也可能是一种解决方案：

algorithm RandomizedMaxWidth
input (top_boundary[...], bottom_boundary[...], k)
output max_width

init max_width = 0
for i from 1 to k
   - randomly choose an edge e from (say) the top boundary (can do this with or without replacement)
   - use binary search to find first edge in the bottom boundary, denoted e1, that intersects ray going through left vertex of e
   - iterate over all edges from left to right, starting with e1, that have at least one vertex between the rays generated by the left and right vertices of e
      - for each edge, compute the maximum width between this edge and e using helper method and update the max_width accordingly
endfor

return max_width

上述算法使用带替换采样的运行时间是$O(k (\log(n) + c))$其中$c$对应于底部边界中与与边缘相交的光线相交的边缘的平均数量。顶部边界。失败概率对应于您从不选择与最大宽度对应的顶部边界上的边的概率。这个错误概率随着$k$变大而缩小，如果你随机选择带替换的边，$k = O(n)$给出一个恒定概率结果，这意味着运行时间是$O(n \log(n) + nc)$. 但是，如果形状通常像我们在示例中看到的那样“不错”，那么您可能可以获得不错的近似值（尤其是与边界框方法相比），使$k$在$n$中成为次线性，这将使算法成为$n$中的整个潜在亚线性，具体取决于$c$的值。

如果您讨厌常数$c$，您可以修改此算法以随机构造一条射线，该射线的方向在对应于两个“边”的方向之间随​​机选择。然后，对于每条随机光线，找到两条相交的边，然后计算这两条边之间的最大宽度。如果你使用$k$随机射线，那么这个算法会给出$O(k \log(n))$运行时间。使用足够大的$k$，您应该得到一个不错的估计，尽管与上述算法相比，错误概率可能更大。同样，如果形状通常“不错”，则选择$k$在$n$中是次线性的可能足以在实践中获得不错的结果，这意味着整体次线性随机算法。

事实上，对于原始问题中绘制的示例，单个样本将证明比使用边界框方法更准确，这将为我们提供$O(\log(n))$近似算法。