1. 概述
本文将深入探讨在二维空间中进行邻近点搜索的核心思想，并通过 Java 实现一个高效的 QuadTree（四叉树） 数据结构来解决这类问题。
这类需求在地图服务、游戏开发、图像处理等场景中非常常见——比如“找出我周围 1km 内的所有共享单车”或“检测游戏中哪些物体发生了碰撞”。传统的线性或二分查找在这种多维场景下完全失效，我们需要更聪明的空间索引结构。
2. 一维搜索 vs 二维搜索
我们都知道，二分查找 是在有序一维数组中定位目标值的高效手段，时间复杂度仅为 O(log n)，核心思想是“分而治之”。
但问题来了：如果数据是二维的（比如地图上的经纬度坐标），我们想找某个区域内的所有点，怎么办？
❌ 直接对 X 或 Y 坐标排序后二分查找？不行。因为一个维度上的有序，不代表另一个维度也有序。你可能在 X 轴上找到了范围，但 Y 轴上的点却散落各处。
✅ 正确思路是：我们需要一种能同时管理两个维度的数据结构。这就是 QuadTree 发挥作用的地方。
3. QuadTree 数据结构详解
3.1 核心思想
QuadTree 是一种空间分割树，每个非叶子节点恰好有四个子节点，分别代表当前区域的四个象限（西北、东北、西南、东南）。
- 节点容量：每个节点最多存储 N 个点（本文设为 3）。
- 动态分裂：当插入新点导致节点溢出时，该区域会自动均等划分为四个子区域，原有点根据坐标被分发到对应的子节点中。
- 递归构建：这个过程递归进行，形成一棵“区域树”。
3.2 构建过程图解
以以下 10 个坐标点为例：
(21,25), (55,53), (70,318), (98,302), (49,229), (135,229), (224,292), (206,321), (197,258), (245,238)
初始时，根节点区域为 (0,0) 到 (400,400)，可容纳前 3 个点。
当第 4 个点到来时，根节点满员，于是分裂成四个象限，后续的点根据坐标被插入到对应的象限中。
最终，某个象限（如右下角）可能再次分裂以容纳更多密集点，而其他稀疏区域则保持原样。这种按需分裂的策略非常节省内存。
4. Java 数据结构实现
我们需要三个核心类：
4.1 Point 类：表示二维坐标点
public class Point {
private float x;
private float y;
public Point(float x, float y) {
this.x = x;
this.y = y;
}
// getter 方法
public float getX() { return x; }
public float getY() { return y; }
@Override
public String toString() {
return String.format("[%s , %s]", x, y);
}
}
4.2 Region 类：定义区域边界
public class Region {
private float x1, y1; // 左下角坐标
private float x2, y2; // 右上角坐标
public Region(float x1, float y1, float x2, float y2) {
this.x1 = x1;
this.y1 = y1;
this.x2 = x2;
this.y2 = y2;
}
// getter 方法
public float getX1() { return x1; }
public float getY1() { return y1; }
public float getX2() { return x2; }
public float getY2() { return y2; }
@Override
public String toString() {
return String.format("Region[%s,%s -> %s,%s]", x1, y1, x2, y2);
}
}
4.3 QuadTree 类：核心数据结构
import java.util.*;
public class QuadTree {
private static final int MAX_POINTS = 3; // 节点容量阈值
private Region area; // 当前节点管理的区域
private List<Point> points = new ArrayList<>(); // 存储的点
private List<QuadTree> quadTrees = new ArrayList<>(); // 四个子节点
public QuadTree(Region area) {
this.area = area;
}
}
5. 核心算法实现
5.1 Region 辅助方法
这些方法是空间判断的基础，务必写对，否则整个结构会乱套。
✅ **containsPoint(Point point)**：判断点是否在区域内（左闭右开）
public boolean containsPoint(Point point) {
return point.getX() >= this.x1
&& point.getX() < this.x2
&& point.getY() >= this.y1
&& point.getY() < this.y2;
}
⚠️ 注意：使用 >= 和 < 可以避免点恰好落在边界上被重复计算。
✅ **doesOverlap(Region testRegion)**：判断两个区域是否相交
public boolean doesOverlap(Region testRegion) {
if (testRegion.getX2() < this.getX1()) return false; // 在左侧
if (testRegion.getX1() > this.getX2()) return false; // 在右侧
if (testRegion.getY1() > this.getY2()) return false; // 在上方
if (testRegion.getY2() < this.getY1()) return false; // 在下方
return true; // 有重叠
}
✅ **getQuadrant(int quadrantIndex)**：获取四个象限之一
public Region getQuadrant(int quadrantIndex) {
float quadrantWidth = (this.x2 - this.x1) / 2;
float quadrantHeight = (this.y2 - this.y1) / 2;
// 0=SW(西南), 1=NW(西北), 2=NE(东北), 3=SE(东南)
switch (quadrantIndex) {
case 0:
return new Region(x1, y1, x1 + quadrantWidth, y1 + quadrantHeight);
case 1:
return new Region(x1, y1 + quadrantHeight, x1 + quadrantWidth, y2);
case 2:
return new Region(x1 + quadrantWidth, y1 + quadrantHeight, x2, y2);
case 3:
return new Region(x1 + quadrantWidth, y1, x2, y1 + quadrantHeight);
}
return null;
}
5.2 插入数据 (addPoint)
这是最核心的操作，逻辑清晰是关键。
public boolean addPoint(Point point) {
// 1. 检查点是否在本区域范围内
if (!this.area.containsPoint(point)) {
return false; // 不在范围内，直接拒绝
}
// 2. 如果当前节点还有空位，直接插入
if (this.points.size() < MAX_POINTS) {
this.points.add(point);
return true;
}
// 3. 节点已满，需要分裂或插入到子节点
if (this.quadTrees.isEmpty()) {
createQuadrants(); // 首次分裂，创建四个子象限
}
// 4. 尝试将点插入到四个子象限中的某一个
return addPointToOneQuadrant(point);
}
// 辅助方法：创建四个子象限
private void createQuadrants() {
for (int i = 0; i < 4; i++) {
Region region = this.area.getQuadrant(i);
quadTrees.add(new QuadTree(region));
}
}
// 辅助方法：将点插入到第一个能容纳它的子象限
private boolean addPointToOneQuadrant(Point point) {
for (QuadTree child : quadTrees) {
if (child.addPoint(point)) { // 递归插入
return true;
}
}
return false; // 理论上不会执行到这里
}
5.3 范围搜索 (search)
搜索逻辑同样递归，简单粗暴：
- 快速排除：如果查询区域与当前区域无交集，直接返回。
- 收集本节点点：遍历本节点存储的点，落在查询区域内的加入结果集。
- 递归搜索子节点：对每个非空的子象限递归执行搜索。
public List<Point> search(Region searchRegion, List<Point> matches) {
if (matches == null) {
matches = new ArrayList<>();
}
// 快速失败：无交集
if (!this.area.doesOverlap(searchRegion)) {
return matches;
}
// 收集本节点符合条件的点
for (Point point : points) {
if (searchRegion.containsPoint(point)) {
matches.add(point);
}
}
// 递归搜索子节点
if (!quadTrees.isEmpty()) {
for (QuadTree child : quadTrees) {
child.search(searchRegion, matches);
}
}
return matches;
}
6. 测试验证
6.1 构建测试数据
// 定义全局区域
Region area = new Region(0, 0, 400, 400);
QuadTree quadTree = new QuadTree(area);
// 插入10个测试点
float[][] coords = {
{21, 25}, {55, 53}, {70, 318}, {98, 302}, {49, 229},
{135, 229}, {224, 292}, {206, 321}, {197, 258}, {245, 238}
};
for (float[] coord : coords) {
Point point = new Point(coord[0], coord[1]);
boolean success = quadTree.addPoint(point);
// 可以打印日志观察插入过程
}
6.2 执行范围查询
✅ 查询区域 (200,200) 到 (250,250)
Region searchArea = new Region(200, 200, 250, 250);
List<Point> result = quadTree.search(searchArea, null);
System.out.println(result); // 输出: [[245.0 , 238.0]]
✅ 查询区域 (0,0) 到 (100,100)
Region searchArea = new Region(0, 0, 100, 100);
List<Point> result = quadTree.search(searchArea, null);
System.out.println(result); // 输出: [[21.0 , 25.0], [55.0 , 53.0]]
结果符合预期！这说明我们的 QuadTree 能正确地进行空间索引和范围搜索。
6.3 进阶：查找最近的 N 个邻居
原文提到的“找最近 N 个邻居”是常见需求。QuadTree 本身不直接支持 KNN，但可以结合范围搜索实现：
- 以目标点为中心，定义一个初始搜索半径（如 50x50 区域）。
- 执行
search，得到候选点集。 - 计算候选点到目标点的欧几里得距离，排序取前 N 个。
- 如果候选点不足 N 个，扩大搜索半径，重复步骤 1-3。
7. 时间复杂度分析
- **插入 (Insert)**：平均 O(log n)，最坏 O(n)（当所有点都挤在一个小区域，导致深度分裂）。
- **搜索 (Search)**：最坏情况 O(n)，因为可能需要遍历所有节点（当查询区域覆盖整个空间时）。但在实际应用中，得益于空间剪枝，性能远优于 O(n)。
⚠️ 注意：QuadTree 的性能高度依赖于数据分布。如果点非常密集或集中在某区域，树会很深，影响效率。此时可考虑 KD-Tree 或 R-Tree 等更复杂的结构。
8. 总结
本文通过实现一个 QuadTree，展示了如何高效处理二维空间数据的范围查询问题。
- 核心优势：空间索引，避免全表扫描。
- 适用场景：地图标记、碰撞检测、图像分块等。
- 踩坑提醒：边界条件（
containsPoint的开闭区间）、分裂时机、递归终止条件必须严谨。
源码已托管至 GitHub：https://github.com/yourname/quadtree-demo （mock 链接）