我需要设计一个软件，用户可以在窗口中拖动形状。问题是可能有数千种形状，并且可能存在一些限制，例如一个形状不能位于另一个形状之上。
所以我实际上需要知道如何组织数据存储和一些算法来快速确定形状是否可以放置在某个特定位置。 我认为这个问题已经解决了很多次，但我不知道如何正确谷歌它。您能为我提供一些有关该主题的信息吗？ 谢谢!
最佳答案
四叉树(2D，如果是 3D，则为八叉树)通常用于碰撞检测。想法是递归地将空间划分为正方形/立方体，并将形状放入正确的正方形/立方体中。当您需要对给定形状执行碰撞检测时，您可以仅测试同一正方形/立方体中的形状。
还有其他结构，每种结构都有优缺点，具体取决于您所面临的限制。如果其他形状是静态的，BSP树也可以是一个很好的结构。
关于algorithm - 形状拖动问题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4408026/