矩形重叠的数据结构

Question

我有一组在指定空间中的矩形，它们可能具有不同的尺寸和位置。

我需要检测碰撞集群，即相互交叉的矩形组，就像附图中所示，其中我有两个集群（在红色框内）。

一个简单的方法是使用这些矩形的向量，并使用双重for循环检查交集，例如：

for (size_t i = 0; i < rectangles.size(); i++) {
  for (size_t j = i + 1; j < rectangles.size(); j++) {
    if (rectangles.at(i).intersect(rectangles.at(j)) {
      // Add rectangle[j] to cluster in which rectangle[i] is
    }
  }

我认为这不是执行微积分的最有效方式。

如何高效地计算这些聚类？我读到了一些关于使用四叉树进行平面划分的内容，但我不知道如何在这种情况下使用它们。这是适当的数据结构还是有更有效的方法（我必须在软实时中处理）。

- Jepessen

---

http://en.wikipedia.org/wiki/Collision_detection - Pauli Nieminen

相关：https://dev59.com/qm025IYBdhLWcg3wpXse - Vaughn Cato

@VaughnCato，对于我的问题，R-Tree是正确的选择，你同意吗？还是我犯了错误？ - Jepessen

我的直觉是，使用扫描线算法会获得更好的性能。 - Vaughn Cato

可能你是对的。我会研究一下这些解决方案。谢谢你的帮助。 - Jepessen

Answer 1

如果情况允许，使用四叉树绝对是个不错的选择，但请确保你有足够的对象来创建和维护这个结构。除此之外，如果你只是使用矩形，那么一个简单的检查一个矩形的最大X值与另一个矩形的最小X值以及Y值是否相同就可以了。如果不是这样，而且你没有使用凹多边形，那么分离轴定理是一种很好的检测方法，甚至可以在推动它时扩展到3D。我真的很喜欢分离轴定理的一点是，如果需要，它还可以进行碰撞响应，因为它可以返回将形状移出彼此所需的最小向量。如果你卡住了，game-dev上的一些人会给你很多关于进一步碰撞检测和响应的指针。

- Yann

---

谢谢。我知道如何执行矩形碰撞，但我不知道为了最小化碰撞测试而使用什么最佳数据结构。我看到@VaughnCato告诉我要使用R树数据结构和分离轴定理，这样我应该能获得良好的性能。 - Jepessen

好的。请记住，如果您的对象不容易被矩形包围，分离轴定理只会在您获得更高的碰撞准确性方面更好。虽然它很有效率，但它不如简单的大于/小于检查快速。@Jepessen - Yann