快速算法，如果一個長方形相交的矩形邊界

Question

想象一下，你有與它周圍的圍欄一碼，這可能是這樣的檢測：

______ ________ 
|  |_|  _| 
|    |_ 
|  _ ___| 
|__  |_| | 
    |   |__ 
___|  _  | 
|  | | |_ 
|________| |______| 

Don't ask why it's a weird shape, it's your yard, I didn't make it. 

..where，在中間的小盒子是有些武斷方形物體。如果物體朝任何方向朝向院子邊緣移動，那麼當物體與柵欄相撞時如何檢測？

如果你的院子數千倍大，並且有許多邊緣需要跟蹤，該怎麼辦？那麼你如何有效地解決這個問題呢？

Answer 1

查看院子裏的一個大矩形，上面有幾個「負面」正方形。

將這些負方格的位置存儲在quad tree中。

若要檢查碰撞，請探測與該物體相鄰的四個方格的樹。

檢測操作的時間複雜度取決於四叉樹變體的選擇，但您可以在負平方數中預期對數時間。