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

Question

如何检查像下面蓝色圆形是否完全包含在其他圆（白色圆）的区域内，需要算法。对于蓝色圆形返回TRUE，对于红色圆形返回FALSE。

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

- oscarm

Answer 1

这是一个简单的解决方案：

• 收集所有圆并找到在或内部测试圆T上的所有交点。拆分相应的边并构建边图：

对于每条边，记录创建它的圆。

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

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

  • 如果在C内，则C覆盖了R。继续进行下一个区域。
  • 如果不在，则R未被C覆盖。循环遍历R的其他蓝色边缘。
  • 如果最后R仍然没有被覆盖，则T未完全覆盖-返回false。

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

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

---

特殊情况：

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

该算法非常低效，我不确定是否还有其他退化情况；如果有任何建议，请告诉我。

- user3235832

Answer 2

我认为没有简单的解决方案。

我会逐个处理每个圆，并对所有其他圆进行布尔减法。(远离圆-R0 + R1 < D12-不会干扰。)

在吃掉一些碎片之后，一个圆变成了由圆弧构成的曲线多边形，或者是一组这样的多边形，因为连通性可以被打破。一个多边形可以用贡献其轮廓弧的圆的列表来表示，弧的端点由两个相邻的邻居或目标圆和邻居的公共交点定义。请注意，同一邻居可能会出现多次。

为了使事情更加复杂，多边形可以有孔洞，您需要将其表示出来。

然后，一个关键的操作是从曲线多边形中减去一个圆。您需要检测完全位于新圆内部的弧以及跨越它的弧。在获取剩余弧的部分之后，您需要重新排列剩余的弧和新的弧。

我想所有这些操作都可以从一个原始操作中构建，该原始操作找到在圆盘内部的弧的部分(由三个圆定义)。

- user1196549

Answer 3

这似乎很简单（编辑：但实际上并不是）：如果给定圆的每个弧的每个点都包含在其他圆中的至少一个圆中，则整个圆被包含在内。然后，您需要找到所有交点（检测圆是否与同一平面中的任何其他圆相交的算法），并对由这些交点指定的所有弧进行检查。如果圆A的弧A1-A2的任何“内部”点都包含在与圆B的两个交点给定的圆B的圆中，则整个弧被包含在圆B中，反之亦然。如果我错了，请纠正我。

编辑：好的，我已经知道我错了，正如maxim1000所展示的那样。这比我想象的更加复杂。我考虑添加一些内容到我的答案中，但我不确定这是否是一个解决方案。我希望它能有所帮助。即：我考虑确定我们心中的圆与所有其他圆之间的总交叉面积。我们找出我们圆内的所有分离的交点 - 所有包括相同点的部分，由所有相交的弧线隔开 - 并找到它们的面积。然后将它们加起来。如果它等于我们圆的面积，则我们的圆包含在其他圆中。确定这个面积本身可能是一个问题，但正如我所说，它可能会引导我们走向正确的方向。让我也想想。

编辑：经过一段时间的思考，确定（多个）相交圆中的所有区域只是添加或减去三角形或...嗯...如何称呼它们？...像这里图片上的黄色部分 :)

- forestgril

---

考虑一个大圆，其边界完全被小圆覆盖。大圆的中心肯定不会被小圆覆盖。如果我正确理解问题，它是关于带有内部的圆的。 - maxim1000

没错。白色圆圈形成了一个区域，其他圆可能会重叠在该区域或部分区域上。这就是我需要检查的内容。 - oscarm

我正在尝试在我的回答中提出一些有用的东西。请稍后检查编辑。 - forestgril

它们是小的片段。 - user3235832

感谢提供这些小段落 :) - forestgril