数学研发论坛

 找回密码
 欢迎注册
查看: 737|回复: 19

[讨论] 凸多边形内最大内接矩形

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

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

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

x
采用何种算法可求出任意凸多边形内的最大内接矩形?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-8-12 09:10:38 | 显示全部楼层
GJK算法是一种。碰撞检测。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-8-12 09:45:26 | 显示全部楼层
最大矩形是需要定义的,面积还是周长最大?

点评

NO  发表于 2021-10-24 08:23
不知我的理解是否正確  发表于 2021-10-23 01:38
也就是說,要找到周長最長的矩形是幾乎找不到的,因為它會無限逼近一條最長的直綫。  发表于 2021-10-23 01:37
經過思考,越狹長的矩形周長越大而面積越小。因此是存在的。  发表于 2021-10-23 00:22
是否存在兩個矩形,A比B周長大,B比A面積大?  发表于 2021-10-23 00:18
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-8-12 12:32:28 | 显示全部楼层
mathe 发表于 2021-8-12 09:45
最大矩形是需要定义的,面积还是周长最大?


面积最大。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-8-13 20:12:21 | 显示全部楼层
Finding the largest area rectangle of arbitrary orientation in  a closed contour.Written by Rubén Molano, Pablo G. Rodriguez,    Andres Caro, M. Luisa Duran.
这篇文章有开源代码实现,希望能帮到你。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-8-13 20:13:38 | 显示全部楼层
References

[1]  H. Alt, D. Hsu, and J. Snoeyink. Computing the largest inscribed isothetic rectangle. In Proc. 7th Canadian Conf. Comput. Geom., Universit'e Laval, Qu'ebec, August 1995, pp. 67--72.http://citeseer.nj.nec.com/alt94computing.html

[2]  D. Kirkpatrick and J. Snoeyink, Tentative prune-and-search for computing fixed-points with applications to geometric computation, Fundamental Informatic, 22 (1995), 353--370.http://citeseer.nj.nec.com/319045.html

[3]  K. Daniels, V. Milenkovic, and D. Roth. Finding the largest area axis-parallel rectangle in a polygon. Computational Geometry: Theory and Applications, 7:125--148, 1997.http://citeseer.nj.nec.com/daniels97finding.html

[4]  N. Amenta. - Bounded boxes, Hausdorff distance, and a new proof of an interesting Helly-type theorem. Proceedings of the 10th Annual ACM Symposium on Computational Geometry (1994) pages 340-347.  http://www.cs.utexas.edu/users/amenta/pubs/meatloaf.ps.gz
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-8-20 16:29:37 | 显示全部楼层
工件加工时,为充分利用任意多边形金属材料,想把工件加工成一个最大的圆,这些情况下如何确定这个圆的圆心和半径,使得这个内圆面积最大?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-8-23 18:33:54 | 显示全部楼层
Algorithms:The PSO algorithm employs a swarm of particles, which traverse a multidimensional search space to seek out optima.

Each particle is a potential solution and is influenced by experiences of its neighbors as well as itself.




pso

pso

点评

禁忌搜索算法也做了对比。  发表于 2021-8-23 18:39
PSO算法解决了任意多边形内最大面积矩形问题。程序语言:python3.7.  发表于 2021-8-23 18:35
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2021-8-25 12:28:23 | 显示全部楼层
markfang2050 发表于 2021-8-23 18:33
Algorithms:The PSO algorithm employs a swarm of particles, which traverse a multidimensional search  ...

具体算法思路是?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-10-21 19:26:19 | 显示全部楼层
markfang2050 发表于 2021-8-13 20:12
Finding the largest area rectangle of arbitrary orientation in  a closed contour.Written by Rube&#76 ...

麻烦问一下代码怎么找到啊?找了好久了,万分感谢

点评

代码自己写的。  发表于 2021-10-22 13:04
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2021-11-29 10:49 , Processed in 0.055241 second(s), 20 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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