14

我找到了一些解决方案，但它们太乱了。

4

4 回答 4

8

是的。集合 C的切比雪夫中心x* 是位于 C 内部的最大球的中心。 [Boyd, p. 416]当C是一个凸集时，那么这个问题就是一个凸优化问题。

更好的是，当 C 是多面体时，这个问题就变成了一个线性规划。

假设 m 边多面体 C 由一组线性不等式定义：ai^T x <= bi，对于 {1, 2, ..., m} 中的 i。那么问题就变成了

maximize  R
such that ai^T x + R||a|| <= bi,  i in {1, 2, ..., m}
          R >= 0

其中最小化的变量是R和x，并且||a||是 的欧几里得范数a。

于 2010-10-31T03:32:18.607 回答
6

总结：这不是微不足道的。所以它不太可能不会变得混乱。但是有一些讲座幻灯片，您可能会觉得有用。

资料来源： http ://www.eggheadcafe.com/software/aspnet/30304481/finding-the-maximum-inscribed-circle-in-c.aspx

您的问题并非微不足道，而且没有开箱即用的 C# 代码可以做到这一点。你必须自己写。我发现这个问题很有趣，并做了一些研究，所以这里有一些线索可能会有所帮助。

首先，这是来自 mathforum.org 的“简单英语”答案：

http://mathforum.org/library/drmath/view/67030.html

答案将 Voronoi 图作为一种提高流程效率的方法。在研究 Voronoi 图时，结合“最大空圆”问题（相同的问题，不同的名称），我遇到了这篇内容丰富的论文：

http://www.cosy.sbg.ac.at/~held/teaching/compgeo/slides/vd_slides.pdf

它由奥地利萨尔茨堡大学的计算几何学教授 Martin Held 撰写。对赫尔德博士著作的进一步研究产生了几篇好文章：

http://www.cosy.sbg.ac.at/~held/projects/vroni/vroni.html http://www.cosy.sbg.ac.at/~held/projects/triang/triang.html

对 Vornoi 图的进一步研究产生了以下站点：

http://www.voronoi.com/

该站点包含大量信息、各种语言的代码以及指向其他资源的链接。

最后，这里是美国国家标准与技术研究院（美国）数学与计算科学部的 URL，包含有关各种数学的大量信息和链接：

http://math.nist.gov/mcsd/

-- HTH,

凯文斯宾塞微软 MVP

于 2010-10-17T14:40:29.307 回答
6

也许这些“太杂乱”的解决方案正是您真正想要的，而且没有更简单的解决方案？

我可以提出一个简单但可能不精确的解决方案，它使用数值分析。假设你有一个有弹性的球，你从零半径开始给它充气。如果它的中心不在你要找的中心，那么它会移动，因为墙壁会将它“推”向正确的方向，直到它到达那个点，从那里他不能移动到其他任何地方。我猜，对于凸多边形，球最终会移动到它具有最大半径的点。

您可以编写一个模拟圆膨胀过程的程序。从任意点开始，然后“膨胀”圆直到它到达墙壁。如果你继续给它充气，它会朝一个方向移动，不会让它更靠近它已经遇到的墙壁。您可以通过绘制与墙壁平行的线穿过您当前所在的中心来确定它可以移动的可能方式。

在此示例中，球将沿绿色标记的方向之一移动：


（来源：coldattic.info）

然后，在其中一个方向上稍微移动你的球（一个不错的选择可能是沿着角度的平分线移动），然后重复该步骤。如果新半径小于您的半径，请撤退并降低移动速度。当你必须让你的速度小于一个值时，比如说，1英寸，那么你已经找到了精度为1英寸的中心。（如果你要在屏幕上绘制它，精度为0.5像素我猜会足够好）。

如果一个不精确的解决方案对你来说足够了，我想这很简单。

于 2010-10-17T14:53:13.900 回答
2

最大的内切圆（我假设它是唯一的）将与一些面相切，并且可能无法与其他面相交。如果最大的内切圆与其相交，我们称一个面为“相关”，否则为“不相关”。

如果你的凸多边形实际上是一个三角形，那么这个问题可以通过计算三角形的中心，通过角平分线相交来解决。这似乎是一个微不足道的情况，但即使你的凸多边形很复杂，内切圆也总是与至少三个面相切（证明？在几何上似乎很明显），因此它的中心可以计算为三个相关面的中心（向外延伸以形成一个外接原始多边形的三角形）。这里我们假设没有两个这样的面是平行的。如果两条平行线，我们必须将两条平行线的“角平分线”解释为它们之间的第三条平行线。

这立即提出了一个相当糟糕的算法：考虑所有 n-choose-3 面子集，如上所述找到所有三角形的中心，并测试每个圆是否包含在原始多边形中。在合法的范围内最大化。但这是 n 的三次方，我们可以做得更好。

但是可以预先识别不相关的面：如果一个面与某个内切圆相切，则存在一个由该面及其端点处的两个角平分线界定的点区域，其中圆的中心必须位于。如果即使中心位于该三角形区域最远尖端的圆是“合法的”（完全包含在多边形中），那么面本身也是无关紧要的，并且可以被删除。接触它的两个面应该延伸到它之外，以便它们相遇。

通过迭代地删除在这个意义上不相关的面，您应该能够将多边形简化为三角形，或者可能是梯形，此时问题将很容易解决，并且其解决方案仍将位于原始多边形内。

于 2010-10-18T15:53:51.083 回答