如何求任意凸凹四边形其最大圆的圆心及其半径
本帖最后由 Nicolas2050 于 2021-9-15 07:35 编辑如果是一个任意凸凹四边形，已知4个顶点坐标，如何求其内部面积最大圆的圆心及其半径。
如果是任意凸凹N边形呢？如何求其内部面积最大圆的圆心及其半径。 算法大致如下：
多边形内部随机选择一点作为初始圆心，然后使半径不断扩大，同时作边界碰撞检测；在满足约束条件下半径不再扩大时停止。如此模拟数千次，多边形内部各个区域基本上都测试到，最后取最大圆及其圆心作为输出。
注意：初始化圆心简称初心，初心要随着边界碰撞约束而改变，不可固定。:P
先在规则多边形内模拟，然后移植到不规则多边形内。无非就是边界碰撞检测条件多一点而已。
模拟过程类似吹气球，就叫“吹气球算法”吧。:lol 计算案例
本帖最后由 uk702 于 2021-9-16 19:20 编辑
能否证明（直觉上），凸四边形的最大内嵌圆至少和其中的两条边相切？假若是，由此得出一个方法：
1a 任取一个角，作其角平分线，然后在角平分线上取点 P，求出 P 到四条边的距离，距离最小值就是以点P为中心的内嵌圆的最大半径。
b 移动（比如以 0.01 或 0.001 的步幅) 角平分线上的点 P，重复过程 a，直到点 P 移出凸四边形。
2 再遍历另外五个角（包括两对边所形成的 2 个角）。
页:
[1]