3

我知道如何检查 X,Y 点是否是单个矩形区域，但是说我有多个可能重叠的区域（这些区域将具有 X,Y,Width,Height,Z-index （或 x1,y1,x2 ,y2 如果这更容易的话——我不关心我如何存储它，如果它是相关的）

是否有任何有效的算法来确定该点是否在其中一个区域内，而不必遍历每个区域。

当添加或删除一个区域时，我更喜欢不需要很长的重新计算时间的东西，但是这会比查找少。

谢谢！

4

2 回答 2

3

您可以将您的区域存储到四叉树（如果是 3D，则为八叉树）。这将帮助您在进入真正的碰撞测试之前拒绝大部分区域。

如果您有多个层，只需每层有一个四叉树，并根据您的点所在的层使用相关的四叉树。

于 2011-01-20T11:26:12.663 回答
1

体积kd树？

于 2011-01-20T11:19:36.707 回答