用于检查圆是否完全包含在其他圆的区域中的算法

Question

检查下面的蓝色圆圈是否完全包含在其他圆圈(圆圈)中的算法是什么.我希望蓝圈为TRUE,红圈为FALSE

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

Answer 1

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

• 取出所有圆，找到测试圆 T上或内部的所有交点。分割相应的边并构建边图：

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

• 使用最小循环算法查找圆内的所有非重叠区域（在边/顶点列表中查找所有非重叠多边形）。

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

  • 如果是，则 C 覆盖 R。继续进入下一个区域。
  • 如果不是，则 R 不会被 C 覆盖。在限制 R 的其他蓝色边缘上循环。
  • 如果最后 R仍未被覆盖，则 T 未被完全覆盖 - 返回false。

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

• 如果您在此阶段尚未返回，则返回true。

边例：

• 如果某个圆包含T，则忽略它。
• 如果 T 包含it，则通过将其存储在列表中来推迟相交测试。最后重做测试并分割其边缘。

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