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

Nicolas2050

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

如果是任意凸凹N边形呢？如何求其内部面积最大圆的圆心及其半径。

Ysu2008

算法大致如下：
多边形内部随机选择一点作为初始圆心，然后使半径不断扩大，同时作边界碰撞检测；在满足约束条件下半径不再扩大时停止。如此模拟数千次，多边形内部各个区域基本上都测试到，最后取最大圆及其圆心作为输出。

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

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

Nicolas2050

计算案例

uk702

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

2 再遍历另外五个角（包括两对边所形成的 2 个角）。