geometry - 检查一个圆是否完全包含在其他圆的区域中的算法

Question

检查像下面的蓝色圆圈这样的圆圈是否完全包含在其他圆圈(while 圆圈)的区域中的算法是什么。我想要蓝色圆圈的 TRUE 和红色圆圈的 FALSE

所有圆的输入是它们的坐标和半径。

Answer 1

这是一个粗略的解决方案:

取所有圆并找到测试圆 T 上或内部的所有交点。拆分相应的边并构建边图:

对于每个边缘，跟踪创建它的圆。

使用最小循环算法 (Find all non-overlapping polygons in a list of edges/vertices) 查找圆内的所有非重叠区域。

对于您找到的每个区域 R 的每个边界 E，取 E 所属的圆 C。如果 C 不是 T(红色) - 即 E 是蓝色，请检查 R 其他边缘上的点是否在 C 内:

如果它们是，则 C 覆盖 R。继续到下一个区域。

如果不是，则 R 没有被 C 覆盖。循环环绕 R 的其他蓝色边缘。

如果最后 R 仍未被覆盖，则 T 未被完全覆盖 - 返回 假 .

在上图中，C 包含 B，因此 R 被覆盖；但C不包含A，所以不覆盖S

如果您在此阶段尚未返回，请返回 真实 .

侧面案例:

如果某个圆圈包含 T，则忽略它。

如果 T 包含它，则通过将其存储在列表中来推迟交叉测试。最后重做测试并分割它的边缘。

这个算法效率很低，我不能 100% 确定是否还有退化的情况；如果有人有任何建议，请告诉我。