如何判断点是否在矩形区域内？含百万级点四叉树实现及少量点解法

一、少量点的高效判断方法 #

直接逐个验证是最直接高效的方式，无需额外预处理：

• 对每个点(x,y)，只需满足两个条件即可判定在目标矩形内：
  1. x1 ≤ x ≤ x2（目标矩形左边界到右边界的x范围）
  2. y2 ≤ y ≤ y1（因矩形左上角y值大于右下角，需匹配这个y轴范围）
• 这种方法逻辑简单，点数量少（比如数千以内）时几乎无性能损耗，完全没必要用复杂数据结构。

二、四叉树处理200万数据点的方案 #

1. 四叉树的存储逻辑 #

核心是递归划分空间来归类点：

• 根节点：先遍历所有200万个点，找到全局最小/最大x、y值，以此确定根节点覆盖的整个空间范围。
• 节点分裂规则：当一个节点内的点数量超过设定阈值（比如50-200，可根据实际场景调整），就将当前节点的矩形平均拆分为左上、右上、左下、右下四个子区域，把节点内的点分配到对应的子节点中。
• 叶子节点：存储落在该节点区域内的所有点，不再继续分裂。
• 空的子节点无需存储，节省内存空间。

2. 四叉树的查询流程 #

查询目标矩形(x1,y1)-(x2,y2)时，按以下逻辑递归遍历：

• 若当前节点区域与查询矩形完全不重叠：直接跳过该节点。
• 若当前节点是叶子节点：遍历节点内所有点，判断是否在查询矩形内，符合条件的加入结果集。
• 若当前节点区域完全包含在查询矩形内：将节点内所有点直接加入结果集。
• 若当前节点区域与查询矩形部分重叠：递归遍历该节点的四个子节点，重复上述判断逻辑。

3. 实用优化点 #

• 预处理时先对所有点去重，减少存储和查询的数据量。
• 分裂阈值不宜过小（避免树层级过多导致递归开销大），也不宜过大（避免叶子节点内点过多，遍历耗时增加）。
• 用数组而非对象存储节点数据，降低内存开销，提升遍历速度。

三、200万点的替代方案 #

如果不想实现四叉树，排序+二分查找的实现成本更低：

• 先将所有点按x坐标排序，查询时通过二分查找快速定位x在[x1,x2]范围内的点集合，再遍历这些点验证y是否在[y2,y1]范围内。
• 这种方法实现简单，单次查询效率可观，适合查询频率不是极高的场景。

内容的提问来源于stack exchange，提问作者sweet_summer_child