多边形的最大内圆问题

markfang2050 · 发表于 2021-8-20 16:31:37

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

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

markfang2050 · 发表于 2021-8-20 17:30:56

计算实例

mathe · 发表于 2021-8-20 17:41:35

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

markfang2050 · 发表于 2021-8-21 17:43:14

计算实例2

markfang2050 · 发表于 2021-8-21 17:46:25

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)

kastin · 发表于 2021-9-22 22:11:36

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

ejsoon · 发表于 2021-9-22 22:42:16

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

markfang2050 · 发表于 2021-9-23 08:05:19

kastin 发表于 2021-9-22 22:11
光给顶点没用啊，随便一些点，可以画出很多个多边形。除非你的点是按照依次相连顺序给的，你应该进行说明一 ...

依次相连顺序给的

kastin · 发表于 2021-9-23 11:07:53

markfang2050 发表于 2021-9-23 08:05
依次相连顺序给的

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

markfang2050 · 发表于 2021-9-23 12:02:36

计算案例2

账号		自动登录	找回密码
密码			欢迎注册

[擂台] 多边形的最大内圆问题

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

点评

点评

点评