在任意有界形状内画指定半径的圆
哪些公司问过
答案要点
- 转化:圆完整落在形状内等价于圆心在内部且到边界最短距离不小于r
- 多边形:射线法判内部,逐边计算点到线段距离,取最小值与r比较
- 找圆心:网格采样检验,或求最大内切圆圆心;最大距离小于r则画不下
- 任意形状:栅格化后做距离变换,距离不小于r的像素都可作圆心
- 优化:包围盒预判宽高小于2r、空间索引加速最近边查询、GPU逐像素计算
易错点
- 只判断圆心在形状内,没检查到边界的距离
- 只检查边的端点距离,忽略点到线段内部的最近距离
- 找不到可行位置时没有给出提示
面试官常见追问
- 如果允许圆超出形状,只画形状内部部分怎么做?
- 点到线段的距离怎么算?
- 怎么精确求多边形的最大内切圆?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。