什么是确定点是否在任意数量的框中最有效的方法

Question

3

我知道如何检查一个X,Y点是否在单个矩形区域内，但是如果有多个可能重叠的区域（这些区域将具有X、Y、宽度、高度、Z索引（或x1、y1、x2、y2，如果更容易存储，我对存储方式不挑剔）），是否有有效的算法可以确定该点是否在其中一个区域内，而无需遍历每个区域。

我希望有一种不需要重新计算时间长的算法来添加或删除区域，但这种情况比查找要少见。

谢谢！

- Dre

这些矩形是否与x轴和y轴对齐？ - Bart Kiers

2个回答

1

- Gareth Rees

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Vincent Mimoun-Prat · Accepted Answer

你可以将区域存储到Quadtree（如果是3D，则为Octree）中。这将帮助您在进行真正的碰撞测试之前拒绝大多数区域。

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