多边形的最大内圆问题

markfang2050

测试1000边形，计算结果准确。

kastin

这个相当于计算几何里面的闵可夫斯基差运算(将多边形对一定半径的圆作差，得到的图形在多边形内部形成类似的封闭图形，这个封闭图形实际上是由直线段和圆弧构成)，当圆的半径从小变大时，所得的封闭图形面积越来越小，直至形成一个个点（可以是离散的，或连续的线段），最后它们全部消失。记录圆半径的变化，那么最后一次剩下的点，就是最大面积圆的圆心，其半径就是倒数第二次的半径。或者各点到多边形最短距离就是半径。不过由于圆在几何上是正n边形近似，此外半径连续增长也是有限次的，所以得到的结果不是精确结果，而是在一定容差范围的。