给定一个简单的多边形(不一定是凸面)和一条原点位于多边形内的射线,我想计算多边形中包含的最大圆,但要遵守以下约束:
- 圆心位于射线上的某处。
- 射线的原点在圆上。
是否有一种算法可以准确地计算出这一点?近似值呢?
最佳答案
设C为满足问题条件的圆的集合(即圆心在射线上,射线的原点在圆上)。
考虑多边形的一条边e。然后:
- C 中的圆圈均未触及 e。在这种情况下,r(e) = ∞。
- 有一个最小的圆 c ∈ C 与 e 相切(e 与 相切c,或者 e 的端点之一位于 c 上——您可以通过求解这些可能性来找到 c)。在这种情况下,r(e) 是 c 的半径。
然后你想要的答案是 min(r(e)).
更新 显然您没有计算C(此集合中有无限多个圆)。您要做的是找到接触每条边 e 的最小圆 c(如果存在这样的圆)。对于每条边 e,您计算 c 的三个候选边:一个与 e 相切,两个与 e< 的端点相切/em>,并选择最小的可行候选者。所以如果有 n 个边,你最多考虑 3n 个圆。
关于algorithm - 给定一条射线和多边形,计算多边形内的最大圆,圆心在射线上,端点在圆上,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36971164/