找到重叠的圆形

Question

我有一个矩形区域，其中有等半径的圆。我想找出哪些圆与其他圆重叠（输出是重叠圆的2元素集合列表）。

我知道如何检查两个圆是否重叠（它们中心之间的距离小于直径）。我可以对每对圆执行此检查，但我想知道是否有更好的算法（比O(n^2)更快）。

编辑

圆的数量通常约为100，重叠不会经常发生。

这是一些上下文：矩形是游戏中的战场。单位的移动是在小步骤中完成的，我正在尝试检测单位之间的碰撞。

- martinkunev

---

不错的问题。 :) 在我看来，你可以使用某种扫描线算法。 - blazs

嗯……所有的圆都可以与其他圆重叠。对我来说，这意味着在最坏情况下，你最好的时间复杂度不能超过 O(n^2)——虽然可能有一些启发式方法可以进行优化。 - Gordon Linoff

我认为应该有一种输出敏感算法，即运行时间与重叠数量（和圆的数量）成正比；这在某种程度上与线段交问题相关。 - blazs

你的问题不够精确。期望的输出是什么？n个圆可以形成一个链，其中任何一个圆都与恰好两个其他圆重叠。在这种情况下，输出将是什么？ - fjardon

n通常大约是100。 - martinkunev

Answer 1

对于一个简单的解决方案，将中心点插入到2d树中，并使用查询半径2R在每个中心点周围执行圆形范围查询。在良好的条件下，这可以是O（N Log（N））。

---

或者，只需按X对中心进行排序，依次尝试所有圆：通过二分搜索，定位横坐标Xc并扫描到Xc-2R和Xc+2R，然后检查2D距离。

二分搜索的成本为O（N Log（N））。如果圆均匀分布在边长为S的正方形中，则宽度为4R的条带包含4RN/S个圆，因此总比较成本为4RN²/S。如果S很大，则这是良好的性能（考虑在正方形中紧密排列N个圆，S〜2R√N，因此有2N√N个比较）。

- user1196549

---

考虑到N的值很小，不确定这个算法能否打败穷举搜索 :( - user1196549

Answer 2

直接回答：通常情况下，你无法得到比O(n^2)更好的结果，因为圆形有可能全部重叠，所以你必须生成n^2个答案。

如果你更具体一些，可能会得到更好的答案。例如，如果你真正想做的是在2D模拟中找到边界球，你可以从实体在帧之间只移动了一定距离这一事实中获益，如果圆形稀疏则与紧密包装时不同，等等。因此，请告诉我们更多关于它的信息。

编辑：你编辑了你的问题 - 你确实正在寻找2D模拟中的碰撞检测。如果你查看https://en.wikipedia.org/wiki/Collision_detection，他们指出了几种算法，恰好适用于你的情况。

我喜欢那个页面上详细介绍的方法，在该页面上，您只需要为每个轴保留一个边界间隔列表（在“2D”中为2个），并且仅需要在这些边界间隔（它们本身按定义是一维的）更改时才需要“努力工作”（即，它们的“重叠状态”）。这消除了对于表现良好的情况下的 O(n²)。他们没有给出其复杂度的估计，但由于基本上归结为排序，因此在我的看来更或多或少是 O(n logn)，而当帧之间只有最小的变化时则更少。

- AnoE

---

O(N²)，在最坏情况下确实是不可避免的，但很可能过于悲观了。 - user1196549

是的，我之前的意图就是指出这一点- 如果楼主提供更具体的信息，我们可以考虑其他解决方案。实际上，他确实提供了更多信息，所以我会编辑回答。:) - AnoE

Answer 3

鉴于问题陈述的新解释，我建议采用不同的方法。

在战场上覆盖一个正方形网格，网格步长等于一个圆直径。每个圆最多可以重叠四个单元格。在每个单元格中，保留重叠圆的列表（并在每次移动时更新）。

现在检测潜在碰撞将需要每个圆约四个单元格/圆测试，即接近线性时间。

- user1196549