algorithm - 检测矩形是否与矩形边界相交的快速算法

Question

假设你有一个围着栅栏的院子，它可能看起来像这样:

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

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

..中间的那个小盒子是一些任意的方形物体。如果那个物体朝你院子边缘的任何方向移动，你会如何检测物体何时与你的栅栏相撞？

如果您的院子大几千倍并且有很多边需要跟踪怎么办？那么您将如何有效地解决这个问题？

Answer 1

把院子看成一个大矩形，其中删除了几个“负”方 block 。

将这些负方 block 的位置存储在 quad tree 中.

要检查是否发生碰撞，请在树中探测与对象相邻的四个方 block 。

检测操作的时间复杂度取决于四叉树变体的选择，但您可以预期负平方数的对数时间。