这个 Reddit 线程解决了您的问题：
我有一组矩形，需要确定一个点是否包含在其中任何一个中。有哪些好的数据结构可以做到这一点，快速查找很重要？
如果您的宇宙是整数，或者精度水平众所周知并且不太高，则可以使用线程中的abelsson的建议，使用 O(1) 查找并使用着色：
像往常一样，您可以用空间换取时间。这是一个 O(1) 查找，常数非常低。init：创建一个足够大的位图，以足够的精度包围所有矩形，将其初始化为黑色。将包含任何矩形的所有像素着色为白色。O(1) 查找：点 (x,y) 是白色的吗？如果是这样，一个矩形被击中。
我建议您阅读该帖子并完整阅读ModernRonin的答案，这是最被接受的答案。我把它贴在这里：
一是微观问题。您有一个任意旋转的矩形和一个点。点在矩形内吗？
有很多方法可以做到这一点。但我认为最好的方法是使用 2d 矢量叉积。首先，确保矩形的点按顺时针顺序存储。然后与 1) 边的两个点形成的向量和 2) 从边的第一个点到测试点的向量进行向量叉积。检查结果的符号 - 正面在侧面（右侧），负面在外面。如果它在所有四个边内，则它在矩形内。或者等效地，如果它在任何边之外，它就在矩形之外。更多解释在这里。
这种方法每个向量需要 3 个减法 * 每边 2 个向量，再加上每边一个叉积，即三个乘法和两个加法。每边 11 次翻牌，每个矩形 44 次翻牌。
如果您不喜欢叉积，那么您可以执行以下操作：找出每个矩形的内接圆和外接圆，检查内接圆内的点。如果是这样，它也在矩形中。如果不是，请检查它是否在外接矩形之外。如果是这样，它也在矩形之外。如果它落在两个圈子之间，你就完蛋了，你必须仔细检查一下。
查找一个点是否在 2d 中的圆内需要两个减法和两个平方（= 乘），然后比较距离平方以避免必须做平方根。那是 4 次翻牌，乘以两个圈就是 8 次翻牌——但有时你仍然不知道。此外，这假设您不支付任何 CPU 时间来计算外接圆或内切圆，这可能会或可能不会正确，具体取决于您愿意对矩形集进行多少预计算。
无论如何，针对每个矩形测试该点可能不是一个好主意，尤其是当您拥有一亿个矩形时。
这给我们带来了宏观问题。如何避免针对集合中的每个矩形测试该点？在 2D 中，这可能是一个四叉树 问题。在 3d 中，generic_handle 所说的 - 八叉树。在我的脑海中，我可能会将它实现为B+ 树。使用 d = 5 很诱人，这样每个节点最多可以有 4 个子节点，因为这很好地映射到四叉树抽象。但是，如果矩形集太大而无法放入主内存（现在不太可能），那么让节点与磁盘块大小相同可能是要走的路。
注意恼人的退化情况，比如一些数据集有一万个几乎相同的矩形，中心在同一点。:P
为什么这个问题很重要？它在计算机图形学中很有用，可以检查光线是否与多边形相交。即，你刚刚射出的那支狙击步枪是否击中了你正在射击的人？它也用于实时地图软件，比如 GPS 单元。GPS 会告诉您您所在的坐标，但地图软件必须在大量地图数据中找到该点的位置，并且每秒执行几次。
再次感谢 ModernRonin ...
对于与轴对齐的矩形，您只需要两个点（四个数字）来识别矩形 - 通常是左下角和右上角。通过测试两者来确定给定点（X test， Y test ）是否与矩形（X BL，Y BL，X TR，Y TR）重叠：
显然，对于足够大的点集进行测试，这可能相当耗时。那么，问题是如何优化测试。
显然，一种优化是为围绕所有矩形的框（边界框）建立最小和最大 X 和 Y 值：对此进行快速测试表明是否需要进一步研究。
根据矩形覆盖的总表面积的多少，您可能能够找到包含矩形的非重叠子区域，然后您可以避免再次搜索那些不能包含与点重叠的矩形的子区域在搜索过程中以预先计算合适的数据结构为代价节省比较。如果矩形集足够稀疏，则可能没有重叠，在这种情况下，这会退化为蛮力搜索。同样，如果矩形集非常密集，以至于边界框中没有可以在不破坏矩形的情况下拆分的子范围。
但是，您也可以任意将边界区域分成四等份（每个方向一半）。然后，您将使用一个框列表，其中包含比原始集合更多的框（每个框与任意边界之一重叠的两个或四个框）。这样做的好处是，您可以从搜索中消除四个季度中的三个，从而减少总共要完成的搜索量 - 以辅助存储为代价。
因此，与以往一样，存在时空权衡。以及预计算与搜索的权衡。如果运气不好，预计算将一无所获（例如，只有两个框，它们在任一轴上都不重叠）。另一方面，它可以实现可观的搜索时间优势。
我建议您查看BSP 树（以及可能的四叉树或八叉树，该页面上也提供链接）。它们用于递归地划分整个空间，并允许您快速检查需要检查的矩形点。
至少您只有一个巨大的分区并且需要检查所有矩形，最多您的分区变得如此之小，以至于它们缩小到单个矩形的大小。当然，分区越细，您需要沿着树向下走的时间越长，才能找到要检查的矩形。
但是，您可以自由决定一个点适合检查多少个矩形，然后创建相应的结构。
不过要注意重叠的矩形。由于无论如何都需要预先计算 BSP 树，因此您不妨在此期间消除重叠，以便获得清晰的分区。
您的 R-tree 方法是我所知道的最好的方法（这是我会选择四叉树、B+ 树或 BSP 树的方法，因为在您的情况下构建 R-tree 似乎很方便）。警告：我不是专家，尽管我记得我大学四年级算法课上的一些事情！
为什么不试试这个。计算和内存似乎都很轻。
考虑所有矩形在空间基线上的投影。将该组行间隔表示为
{[Rl1, Rr1], [Rl2, Rr2],..., [Rln, Rrn]}, ordered by increasing left coordinates.
现在假设您的点是 (x, y)，在该集合的左侧开始搜索，直到到达包含点 x 的行间隔。
如果没有，您的点 (x,y) 在所有矩形之外。
如果有人这样做，比如 [Rlk, Rrk], ..., [Rlh, Rrh], (k <= h) 那么只需检查 y 是否在这些矩形的垂直范围内。
完毕。
祝你好运。
约翰·多纳