形状拖动问题

Question

我需要设计一个软件，用户可以在窗口中拖动形状。问题在于可能有成千上万的形状，并且可能存在一些限制，例如，一个形状不能超过另一个形状。

所以我实际上需要知道如何组织数据存储和一些算法来快速确定一个形状是否可以放置在某个特定位置。 我认为这个问题已经解决了很多次，但我不知道如何正确地谷歌它。你能否给我提供一些关于这个话题的信息？ 谢谢！

Answer 1

四叉树（2D，八叉树，如果3D）经常用于碰撞检测。想法是递归地将空间分成正方形/立方体，并将这些形状放置到正确的正方形/立方体中。当您需要在给定的形状上执行碰撞检测时，您只能测试相同方块/立方体中的形状。

还有其他的结构，每个结构都有优点/缺点取决于你的限制。如果其他形状是静态的，BSP树也可以是一个好的结构。