数学研发论坛

 找回密码
 欢迎注册
查看: 963|回复: 23

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

[复制链接]
发表于 2021-8-20 16:31:37 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
要在一块多边形钢板上画出一个最大的圆以供切割下料,如何确定这个圆的圆心和半径?
编程实现之。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-8-20 17:30:56 | 显示全部楼层
计算实例
QQ图片20210820172859.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
回复

使用道具 举报

发表于 2021-8-20 17:41:35 | 显示全部楼层
正常情况圆至少和三条边相切,枚举和三条边相切又完全在图形内部的圆即可。
对于凹多边形的情况,还有特殊情况是经过k个顶点(凹进去的顶点)和3-k条边相切。全部枚举即可
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-8-21 17:43:14 | 显示全部楼层
计算实例2

results

results
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
回复

使用道具 举报

 楼主| 发表于 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)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-9-22 22:11:36 | 显示全部楼层
光给顶点没用啊,随便一些点,可以画出很多个多边形。除非你的点是按照依次相连顺序给的,你应该进行说明一下。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-9-22 22:42:16 | 显示全部楼层
有一個難點是,有的圓是既跟綫相切,又過凹頂點,所以邊數一多,枚舉法可能會很吃力。

点评

枚举是三次幂增长率,对于边数比较少的情况可以用一用,边数多了效率是低了。  发表于 2021-9-23 11:05
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-9-23 08:05:19 | 显示全部楼层
kastin 发表于 2021-9-22 22:11
光给顶点没用啊,随便一些点,可以画出很多个多边形。除非你的点是按照依次相连顺序给的,你应该进行说明一 ...

依次相连顺序给的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-9-23 11:07:53 | 显示全部楼层

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

点评

这个利用圆来生成凸凹多边形顶点,不会自交。  发表于 2021-9-23 11:58
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-9-23 12:02:36 | 显示全部楼层
计算案例2
test10.jpg
test9.jpg
test3.jpg
test2.jpg
test1.jpg

点评

这些多边形是利用圆来生成的吗?什么原理?  发表于 2021-9-23 21:33
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2022-5-16 12:42 , Processed in 0.146488 second(s), 20 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表