此Reddit线程解决了您的问题：
我有一组矩形，需要确定其中是否包含一个点。有哪些好的数据结构可以做到这一点，而快速查找很重要？
如果您的Universe是整数，或者精度水平众所周知并且不太高，则可以使用线程使用abelsson的建议，并使用使用着色的O（1）查找：
像往常一样，您可以用空间来交换时间。.这是一个常数很低的O（1）查找。init：创建一个足够大的位图以包围所有矩形，并将其初始化为黑色。将所有包含任何矩形的像素着色为白色。O（1）查找：点（x，y）是白色的吗？如果是这样，则击中一个矩形。
我建议您转到该职位，并完整阅读ModernRonin的回答，这是最被接受的答案。我在这里粘贴：
首先，微观问题。您有一个任意旋转的矩形和一个点。该点在矩形内吗？
有很多方法可以做到这一点。但我认为最好的方法是使用2D矢量叉积。首先，确保矩形的点按顺时针顺序存储。然后对向量进行叉积运算：1）由侧面的两个点形成的向量，以及2）从侧面的第一个点到测试点的向量。检查结果的符号- 正极在侧面的内侧（右侧），负极在外侧。如果在所有四个边内，则在矩形内。或等效地，如果它在任何边的外部，则在矩形的外部。在这里更多的解释。
此方法将对每个向量进行3次减法*乘以每边2个向量，再加上每边1个叉积，即三个乘法和两个加法。每边11触发器，每矩形44触发器。
如果您不喜欢叉积，则可以执行以下操作：找出每个矩形的内切圆和外切圆，检查内切圆内的点。如果是这样，它也在矩形中。如果不是，请检查它是否在外接矩形之外。如果是这样，它也位于矩形之外。如果它落在两个圆圈之间，那么您会感到困惑，并且必须用困难的方式对其进行检查。
在2d中查找点是否在圆内需要两次减法和两次平方（=乘），然后比较距离的平方以避免避免求平方根。那是4次翻牌，乘以两个圈就是8次翻牌- 但有时您还是不知道。此外，这还假定您不花费任何cpu时间来计算外接圆或内切圆，这可能是正确的，也可能不是正确的，具体取决于您愿意在矩形集上进行多少次预计算。
无论如何，针对每个矩形测试该点可能不是一个好主意，尤其是如果您有一亿个矩形。
这将我们带入宏观问题。如何避免针对集合中的每个矩形测试点？在2D中，这可能是一个四叉树 问题。在3d中，generic_handle说的是-八叉树。在我头顶上方，我可能会将其实现为B +树。尝试使用d = 5，以便每个节点最多可以有4个子节点，因为这很好地映射到四叉树抽象上。但是，如果矩形的集合太大而无法放入主存储器中（目前不太可能），那么使节点具有与磁盘块相同大小的节点可能是可行的方法。
提防烦人的退化情况，例如某些数据集具有一万个几乎相同的矩形，且其中心在同一精确点。：P
为什么这个问题很重要？在计算机图形学中，检查射线是否与多边形相交很有用。就是说，您刚才射击的那支狙击步枪是否击中了要射击的人？它也用在实时地图软件中，例如GPS单位。GPS会告诉您您所处的坐标，但是地图软件必须找到大量地图数据中该点的位置，然后每秒执行几次。
同样，归功于ModernRonin …
602392714
清零编程群