算法概述
四叉树（Quadtree）是一种基于空间递归分区的树形数据结构，通过将二维平面沿中轴划分为四个象限（西北、东北、西南、东南），实现对空间中点的层次化组织。四叉树在计算机图形学、地理信息系统（GIS）、碰撞检测、图像压缩和最近邻搜索等领域有广泛应用。
本文用Java实现一个完整的点四叉树（Point Quadtree），支持插入、查询、范围搜索和最近邻查找，并探讨其在游戏场景中的实际应用。
核心原理
四叉树的核心思想是自适应空间划分：
1. 每个节点对应一个矩形区域，存储该区域内的数据点
2. 当节点中的点数超过容量阈值时，将该区域四等分，生成四个子节点
3. 数据点根据坐标落入对应的子象限
4. 递归执行上述过程，直到满足停止条件（达到最大深度或点数不超过阈值）
对于一个覆盖范围 ([x_{min}, x_{max}] \times [y_{min}, y_{max}]) 的节点，划分线为：
– 垂直划分线：(x_{mid} = (x_{min} + x_{max}) / 2)
– 水平划分线：(y_{mid} = (y_{min} + y_{max}) / 2)
四个子象限：
– 西北（NW）：(x < x_{mid}, y \geq y_{mid})
– 东北（NE）：(x \geq x_{mid}, y \geq y_{mid})
– 西南（SW）：(x < x_{mid}, y < y_{mid})
– 东南（SE）：(x \geq x_{mid}, y < y_{mid})
Java实现
项目结构
quadtree/
├── Point.java // 二维点封装
├── Rectangle.java // 矩形区域
├── QuadTreeNode.java // 四叉树节点
├── QuadTree.java // 四叉树核心实现
├── GameEntity.java // 游戏实体示例
└── Main.java // 测试入口
基础数据结构
/**
* 二维点，支持距离计算
*/
public class Point {
public final double x;
public final double y;
public final Object data; // 附加数据
public Point(double x, double y) {
this(x, y, null);
}
public Point(double x, double y, Object data) {
this.x = x;
this.y = y;
this.data = data;
}
/**
* 欧几里得距离平方（避免开方运算）
*/
public double distSq(Point other) {
double dx = this.x - other.x;
double dy = this.y - other.y;
return dx * dx + dy * dy;
}
public double dist(Point other) {
return Math.sqrt(distSq(other));
}
@Override
public String toString() {
return String.format("(%.2f, %.2f)", x, y);
}
}
/**
* 轴对齐矩形区域
*/
public class Rectangle {
public final double xMin, xMax, yMin, yMax;
public Rectangle(double xMin, double xMax, double yMin, double yMax) {
if (xMin >= xMax || yMin >= yMax) {
throw new IllegalArgumentException("非法矩形边界");
}
this.xMin = xMin;
this.xMax = xMax;
this.yMin = yMin;
this.yMax = yMax;
}
/**
* 判断点是否在矩形内（包含边界）
*/
public boolean contains(Point p) {
return p.x >= xMin && p.x <= xMax && p.y >= yMin && p.y <= yMax;
}
/**
* 判断两个矩形是否相交
*/
public boolean intersects(Rectangle other) {
return !(other.xMin > this.xMax || other.xMax < this.xMin
|| other.yMin > this.yMax || other.yMax < this.yMin);
}
/**
* 计算矩形中心
*/
public Point center() {
return new Point((xMin + xMax) / 2, (yMin + yMax) / 2);
}
/**
* 计算矩形到某点的最短距离平方
*/
public double distSqToPoint(Point p) {
double dx = 0;
if (p.x < xMin) dx = xMin - p.x;
else if (p.x > xMax) dx = p.x - xMax;
double dy = 0;
if (p.y < yMin) dy = yMin - p.y;
else if (p.y > yMax) dy = p.y - yMax;
return dx * dx + dy * dy;
}
@Override
public String toString() {
return String.format("[%.1f,%.1f]x[%.1f,%.1f]", xMin, xMax, yMin, yMax);
}
}
四叉树核心实现：QuadTree.java
import java.util.ArrayList;
import java.util.List;
/**
* 点四叉树（Point Quadtree）
* 支持动态插入、范围查询、最近邻搜索
*/
public class QuadTree {
private static final int MAX_CAPACITY = 4; // 节点最大容量
private static final int MAX_DEPTH = 10; // 最大深度限制
private QuadTreeNode root;
private int size;
/**
* 四叉树节点
*/
private static class QuadTreeNode {
Rectangle boundary;
List<Point> points;
QuadTreeNode nw, ne, sw, se; // 四个子象限
boolean divided;
int depth;
QuadTreeNode(Rectangle boundary, int depth) {
this.boundary = boundary;
this.points = new ArrayList<>();
this.divided = false;
this.depth = depth;
}
/**
* 将当前节点划分为四个子象限
*/
void subdivide() {
double xMid = (boundary.xMin + boundary.xMax) / 2;
double yMid = (boundary.yMin + boundary.yMax) / 2;
nw = new QuadTreeNode(new Rectangle(boundary.xMin, xMid, yMid, boundary.yMax), depth + 1);
ne = new QuadTreeNode(new Rectangle(xMid, boundary.xMax, yMid, boundary.yMax), depth + 1);
sw = new QuadTreeNode(new Rectangle(boundary.xMin, xMid, boundary.yMin, yMid), depth + 1);
se = new QuadTreeNode(new Rectangle(xMid, boundary.xMax, boundary.yMin, yMid), depth + 1);
divided = true;
// 将已有数据点重新分配到子节点
List<Point> temp = new ArrayList<>(points);
points.clear();
for (Point p : temp) {
insertToChild(p);
}
}
/**
* 将点插入到合适的子象限
*/
boolean insertToChild(Point p) {
if (nw.boundary.contains(p)) return nw.insert(p);
if (ne.boundary.contains(p)) return ne.insert(p);
if (sw.boundary.contains(p)) return sw.insert(p);
if (se.boundary.contains(p)) return se.insert(p);
return false; // 不应发生
}
/**
* 插入点
*/
boolean insert(Point p) {
if (!boundary.contains(p)) return false;
if (!divided) {
if (points.size() < MAX_CAPACITY || depth >= MAX_DEPTH) {
points.add(p);
return true;
}
subdivide();
}
return insertToChild(p);
}
/**
* 范围查询：查找矩形范围内的所有点
*/
void query(Rectangle range, List<Point> found) {
if (!boundary.intersects(range)) return;
for (Point p : points) {
if (range.contains(p)) {
found.add(p);
}
}
if (divided) {
nw.query(range, found);
ne.query(range, found);
sw.query(range, found);
se.query(range, found);
}
}
/**
* 最近邻搜索辅助方法
* @param target 目标点
* @param best 当前最优解 [距离的平方, 最近点]
*/
void nearest(Point target, Object[] best) {
// 剪枝：如果当前区域到目标点的最短距离已大于已知最优，直接返回
double distSqToRegion = boundary.distSqToPoint(target);
if (distSqToRegion > (Double) best[0]) return;
// 检查当前节点的所有点
for (Point p : points) {
double d = p.distSq(target);
if (d < (Double) best[0]) {
best[0] = d;
best[1] = p;
}
}
if (!divided) return;
// 按距离排序子节点，优先搜索更近的象限
QuadTreeNode[] children = {nw, ne, sw, se};
// 简单的排序：优先搜索包含目标点的象限
for (QuadTreeNode child : children) {
child.nearest(target, best);
}
}
int count() {
int c = points.size();
if (divided) {
c += nw.count() + ne.count() + sw.count() + se.count();
}
return c;
}
}
public QuadTree(Rectangle boundary) {
this.root = new QuadTreeNode(boundary, 0);
this.size = 0;
}
/**
* 插入一个点
*/
public boolean insert(Point p) {
boolean success = root.insert(p);
if (success) size++;
return success;
}
/**
* 批量插入
*/
public void insertAll(List<Point> points) {
for (Point p : points) {
insert(p);
}
}
/**
* 范围查询
*/
public List<Point> query(Rectangle range) {
List<Point> found = new ArrayList<>();
root.query(range, found);
return found;
}
/**
* 最近邻搜索
* @param target 目标点
* @return 最近的点，若树为空则返回null
*/
public Point nearest(Point target) {
if (size == 0) return null;
// 初始最优解设为无穷远
Object[] best = {Double.POSITIVE_INFINITY, null};
root.nearest(target, best);
return (Point) best[1];
}
/**
* K近邻搜索
*/
public List<Point> kNearest(Point target, int k) {
if (k <= 0 || size == 0) return new ArrayList<>();
// 使用优先队列（最大堆）维护当前K个最近点
java.util.PriorityQueue<Point> pq = new java.util.PriorityQueue<>(
(a, b) -> Double.compare(b.distSq(target), a.distSq(target))
);
collectAll(root, target, pq, k);
List<Point> result = new ArrayList<>(pq);
result.sort((a, b) -> Double.compare(a.distSq(target), b.distSq(target)));
return result;
}
private void collectAll(QuadTreeNode node, Point target,
java.util.PriorityQueue<Point> pq, int k) {
if (node == null) return;
// 剪枝
double distSqToRegion = node.boundary.distSqToPoint(target);
if (!pq.isEmpty() && distSqToRegion > pq.peek().distSq(target)) {
return;
}
for (Point p : node.points) {
pq.offer(p);
if (pq.size() > k) pq.poll();
}
if (node.divided) {
collectAll(node.nw, target, pq, k);
collectAll(node.ne, target, pq, k);
collectAll(node.sw, target, pq, k);
collectAll(node.se, target, pq, k);
}
}
public int size() {
return size;
}
/**
* 验证数据完整性
*/
public boolean validate() {
return root.count() == size;
}
}
游戏实体管理示例：GameEntity.java
/**
* 游戏实体管理器 - 四叉树在游戏开发中的应用
* 管理大量游戏单位（NPC、玩家、道具），支持视野查询和碰撞检测
*/
public class GameEntity {
public static class Entity {
String id;
Point position;
double radius; // 碰撞半径
String type; // player, monster, item
public Entity(String id, double x, double y, double radius, String type) {
this.id = id;
this.position = new Point(x, y, this);
this.radius = radius;
this.type = type;
}
@Override
public String toString() {
return String.format("%s[%s]@(%.1f,%.1f)", type, id, position.x, position.y);
}
}
public static void main(String[] args) {
// 创建1000x1000的游戏世界
QuadTree world = new QuadTree(new Rectangle(0, 1000, 0, 1000));
java.util.Random rand = new java.util.Random(42);
// 生成1000个随机实体
List<Entity> entities = new ArrayList<>();
for (int i = 0; i < 1000; i++) {
String type = rand.nextDouble() < 0.5 ? "monster" : "item";
Entity e = new Entity(
"E" + i,
rand.nextDouble() * 1000,
rand.nextDouble() * 1000,
5 + rand.nextDouble() * 15,
type
);
entities.add(e);
world.insert(e.position);
}
System.out.println("=== 游戏世界实体管理 ===");
System.out.println("总实体数: " + world.size());
System.out.println("数据完整性: " + world.validate());
// 场景1：玩家视野查询（以(500,500)为中心，200x200范围）
System.out.println("\n--- 视野范围查询 ---");
Rectangle viewRange = new Rectangle(400, 600, 400, 600);
List<Point> visible = world.query(viewRange);
System.out.printf("视野内实体数: %d%n", visible.size());
visible.stream().limit(5).forEach(p -> System.out.println(" " + p.data));
// 场景2：最近道具查找
System.out.println("\n--- 最近实体查找 ---");
Point playerPos = new Point(500, 500);
Point nearest = world.nearest(playerPos);
System.out.printf("玩家位置: %s%n", playerPos);
System.out.printf("最近实体: %s (距离: %.2f)%n",
nearest.data, playerPos.dist(nearest));
// 场景3：K近邻
System.out.println("\n--- 5个最近实体 ---");
List<Point> kNearest = world.kNearest(playerPos, 5);
for (int i = 0; i < kNearest.size(); i++) {
Point p = kNearest.get(i);
System.out.printf(" #%d: %s (距离: %.2f)%n",
i + 1, p.data, playerPos.dist(p));
}
}
}
测试入口：Main.java
public class Main {
public static void main(String[] args) {
System.out.println("=== 四叉树空间索引测试 ===\n");
// 测试1：基本插入与查询
System.out.println("--- 测试1：插入与范围查询 ---");
QuadTree qt = new QuadTree(new Rectangle(0, 100, 0, 100));
Point[] points = {
new Point(10, 10), new Point(20, 20), new Point(30, 30),
new Point(40, 40), new Point(50, 50), new Point(60, 60),
new Point(70, 70), new Point(80, 80), new Point(90, 90),
new Point(15, 85), new Point(85, 15)
};
for (Point p : points) {
qt.insert(p);
}
System.out.println("插入点数: " + qt.size());
Rectangle range = new Rectangle(20, 60, 20, 60);
List<Point> result = qt.query(range);
System.out.println("范围 " + range + " 内点数: " + result.size());
result.forEach(p -> System.out.println(" " + p));
// 测试2：最近邻
System.out.println("\n--- 测试2：最近邻搜索 ---");
Point target = new Point(55, 55);
Point nearest = qt.nearest(target);
System.out.println("目标点: " + target);
System.out.println("最近点: " + nearest + " (距离: " + target.dist(nearest) + ")");
// 测试3：大规模性能测试
System.out.println("\n--- 测试3：性能测试 (10万点) ---");
QuadTree bigTree = new QuadTree(new Rectangle(0, 10000, 0, 10000));
java.util.Random rand = new java.util.Random(123);
long start = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
bigTree.insert(new Point(rand.nextDouble() * 10000, rand.nextDouble() * 10000));
}
long insertTime = System.currentTimeMillis() - start;
System.out.println("插入10万点耗时: " + insertTime + "ms");
start = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) {
bigTree.query(new Rectangle(
rand.nextDouble() * 9000, rand.nextDouble() * 9000 + 1000,
rand.nextDouble() * 9000, rand.nextDouble() * 9000 + 1000
));
}
long queryTime = System.currentTimeMillis() - start;
System.out.println("1万次范围查询耗时: " + queryTime + "ms");
start = System.currentTimeMillis();
for (int i = 0; i < 1000; i++) {
bigTree.nearest(new Point(rand.nextDouble() * 10000, rand.nextDouble() * 10000));
}
long nearestTime = System.currentTimeMillis() - start;
System.out.println("1000次最近邻查询耗时: " + nearestTime + "ms");
// 测试4：游戏实体管理
System.out.println("\n--- 测试4：游戏实体管理 ---");
GameEntity.main(args);
}
}
复杂度分析
| 操作 | 平均时间复杂度 | 最坏时间复杂度 |
|---|---|---|
| 插入 | (O(\log n)) | (O(n))（所有点共线） |
| 范围查询 | (O(k + \log n)) | (O(n))（范围覆盖全部） |
| 最近邻 | (O(\log n)) | (O(n)) |
| K近邻 | (O(k \log n)) | (O(n \log k)) |
空间复杂度为 (O(n))，每个点仅存储一次。
适用场景
- 游戏开发：大规模单位的视野查询、碰撞检测、寻路辅助
- 地理信息系统：空间索引、邻近查询、地图渲染
- 计算机图形学：光线追踪加速、场景管理
- 图像处理：图像压缩（四叉树编码）、区域分割
- 机器学习：空间数据索引、局部敏感哈希辅助
与k-d树的对比
| 特性 | 四叉树 | k-d树 |
|---|---|---|
| 划分维度 | 固定2D四等分 | 按维度循环二分 |
| 构造方式 | 自底向上（动态） | 通常自顶向下（静态） |
| 平衡性 | 依赖数据分布 | 可强制平衡 |
| 最佳场景 | 动态数据、范围查询 | 精确KNN、静态数据 |
扩展方向
- 线性四叉树：用Morton码（Z-order曲线）压缩存储
- R树/R*树：支持矩形对象而不仅是点
- 八叉树（Octree）：三维空间扩展
总结
四叉树是处理二维空间数据的基础索引结构。通过Java实现，我们掌握了自适应空间划分的核心思想：根据数据密度动态调整划分粒度，在稠密区域细分、稀疏区域粗分。在游戏实体管理、GIS系统、碰撞检测等需要高效空间查询的场景中，四叉树以其简洁的实现和良好的平均性能，成为一种不可或缺的空间索引工具。
