数学中国

 找回密码
 注册
搜索
热搜: 活动 交友 discuz
查看: 106|回复: 4

如何求任意凸凹四边形其最大圆的圆心及其半径

[复制链接]
发表于 2021-9-15 06:59 | 显示全部楼层 |阅读模式
本帖最后由 Nicolas2050 于 2021-9-15 07:35 编辑

如果是一个任意凸凹四边形,已知4个顶点坐标,如何求其内部面积最大圆的圆心及其半径。

如果是任意凸凹N边形呢?如何求其内部面积最大圆的圆心及其半径。
发表于 2021-9-15 21:45 | 显示全部楼层
算法大致如下:
多边形内部随机选择一点作为初始圆心,然后使半径不断扩大,同时作边界碰撞检测;在满足约束条件下半径不再扩大时停止。如此模拟数千次,多边形内部各个区域基本上都测试到,最后取最大圆及其圆心作为输出。

注意:初始化圆心简称初心,初心要随着边界碰撞约束而改变,不可固定。

先在规则多边形内模拟,然后移植到不规则多边形内。无非就是边界碰撞检测条件多一点而已。
模拟过程类似吹气球,就叫“吹气球算法”吧。
回复 支持 0 反对 1

使用道具 举报

 楼主| 发表于 2021-9-16 09:04 | 显示全部楼层
计算案例

本帖子中包含更多资源

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

x

点评

赞一下。  发表于 2021-9-16 11:20
回复 支持 反对

使用道具 举报

发表于 2021-9-16 17:31 | 显示全部楼层
本帖最后由 uk702 于 2021-9-16 19:20 编辑

能否证明(直觉上),凸四边形的最大内嵌圆至少和其中的两条边相切?假若是,由此得出一个方法:
1a 任取一个角,作其角平分线,然后在角平分线上取点 P,求出 P 到四条边的距离,距离最小值就是以点P为中心的内嵌圆的最大半径。
b 移动(比如以 0.01 或 0.001 的步幅) 角平分线上的点 P,重复过程 a,直到点 P 移出凸四边形。

2 再遍历另外五个角(包括两对边所形成的 2 个角)。
回复 支持 反对

使用道具 举报

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

本版积分规则

Archiver|手机版|小黑屋|数学中国 ( 京ICP备05040119号 )

GMT+8, 2021-9-22 15:27 , Processed in 0.093750 second(s), 17 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

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