测试点是否在某个矩形内

Question

我有一组大小相同的矩形，现在我正在生成随机点，这些随机点不应该落在这些矩形中，因此我希望测试生成的点是否在其中一个矩形内，如果是，则生成一个新的点。

使用R树似乎可以解决问题，但它们实际上是针对矩形而非点。我可以使用修改过的R树算法来处理点的情况，但如果已经存在更好的解决方案，我宁愿不重复发明轮子。我对数据结构不太熟悉，也许已经存在适用于我的问题的某种结构？

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

编辑：这是在二维平面上进行的，并且矩形没有旋转。

- pafcu

---

你的矩形边缘是与坐标轴对齐，还是以任意角度朝向坐标轴？ - Jonathan Leffler

它们都对齐了，没有旋转或任何花哨的东西。 - pafcu

这些矩形有重叠吗？ - jk.

是的，矩形重叠是完全可能的。 - pafcu

Answer 1

这个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...

- Roee Adler

---

我很难想象ModernRonin的“向量积”方法如何比简单地检查min_x <= x <= max_x和min_y <= y <= max_y更快... 我对四叉树方法也不确定，因为它们主要用于存储点，而不是矩形... - Eric O. Lebigot

向量积允许任意方向的矩形；当所有矩形都与某个坐标系的轴对齐时，我相信其他方法更为合适。 - musicinmybrain

此外，向量积方法可以让我们检查一个点是否在任何四边形内部，无论它是否为矩形。 - David Sanders

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 根据矩形覆盖的总表面积，您可以找到包含矩形的非重叠子区域，并且您可以避免搜索那些不能包含重叠点的子区域，从而在搜索期间节省比较的时间，但需要预先计算合适的数据结构。如果矩形集足够稀疏，则可能不存在重叠，此时这将退化为蛮力搜索。同样，如果矩形集过于密集，而没有子范围可以分割而不会破坏矩形，则无法进行划分。

但是，您还可以任意地将边界区域分成四个部分（每个方向半个）。然后，您将使用包含更多框的框列表（每个与任意边界之一重叠的框的两个或四个框）。其优点是，您可以消除搜索中的四分之三的部分，从而减少要完成的搜索量，但代价是辅助存储。

因此，像往常一样，存在空间和时间的权衡。以及预计算与搜索之间的权衡。如果您运气不好，预计算什么也没做（例如，只有两个框，它们在任何轴上都不重叠）。另一方面，它可能会带来相当大的搜索时间优势。

- Jonathan Leffler

Answer 3

为什么不试试这个。它似乎在计算和内存方面都比较轻量级。

考虑将所有矩形投影到空间底线上的情况。将该线段集合表示为

 {[Rl1, Rr1], [Rl2, Rr2],..., [Rln, Rrn]}, ordered by increasing left coordinates. 

现在假设你的点是（x，y），从这个集合的左边开始搜索，直到找到包含点x的线段间隔。

如果没有找到，则表明你的点（x，y）在所有矩形的外面。

如果找到一些线段间隔，例如[Rlk，Rrk]，...，[Rlh，Rrh]（k <= h），那么只需检查y是否位于这些矩形的垂直范围内即可。

搞定了。

祝你好运。

John Doner

- John R Doner

Answer 4

我建议你看一下BSP树（还有可能是四叉树或八叉树，该页面上也提供了链接）。它们用于递归地划分整个空间，并允许您快速检查一个点需要检查哪些矩形。

最少你只有一个巨大的分区需要检查所有矩形，最多你的分区变得如此之小，以至于它们缩小到单个矩形的大小。当然，分区越细粒度，您需要沿着树向下走更长时间才能找到要检查的矩形。

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

注意重叠的矩形。由于BSP树必须预先计算，因此您可以在此期间删除重叠，以便获得清晰的分区。

- Frank

Answer 5

你的R树算法是我所知道的最好的算法（在这种情况下，我会选择R树而不是四叉树、B+树或BSP树，因为R树在你的情况下似乎更方便构建）。但要注意：虽然我还记得一些来自我的大学算法课程的东西，但我并不是专家！

- Eric O. Lebigot