algorithm - 给定一条射线和多边形，计算多边形内的最大圆，圆心在射线上，端点在圆上

Question

给定一个简单的多边形(不一定是凸面)和一条原点位于多边形内的射线，我想计算多边形中包含的最大圆，但要遵守以下约束:

1. 圆心位于射线上的某处。
2. 射线的原点在圆上。

是否有一种算法可以准确地计算出这一点？近似值呢？

Answer 1

设C为满足问题条件的圆的集合(即圆心在射线上，射线的原点在圆上)。

考虑多边形的一条边e。然后:

1. C 中的圆圈均未触及 e。在这种情况下，r(e) = ∞。
2. 有一个最小的圆 c ∈ C 与 e 相切(e 与 相切c，或者 e 的端点之一位于 c 上——您可以通过求解这些可能性来找到 c)。在这种情况下，r(e) 是 c 的半径。

然后你想要的答案是 min(r(e)).

更新 显然您没有计算C(此集合中有无限多个圆)。您要做的是找到接触每条边 e 的最小圆 c(如果存在这样的圆)。对于每条边 e，您计算 c 的三个候选边:一个与 e 相切，两个与 e< 的端点相切/em>，并选择最小的可行候选者。所以如果有 n 个边，你最多考虑 3n 个圆。