是否有一个简单的算法来计算凸多边形的最大内切圆？

Question

我找到了一些解决方案,但它们太乱了.

Answer 1

是.C组的切比雪夫中心 x*是C内最大球的中心.[Boyd,p.当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.

Answer 2

简介:这不是微不足道的.因此它不太可能不会变得混乱.但是你可能会发现一些有用的演讲幻灯片.

资料来源: 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 Diagrams作为一种使该过程更有效的方法.在研究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 Diagrams的进一步研究产生了以下网站:

http://www.voronoi.com/

该站点有许多信息,各种语言的代码以及其他资源的链接.

最后,这里是美国国家标准与技术研究院(美国)数学与计算科学部门的URL,有关各种数学的丰富信息和链接:

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

- HTH,

Kevin Spencer微软MVP

Answer 3

也许这些"太乱"的解决方案是你真正想要的,而且没有简单的解决方案？

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

您可以编写一个模拟循环通胀过程的程序.从一个任意点开始,然后"膨胀"圆圈直到它到达墙壁.如果你继续给它充气,它会向一个方向移动,使其不再接近它已经遇到的墙壁.您可以通过绘制与您当前所在的中心平行的墙线来确定可以移动的方式.

在此示例中,球将沿标有绿色的方向之一移动:

http://coldattic.info/pic/522403726925.png

然后,沿着这些方向之一稍微移动你的球(一个好的选择可能是沿着角度的二等分移动),然后重复这个步骤.如果新半径小于你的半径,则撤退并减小移动它的速度.当你必须使你的速度低于1英寸的值时,你就会发现精度为1英寸的中心.(如果你要在屏幕上绘制它,精度为0.5像素我想这会很好.

如果一个不精确的解决方案足够你,我想这很简单.