每日算法 — 使用java实现八叉树：三维空间点集划分与最近邻高效搜索

算法概述

八叉树（Octree）是四叉树在三维空间的自然扩展，广泛应用于计算机图形学、物理引擎碰撞检测、三维地理信息系统和点云处理等领域。其核心思想是将三维空间递归地划分为8个子空间（象限），每个节点代表一个立方体区域，根据空间内点的分布决定是否继续细分，从而在密集区域提供高精度、稀疏区域保持低消耗的适应性空间索引。

核心原理

八叉树的构建过程：

1. 定义根节点覆盖整个三维空间边界框（AABB）
2. 将点插入对应节点，若节点内点数超过阈值且未达到最大深度，则分裂为8个子节点
3. 8个子节点分别对应父节点的：左下前、右下前、左下后、右下后、左上前、右上前、左上后、右上后
4. 重复步骤2-3直至满足终止条件

空间查询时，通过递归判断查询区域与节点包围盒的交集关系，快速排除无关分支。

Java完整实现

import java.util.ArrayList;
import java.util.List;

/**
 * 八叉树三维空间索引实现
 * 应用场景：点云处理、碰撞检测、最近邻搜索、三维GIS
 */
public class Octree {

    // 三维点
    public static class Point3D {
        public double x, y, z;
        public Object data; // 可附加任意数据

        public Point3D(double x, double y, double z) {
            this.x = x; this.y = y; this.z = z;
        }

        public Point3D(double x, double y, double z, Object data) {
            this(x, y, z);
            this.data = data;
        }

        public double distanceSquared(Point3D other) {
            double dx = x - other.x;
            double dy = y - other.y;
            double dz = z - other.z;
            return dx * dx + dy * dy + dz * dz;
        }

        @Override
        public String toString() {
            return String.format("(%.2f, %.2f, %.2f)", x, y, z);
        }
    }

    // 轴对齐包围盒
    public static class BoundingBox {
        public double minX, minY, minZ;
        public double maxX, maxY, maxZ;

        public BoundingBox(double minX, double minY, double minZ,
                          double maxX, double maxY, double maxZ) {
            this.minX = minX; this.minY = minY; this.minZ = minZ;
            this.maxX = maxX; this.maxY = maxY; this.maxZ = maxZ;
        }

        public double getCenterX() { return (minX + maxX) / 2; }
        public double getCenterY() { return (minY + maxY) / 2; }
        public double getCenterZ() { return (minZ + maxZ) / 2; }

        public boolean contains(Point3D p) {
            return p.x >= minX && p.x <= maxX &&
                   p.y >= minY && p.y <= maxY &&
                   p.z >= minZ && p.z <= maxZ;
        }

        public boolean intersects(BoundingBox other) {
            return !(other.minX > maxX || other.maxX < minX ||
                     other.minY > maxY || other.maxY < minY ||
                     other.minZ > maxZ || other.maxZ < minZ);
        }

        // 计算点到包围盒的最小距离平方
        public double distanceSquaredToPoint(Point3D p) {
            double dx = 0, dy = 0, dz = 0;
            if (p.x < minX) dx = minX - p.x;
            else if (p.x > maxX) dx = p.x - maxX;
            if (p.y < minY) dy = minY - p.y;
            else if (p.y > maxY) dy = p.y - maxY;
            if (p.z < minZ) dz = minZ - p.z;
            else if (p.z > maxZ) dz = p.z - maxZ;
            return dx * dx + dy * dy + dz * dz;
        }
    }

    private static final int MAX_POINTS = 8;   // 节点最大点数阈值
    private static final int MAX_DEPTH = 10;   // 最大递归深度

    private BoundingBox bounds;
    private List<Point3D> points;
    private Octree[] children; // 8个子节点
    private int depth;

    public Octree(BoundingBox bounds, int depth) {
        this.bounds = bounds;
        this.points = new ArrayList<>();
        this.children = null;
        this.depth = depth;
    }

    /**
     * 插入点到八叉树
     */
    public void insert(Point3D point) {
        if (!bounds.contains(point)) {
            return; // 点不在当前节点范围内
        }

        if (children == null) {
            points.add(point);
            // 超过阈值且未达到最大深度时分裂
            if (points.size() > MAX_POINTS && depth < MAX_DEPTH) {
                subdivide();
            }
        } else {
            // 已分裂，插入到对应子节点
            for (Octree child : children) {
                if (child.bounds.contains(point)) {
                    child.insert(point);
                    break;
                }
            }
        }
    }

    /**
     * 将当前节点分裂为8个子节点
     */
    private void subdivide() {
        children = new Octree[8];
        double cx = bounds.getCenterX();
        double cy = bounds.getCenterY();
        double cz = bounds.getCenterZ();

        // 8个子象限的包围盒
        children[0] = new Octree(new BoundingBox(bounds.minX, bounds.minY, bounds.minZ, cx, cy, cz), depth + 1);
        children[1] = new Octree(new BoundingBox(cx, bounds.minY, bounds.minZ, bounds.maxX, cy, cz), depth + 1);
        children[2] = new Octree(new BoundingBox(bounds.minX, cy, bounds.minZ, cx, bounds.maxY, cz), depth + 1);
        children[3] = new Octree(new BoundingBox(cx, cy, bounds.minZ, bounds.maxX, bounds.maxY, cz), depth + 1);
        children[4] = new Octree(new BoundingBox(bounds.minX, bounds.minY, cz, cx, cy, bounds.maxZ), depth + 1);
        children[5] = new Octree(new BoundingBox(cx, bounds.minY, cz, bounds.maxX, cy, bounds.maxZ), depth + 1);
        children[6] = new Octree(new BoundingBox(bounds.minX, cy, cz, cx, bounds.maxY, bounds.maxZ), depth + 1);
        children[7] = new Octree(new BoundingBox(cx, cy, cz, bounds.maxX, bounds.maxY, bounds.maxZ), depth + 1);

        // 将已有 points 重新分配到子节点
        for (Point3D p : points) {
            for (Octree child : children) {
                if (child.bounds.contains(p)) {
                    child.insert(p);
                    break;
                }
            }
        }
        points.clear(); // 清空当前节点的直接存储
    }

    /**
     * 范围查询：查找指定包围盒内的所有点
     */
    public List<Point3D> queryRange(BoundingBox range) {
        List<Point3D> result = new ArrayList<>();

        if (!bounds.intersects(range)) {
            return result;
        }

        // 检查当前节点直接存储的点
        for (Point3D p : points) {
            if (range.contains(p)) {
                result.add(p);
            }
        }

        // 递归查询子节点
        if (children != null) {
            for (Octree child : children) {
                result.addAll(child.queryRange(range));
            }
        }

        return result;
    }

    /**
     * 最近邻搜索：查找距离目标点最近的点
     */
    public Point3D nearestNeighbor(Point3D target) {
        return nearestNeighbor(target, null, Double.MAX_VALUE);
    }

    private Point3D nearestNeighbor(Point3D target, Point3D best, double bestDistSq) {
        // 剪枝：如果当前节点的包围盒距离目标点比当前最优距离还远，直接返回
        double nodeDistSq = bounds.distanceSquaredToPoint(target);
        if (nodeDistSq >= bestDistSq) {
            return best;
        }

        // 检查当前节点直接存储的点
        for (Point3D p : points) {
            double distSq = p.distanceSquared(target);
            if (distSq < bestDistSq && distSq > 0) { // distSq > 0 排除目标点自身
                bestDistSq = distSq;
                best = p;
            }
        }

        // 递归查询子节点，按距离排序优先访问更近的
        if (children != null) {
            // 优先访问包含目标点的子节点
            for (Octree child : children) {
                if (child.bounds.contains(target)) {
                    best = child.nearestNeighbor(target, best, bestDistSq);
                    if (best != null) bestDistSq = best.distanceSquared(target);
                    break;
                }
            }
            // 再访问其他可能包含更近点的子节点
            for (Octree child : children) {
                if (!child.bounds.contains(target)) {
                    double childDistSq = child.bounds.distanceSquaredToPoint(target);
                    if (childDistSq < bestDistSq) {
                        best = child.nearestNeighbor(target, best, bestDistSq);
                        if (best != null) bestDistSq = best.distanceSquared(target);
                    }
                }
            }
        }

        return best;
    }

    public static void main(String[] args) {
        // 创建八叉树，覆盖 0~100 的三维空间
        Octree octree = new Octree(new BoundingBox(0, 0, 0, 100, 100, 100), 0);

        // 插入随机点
        java.util.Random rand = new java.util.Random(42);
        for (int i = 0; i < 1000; i++) {
            octree.insert(new Point3D(
                rand.nextDouble() * 100,
                rand.nextDouble() * 100,
                rand.nextDouble() * 100,
                "Point_" + i
            ));
        }

        // 范围查询
        BoundingBox queryBox = new BoundingBox(40, 40, 40, 60, 60, 60);
        List<Point3D> inRange = octree.queryRange(queryBox);
        System.out.println("范围 " + queryBox + " 内找到 " + inRange.size() + " 个点");

        // 最近邻搜索
        Point3D target = new Point3D(50, 50, 50);
        Point3D nearest = octree.nearestNeighbor(target);
        System.out.println("距离 " + target + " 最近的点: " + nearest);
        if (nearest != null) {
            System.out.println("距离: " + Math.sqrt(target.distanceSquared(nearest)));
        }
    }
}

复杂度分析

其中N为点数，D为树的最大深度，k为查询结果数量。

应用场景

• 点云处理：LiDAR数据的快速邻域查询和降采样
• 物理引擎：刚体碰撞检测的粗筛阶段
• 三维GIS：地理空间数据的层级管理与LOD渲染
• 分子模拟：粒子间相互作用力的近邻列表构建
• 游戏开发：大型场景中的视锥剔除与对象管理

八叉树通过自适应的空间细分，在三维数据处理中提供了时间与空间的最优平衡。