矩形重叠的数据结构

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 
    } 
    } 

我不认为这是为了执行结石最有效的方法。

如何有效计算这些簇？我已经阅读了有关使用四叉树的平面分区的一些内容，但我不知道在这种情况下如何使用它们。这是合适的数据结构还是更有效的方法（我必须在软实时处理它）。

Answer 1

如果情况允许的情况下，使用quad tree是肯定是一个良好的通话，但请确保您有结构值得的创建和维护的开销足够的对象。

除此之外，如果您只是使用矩形，则可以简单检查一个矩形的最大X值与另一个的最小X值以及Y的相同。如果没有，并且您没有使用凹面物体，那么separating axis theorem是一种很好的检测方法，如果足够的话，它甚至可以拉伸3d。我非常喜欢关于分离轴定理的一件事，那就是如果你需要它也会碰撞响应，因为它可以返回最小向量来移动形状。

game-dev上的某些人如果遇到困难，将会对进一步的碰撞检测和响应提供大量指示。