这个Reddit帖子解决了你的问题:
我有一组矩形,需要确定一个点是否包含在其中任何一个矩形中。使用哪些数据结构可以快速查找?
如果你的宇宙是整数,或者精度水平已知且不太高,你可以使用abelsson在帖子中的建议,使用O(1)的颜色查找:
通常情况下,你可以用空间换时间...这里有一个O(1)查找,非常低的常数。初始化:创建一个足够大以包围所有矩形并具有足够精度的位图,并将其初始化为黑色。将包含任何矩形的像素点都涂成白色。O(1)查找:点(x,y)是否为白色?如果是,那么就击中了一个矩形。
我建议您前往该帖子并完整阅读ModernRonin的答案,这是最被接受的答案。我在此粘贴:
首先是微观问题。你有一个任意旋转的矩形和一个点,这个点在矩形内吗?有很多方法可以解决这个问题。但我认为最好的方法是使用二维向量叉积。首先确保矩形的顶点按顺时针顺序存储。然后用1)由两个边的点形成的向量和2)从第一个点到测试点的向量进行向量叉积。检查结果的符号——正数是内部(在侧面右侧),负数是外部。如果所有四条边都在内部,则在矩形内。或者等效地,如果在任何一条边之外,则在矩形之外。
这里有更详细的解释。这种方法每个向量需要3次减法* 2个向量,加上每个边的一个叉积,即三次乘法和两次加法。每个边需要11个FLOP,每个矩形需要44个FLOP。
如果你不喜欢叉积,那么你可以做一些类似的事情:找出每个矩形的内切圆和外接圆,检查点是否在内切圆内。如果是,它也在矩形中。如果不是,请检查它是否在外接矩形之外。如果是,它也在矩形之外。如果它落在两个圆之间,你就完了,必须用艰难的方式检查它。
在2D中,找出点是否在集合中的每个矩形中可能不是一个好主意,特别是如果你有一亿个矩形。这就带我们到了宏观问题。如何避免测试点对集合中的每个矩形进行测试?在2D中,这可能是一个
quad-tree问题。在3D中,根据generic_handle所说,是一个八叉树。我会将其实现为
B+ tree。很诱人地使用d = 5,这样每个节点最多可以有4个孩子,因为这映射得非常好。但是,如果矩形集太大而无法适应主存储器(这些天不太可能),那么具有与磁盘块相同大小的节点可能是正确的方法。要注意令人讨厌的退化情况,比如某个数据集有一万个几乎相同的矩形,它们的中心在完全相同的点上。
为什么这个问题很重要?它在计算机图形学中很有用,用于检查光线是否与多边形相交。即,你刚刚开枪打死的人是你要打的人吗?它还用于实时地图软件,比如GPS单位。GPS告诉你你所在的坐标,但地图软件必须在大量的地图数据中找到那个点,并且每秒钟执行多次。
再次感谢ModernRonin...