公子相 发表于 2024-4-15 14:34:48

多边形的最大内圆问题

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

aecupeemow 发表于 2024-4-15 14:35:14

计算实例

https://bbs.emath.ac.cn/data/attachment/forum/202108/20/173050jwf4uoeenk4iooik.png

akomosuse 发表于 2024-4-15 14:35:26

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

渐行渐远 发表于 2024-4-15 14:35:46

计算实例2
https://bbs.emath.ac.cn/data/attachment/forum/202108/21/174302z7p0lvfzx48k0x9z.png

ugetetip 发表于 2024-4-15 14:36:33

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 发表于 2024-4-15 14:37:11

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

aqobuoeditom 发表于 2024-4-15 14:37:28

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

BristSes 发表于 2024-4-15 14:37:51

依次相连顺序给的

efaugko 发表于 2024-4-15 14:38:50

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

eheotolee 发表于 2024-4-15 14:39:32

计算案例2
https://bbs.emath.ac.cn/data/attachment/forum/202109/23/120227ljjzji7mnz6mhja1.jpg
https://bbs.emath.ac.cn/data/attachment/forum/202109/23/120228e9rop0tti1optfp1.jpg
https://bbs.emath.ac.cn/data/attachment/forum/202109/23/120228mtddwtxlgw0082ri.jpg
https://bbs.emath.ac.cn/data/attachment/forum/202109/23/120228g539o0j1351hh233.jpg
https://bbs.emath.ac.cn/data/attachment/forum/202109/23/120228li8yc399c3s8w9ne.jpg
页: [1]
查看完整版本: 多边形的最大内圆问题