多边形的最大内圆问题

公子相

要在一块多边形钢板上画出一个最大的圆以供切割下料，如何确定这个圆的圆心和半径？
编程实现之。

aecupeemow

计算实例

akomosuse

正常情况圆至少和三条边相切，枚举和三条边相切又完全在图形内部的圆即可。
对于凹多边形的情况，还有特殊情况是经过k个顶点（凹进去的顶点）和3-k条边相切。全部枚举即可

渐行渐远

计算实例2

ugetetip

a = Point(0,-4)
b = Point(5.25,-3.1)
c = Point(4,0)
d = Point(7,2.55)
e = Point(4.25,3.6)
f = Point(4.55,7)
g = Point(0,4)
h = Point(-3.1,2.45)
i = Point(-0.45,0)

anaboewako

光给顶点没用啊，随便一些点，可以画出很多个多边形。除非你的点是按照依次相连顺序给的，你应该进行说明一下。

aqobuoeditom

有一個難點是，有的圓是既跟綫相切，又過凹頂點，所以邊數一多，枚舉法可能會很吃力。

BristSes

依次相连顺序给的

efaugko

依次相连，如果发生自相交怎么办？比如玫瑰花瓣形状的曲线，就是这种类型。如果不加入判断，算法很可能给出错误的结果。

eheotolee

计算案例2