测试点是否在某个矩形内

Question

我有一大堆大小相同的矩形。我正在生成一些随机点，这些点不能落在这些矩形里。所以我想做的是检查生成的点是否在某个矩形里，如果在的话，就生成一个新的点。

使用R树（R-trees）似乎可以解决这个问题，但它们主要是为矩形设计的，而不是为点设计的。我可以使用一种修改过的R树算法，让它也能处理点，但如果已经有更好的解决方案，我不想重新发明轮子。我对数据结构不太熟悉，所以也许已经有适合我这个问题的结构存在？

简单来说，我想问的是，是否有人知道一个好的算法，可以在Python中使用，用来检查一个点是否在给定的一组矩形中的任何一个矩形里。

补充说明：这是在二维空间中，矩形没有旋转。

Answer 1

我建议你看看BSP树（还有可能的四叉树或八叉树，那个页面上也有链接）。这些树结构用于把整个空间分割成小块，这样你就能快速找到需要检查的矩形。

最简单的情况就是你只有一个大块区域，这样就得检查所有的矩形；而最复杂的情况是，你把区域分得非常细，细到每个小块的大小和单个矩形差不多。当然，分得越细，你在树上查找时就需要走的步骤越多，才能找到你想检查的矩形。

不过，你可以自由决定哪些矩形适合用来检查某个点，然后创建相应的结构。

要注意重叠的矩形哦。因为BSP树需要提前计算，所以在这个过程中你可以把重叠的部分去掉，这样就能得到清晰的分区。

Answer 2

对于与坐标轴对齐的矩形，只需要两个点（四个数字）就能确定这个矩形的位置，通常是左下角和右上角的坐标。要判断一个点（X_test, Y_test）是否与一个矩形（X_BL, Y_BL, X_TR, Y_TR）重叠，可以通过以下两个条件来测试：

• X_test 大于等于 X_BL 并且 X_test 小于等于 X_TR
• Y_test 大于等于 Y_BL 并且 Y_test 小于等于 Y_TR

显然，如果要测试的点很多，这个过程可能会比较耗时。那么，问题就是如何优化这个测试过程。

一种明显的优化方法是确定一个包围所有矩形的最小和最大 X、Y 值（也叫边界框）：快速测试这个边界框可以判断是否有必要继续深入检查。

• X_test 大于等于 X_min 并且 X_test 小于等于 X_max
• Y_test 大于等于 Y_min 并且 Y_test 小于等于 Y_max

根据矩形覆盖的总面积，可能会找到一些不重叠的子区域，这些区域内包含矩形。这样，你就可以避免搜索那些不可能包含与点重叠的矩形的子区域，从而节省比较的时间，但这需要提前计算合适的数据结构。如果矩形的数量比较少，可能就没有重叠的情况，这样就变成了暴力搜索。同样，如果矩形的数量非常多，以至于在边界框内没有可以分割的子区域，那就会很麻烦。

不过，你也可以随意将边界区域分成四个部分（每个方向各一半）。然后你会用一个包含更多矩形的列表（对于每个与任意边界重叠的矩形，可能会有两个或四个矩形）。这样做的好处是，你可以从搜索中排除掉四个部分中的三个，从而减少总的搜索量，虽然这会增加存储空间的需求。

所以，空间和时间之间总是有权衡。而且，预计算和搜索之间也有权衡。如果运气不好，预计算可能没有任何效果（比如只有两个矩形，它们在任一轴上都不重叠）。但另一方面，预计算也可能带来显著的搜索时间收益。

Answer 3

这个Reddit讨论串解决了你的问题：

我有一组矩形，需要确定一个点是否在其中任何一个矩形内。有什么好的数据结构可以做到这一点，快速查找很重要吗？

如果你的数据是整数，或者你知道精度并且不太高，你可以使用abelsson在讨论中提到的建议，利用颜色来实现O(1)的查找：

像往常一样，你可以用空间换时间……这里有一个O(1)的查找，常数非常低。初始化：创建一个足够大的位图，能够包围所有矩形并具有足够的精度，初始化为黑色。将所有包含矩形的像素涂成白色。O(1)查找：点(x,y)是白色吗？如果是，说明碰到了一个矩形。

我建议你去那篇帖子，完整阅读ModernRonin的回答，这是最被接受的答案。我把它粘贴在这里：

首先，微观问题。你有一个任意旋转的矩形和一个点。这个点在矩形内吗？

有很多方法可以做到这一点。但我认为最好的方法是使用二维向量的叉积。首先，确保矩形的四个点按顺时针顺序存储。然后用1）矩形边的两个点形成的向量和2）从边的第一个点到测试点的向量做叉积。检查结果的符号——正数表示在边的右侧（即在矩形内），负数表示在外面。如果它在四条边的内部，那么它就在矩形内。或者说，如果它在任何一条边的外面，那么它就在矩形外面。这里有更多解释。

这种方法每条边需要进行3次减法，每条边有2个向量，加上每条边需要做一次叉积，这样就需要3次乘法和2次加法。每条边11次运算，每个矩形44次运算。

如果你不喜欢叉积，你可以尝试其他方法：找出每个矩形的内切圆和外接圆，检查点是否在内切圆内。如果在，那么它也在矩形内。如果不在，再检查它是否在外接矩形外。如果在外接圆外，那么它也在矩形外。如果它在两个圆之间，那就麻烦了，你得用更复杂的方法来检查。

在二维空间中，判断一个点是否在圆内需要进行两次减法和两次平方（即乘法），然后比较平方后的距离，以避免计算平方根。这是4次运算，两个圆就是8次运算——但有时候你仍然无法确定。此外，这假设你不需要花时间计算外接圆或内切圆，这可能取决于你愿意为矩形集做多少预处理。

无论如何，逐个测试每个矩形可能不是个好主意，特别是当你有一亿个矩形的时候。

这就引出了宏观问题。如何避免逐个测试每个矩形？在二维空间中，这可能是一个四叉树的问题。在三维空间中，generic_handle提到的就是八叉树。根据我的经验，我可能会把它实现为B+树。使用d=5是很有吸引力的，这样每个节点可以有最多4个子节点，因为这与四叉树的抽象非常匹配。但如果矩形集太大，无法放入主内存（现在不太可能），那么让节点的大小与磁盘块相同可能是更好的选择。

要注意一些烦人的特殊情况，比如某些数据集中有一万个几乎相同的矩形，它们的中心点完全相同。:P

这个问题为什么重要？它在计算机图形学中很有用，用来检查光线是否与多边形相交。也就是说，你刚刚开枪的狙击步枪是否击中了你瞄准的人？它也用于实时地图软件，比如GPS设备。GPS告诉你你所在的坐标，但地图软件必须在大量地图数据中找到这个点的位置，并且每秒要做好几次。

再次感谢ModernRonin……