给定一个凸多边形，我试图在保持其直径的同时扩大其形状（如“最大面积”）。直径定义为可以放置在多边形内的最长线段的长度。由于多边形是凸的，我假设这个直径总是可以通过扫描所有顶点对来找到。
例如，给定一个等边三角形作为输入多边形，三角形的直径是任意边的长度；平滑这将导致 3 个圆段，如图所示
对于任意凸多边形，一个非常低效的算法是计算以每个多边形顶点为中心的最大直径半径圆的交点；这就是我目前正在使用的（在 Java 中）。有更好的吗？任何伪代码或算法指针都将不胜感激。
另一个例子：一个被压扁的五边形及其对应的保持直径的最大形状。这个想法是你不能在不增加直径的情况下增加这个形状的面积（也就是说，可以在形状的边界内绘制一条比原始直径长的直线）。在这种特殊情况下，半径 = 多边形直径/2（粉红色）的单个圆似乎比半径 = 多边形直径（浅蓝色）的多个较大圆的交集要好。第二张图像将两个区域叠加在一起，以便于比较，但区域应完全包围多边形。
计算交点比看起来简单；您实际需要做的就是确定与两个相邻顶点等距的点；你最终会得到两点，但最接近形状中心的几乎肯定是正确的；它甚至可以保证凸多边形，但数学证明不是我的强项。
在我看来，您当前的算法不仅效率低下而且不正确。以当前直径略大于 10 的矩形为例(0,0)-(10,0)-(10,1)-(0,1)。在所有拐角处用该半径与圆相交，你最终会得到一个直径超过 16 的相当大的透镜状物体。所以该算法不会不行。
您可以通过再次将形状与围绕新顶点之一的直径大小的圆相交来修复多余的直径，但是您选择使用的顶点是任意的。而且无论选择什么，最终的“臃肿三角形”形状仍然显得比矩形的外接圆小。我假设在我的情况下，该外接圆将是最佳解决方案，但我看不到一种简单的方法来修改您的算法以找到该解决方案，同时保持其普遍性。
这只是一种直觉，但我怀疑所需的输出是否由输入多边形和您的要求唯一定义。虽然我还没有这个效果的例子，但我相信可能存在多个“平滑”形状的输入多边形，它们都具有相同的面积和相同的直径，但彼此之间仍然不一致。可能值得将其带到数学堆栈交换中，以进一步讨论这个存在问题。
事实证明，这个问题已经在Math Overflow上被问到，人们认为这可能是一个难题。甚至还有一些悬而未决的基本问题，比如这样的形状是否独一无二。
所以我没有一个确切的解决方案，但希望这会让你更接近或至少给你一些想法。
为简单起见，我们可以不失一般性地假设初始多边形的直径为 1。
关于磁盘多边形的 Blaschke-Lebesgue 定理的推广(M. Bezdek, 2009) 描述了许多有用的概念。相关的包括：
不用多边形，用圆盘多边形就足够了：我们总是可以用它的主轴凸包替换原始多边形而不改变结果。
当D的直径为 1时，我们有D ⊆ D* ，当且仅当D具有恒定宽度 1 时， D = D*。解S将具有恒定宽度 1（尽管这当然是不够的）。因此D ⊆ S当且仅当D ⊆ S ⊆ D*：特别是，要逼近S，我们只需要找到 S 的足够大的圆盘多边形子集D。这是非常强大的，因为正如我们将看到的，说某个点属于或不属于S转换为S（以及其面积）的上限和下限。
理想情况下，要找到一种有效的算法，回答以下问题会很有用：
关于圆盘多边形面积的问题可能很困难：将圆盘分开 - 平面中的 Kneser-Poulsen 猜想(K. Bezdek, R. Connelly, 2001) 中解决的问题是关于圆盘相交面积的简单问题在很久没有解决的飞机上。
全局搜索：
从多边形的主轴凸包开始，懒惰地构建一个无限增长的磁盘多边形搜索树，其中每个节点划分满足D ⊆ X ⊆ D*的所有等宽X的集合，取决于某个点是否D* \ D的x属于或不属于X。左分支是D ∪ { x } 的主轴凸包。右分支是D* ∩ { y : x ∉ [ y , z ] 的对偶圆盘多边形Z在D } 中。
除非您选择x非常差（例如在D* \ D的边界上），否则该树的每条无限路径都应收敛到恒定宽度曲线。
这个想法是以某种广度优先的方式探索树。希望如果以合理的方式选择x，您将能够丢弃 D* 的所有分支，其中D*的面积小于迄今为止找到的D的最大面积，因为这些分支不能包含解决方案。然后，当您在树中深入时，您将拥有一组圆盘多边形，它们会收敛到问题的一组解决方案，希望不会增长太快。
x的一些启发式方法可能是：取一个尽可能靠近D* \ D内部的点，取一个随机点，等等。结合一定数量的深度优先搜索以获得更精确的解决方案区域下限也可能很有趣，这将允许更快地丢弃树的整个分支。
局部搜索：
我们也可以只使用等宽的圆盘多边形（Reuleaux 多边形），并查看小偏差的影响。但是搜索空间非常大，所以不清楚如何做到这一点。