矩形重疊的數據結構

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上的某些人如果遇到困難，將會對進一步的碰撞檢測和響應提供大量指示。