测试点是否在某个矩形中

Question

我有一个很大的矩形集合，大小都一样。我正在生成不应该落在这些矩形中的随机点，所以我希望做的是测试生成的点是否位于其中一个矩形中，如果是，则生成一个新点。

使用R树似乎是可行的，但它们实际上是针对矩形而不是点。我可以使用R-tree算法的修改版本，它也适用于点，但如果已经有更好的解决方案，我宁愿不重新发明轮子。我对数据结构不是很熟悉，所以可能已经有一些结构可以解决我的问题了？

总而言之，基本上我想问的是，有没有人知道一个好的算法，在Python中有效，可以用来检查一个点是否位于给定矩形集中的任何矩形中。

编辑:这是二维的，矩形不旋转。

Answer 1

这个Reddit线程解决了你的问题：

I have a set of rectangles, and need to determine whether a point is contained within any of them. What are some good data structures to do this, with fast lookup being important?

如果您的领域是整数，或者如果精度级别是众所周知的，并且不是太高，您可以在线程中使用abelsson的建议，使用O(1)查找并使用着色：

和往常一样，你可以用空间来换取时间。这是一个常量非常小的O(1)查找。初始化:创建一个足够大的位图，以足够的精度包围所有的矩形，将其初始化为黑色。将所有包含任何矩形的像素涂成白色。O(1)查找：(x，y)点是白色的吗？如果是这样，则命中了一个矩形。

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

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

有很多方法可以做到这一点。但我认为，最好的方法是使用二维矢量叉积。首先，确保矩形的点按顺时针顺序存储。然后用1)边的两个点形成的矢量和2)边的第一个点到测试点的矢量来做矢量叉积。检查结果的符号--正的在(右边)，负的在外面。如果它位于所有四个边的内部，则它位于矩形内部。或者等价地，如果它在任何边的外面，它就在矩形之外。More explanation here。

此方法将采用每个向量3减法*乘以每边2个向量，再加上每边一个叉积，即三次乘法和两次加法。每边11个flops，每个矩形44个flops。

如果你不喜欢叉积，那么你可以这样做:计算出每个矩形的内接圆和外接圆，检查内接圆内的点是否存在。如果是这样的话，它也在矩形中。如果不是，请检查它是否在外接矩形之外。如果是这样的话，它也在矩形之外。如果它落在两个圆圈之间，你就是f*d，你必须用很难的方式来检查它。

在2d中查找一个点是否在圆内需要两个减法和两个平方(=乘法)，然后比较距离的平方，以避免必须计算平方根。这是4个flops，乘以两个圆圈是8个flops -但有时你仍然不会知道。此外，这还假设您不花费任何CPU时间来计算外接圆或内接圆，这可能是真的也可能不是真的，这取决于您愿意在矩形集上进行多少预计算。

在任何情况下，针对每个矩形测试点可能都不是一个好主意，特别是当您有上亿个矩形的时候。

这就引出了宏观问题。如何避免在集合中的每个矩形上测试点？在2D中，这可能是一个quad-tree问题。在3d中，generic_handle所说的是一个八叉树。不经意间，我可能会把它实现为一个B+ tree。我们很容易使用d= 5，这样每个节点最多可以有4个子节点，因为这很好地映射到了四叉树抽象上。但是，如果矩形集太大而不能放入主内存中(现在不太可能)，那么让节点的大小与磁盘块相同可能是可行的。

注意恼人的退化情况，比如有些数据集有一万个几乎相同的矩形，中心在同一个点上。:P

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

再次归功于ModernRonin..。

Answer 2

我建议你看看BSP trees (以及可能的四叉树或八叉树，也可以在该页面上找到链接)。它们用于递归地划分整个空间，并允许您快速检查需要检查哪些矩形的点。

最少你只有一个巨大的分区，并且需要检查所有的矩形，最大限度地，你的分区变得如此之小，以至于它们只有单个矩形的大小。当然，分区的粒度越细，为了找到要检查的矩形，您需要沿着树走的时间就越长。

但是，您可以自由地决定有多少个矩形适合用于检查点，然后创建相应的结构。

不过，要注意重叠的矩形。因为BSP树无论如何都需要预先计算，所以你也可以在这段时间内移除重叠，这样你就可以得到清晰的分区。

Answer 3

您的R树方法是我所知道的最好的方法(这是我会选择的方法，而不是四叉树、B+树或BSP树，因为在您的情况下构建R树似乎很方便)。警告:我不是专家，即使我记得我大学四年级的算法课上的一些东西！