Java实现高效存储IShape并按坐标返回最上层形状的方案问询

针对你这个存储大量IShape并高效查询指定坐标最上层形状的需求，普通集合遍历肯定扛不住——尤其是当形状边界范围极大时，必须用空间数据结构来优化。下面给你几个经过验证的方案，从实现复杂度和适用场景帮你拆解：

方案1：四叉树（Quadtree） #

这是2D空间索引里最常用的结构之一，特别适合静态或低动态的形状集合：

• 核心思路：把整个空间递归划分成四个象限，每个节点只存储落在自己范围内的形状，查询(x,y)时只需要遍历包含该点的子节点，不用扫全量数据。
• 适配细节：
  • 每个四叉树节点维护一个形状列表和自身的边界范围
  • 查询时从根节点往下遍历，直到叶子节点，收集所有包含目标点的形状，再按z-index层级排序取最上层的
  • 若形状动态增删频繁，需要实现节点的拆分/合并逻辑；跨象限的形状要在多个节点中存储引用（或记录覆盖的节点）
• 核心代码示例：

public class Quadtree {
    private static final int MAX_SHAPES_PER_NODE = 10;
    private Rectangle bounds;
    private List<IShape> shapes;
    private Quadtree[] children;

    public Quadtree(Rectangle bounds) {
        this.bounds = bounds;
        this.shapes = new ArrayList<>();
        this.children = null;
    }

    public boolean insert(IShape shape) {
        Rectangle shapeBounds = new Rectangle(shape.getLeft(), shape.getTop(),
                shape.getRight() - shape.getLeft(), shape.getBottom() - shape.getTop());
        if (!bounds.intersects(shapeBounds)) return false;

        if (shapes.size() < MAX_SHAPES_PER_NODE) {
            shapes.add(shape);
            return true;
        }

        if (children == null) split();
        return children[0].insert(shape) || children[1].insert(shape) ||
               children[2].insert(shape) || children[3].insert(shape);
    }

    public List<IShape> query(int x, int y) {
        List<IShape> result = new ArrayList<>();
        if (!bounds.contains(x, y)) return result;

        // 筛选当前节点内包含目标点的形状
        for (IShape shape : shapes) {
            if (x >= shape.getLeft() && x <= shape.getRight() &&
                y >= shape.getTop() && y <= shape.getBottom()) {
                result.add(shape);
            }
        }

        if (children != null) {
            result.addAll(children[0].query(x, y));
            result.addAll(children[1].query(x, y));
            result.addAll(children[2].query(x, y));
            result.addAll(children[3].query(x, y));
        }
        return result;
    }

    private void split() {
        int x = bounds.x;
        int y = bounds.y;
        int w = bounds.width / 2;
        int h = bounds.height / 2;
        children = new Quadtree[4];
        children[0] = new Quadtree(new Rectangle(x, y, w, h));     // 左上
        children[1] = new Quadtree(new Rectangle(x + w, y, w, h)); // 右上
        children[2] = new Quadtree(new Rectangle(x, y + h, w, h)); // 左下
        children[3] = new Quadtree(new Rectangle(x + w, y + h, w, h)); // 右下
    }
}

• 最后一步：拿到查询结果后，从getProperties()中取出z-index，排序后取最大值对应的形状即可。

方案2：R树（R-Tree） #

如果你的形状动态变化频繁（增删移操作多），或者形状边界不规则、跨度极大，R树会比四叉树更合适：

• 核心思路：以形状的最小包围矩形（MBR）作为索引单元，节点中的MBR尽可能紧凑地包含子节点的MBR，查询时只遍历与目标点相交的MBR路径。
• 优势：不需要预先划分固定空间，能自适应形状分布，完美适配坐标范围极大的场景（不用提前定义超大的根节点边界）。
• 实现建议：不用自己造轮子，直接用成熟的Java库，比如JTS Topology Suite的STRtree（R树变种）：

import org.locationtech.jts.index.strtree.STRtree;
import org.locationtech.jts.geom.Envelope;
import java.util.Comparator;
import java.util.List;

public class ShapeRTreeIndex {
    private STRtree index;

    public ShapeRTreeIndex() {
        index = new STRtree();
    }

    public void addShape(IShape shape) {
        Envelope envelope = new Envelope(shape.getLeft(), shape.getRight(),
                shape.getTop(), shape.getBottom());
        index.insert(envelope, shape);
    }

    public IShape getTopShapeAt(int x, int y) {
        Envelope pointEnv = new Envelope(x, x, y, y);
        List<IShape> candidates = index.query(pointEnv);
        
        return candidates.stream()
                .max(Comparator.comparingInt(s -> 
                        Integer.parseInt(s.getProperties().getProperty("z-index", "0"))))
                .orElse(null);
    }
}

• 提示：STRtree的插入和查询性能都很稳定，适合大规模数据场景。

方案3：网格哈希（Grid Hashing） #

如果你的形状大小相对均匀，或者可以接受一定的查询误差，这是实现最简单的高性能方案：

• 核心思路：把整个空间划分成固定大小的网格单元格，每个单元格对应一个形状集合。查询(x,y)时，计算对应的网格坐标，再检查该单元格及相邻单元格的形状（处理跨网格的情况）。
• 适配场景：坐标范围极大但形状尺寸不会远超网格尺寸的情况，比如地图图标、小图形。
• 核心代码示例：

import java.util.*;
import java.util.stream.Collectors;

public class GridShapeIndex {
    private static final int GRID_SIZE = 100; // 根据形状平均尺寸调整
    private Map<GridPoint, List<IShape>> gridMap = new HashMap<>();

    public void addShape(IShape shape) {
        int minGridX = shape.getLeft() / GRID_SIZE;
        int maxGridX = shape.getRight() / GRID_SIZE;
        int minGridY = shape.getTop() / GRID_SIZE;
        int maxGridY = shape.getBottom() / GRID_SIZE;

        for (int x = minGridX; x <= maxGridX; x++) {
            for (int y = minGridY; y <= maxGridY; y++) {
                GridPoint key = new GridPoint(x, y);
                gridMap.computeIfAbsent(key, k -> new ArrayList<>()).add(shape);
            }
        }
    }

    public IShape getTopShapeAt(int x, int y) {
        int gridX = x / GRID_SIZE;
        int gridY = y / GRID_SIZE;
        Set<GridPoint> checkGrids = Set.of(
                new GridPoint(gridX, gridY),
                new GridPoint(gridX-1, gridY),
                new GridPoint(gridX+1, gridY),
                new GridPoint(gridX, gridY-1),
                new GridPoint(gridX, gridY+1)
        );

        List<IShape> candidates = new ArrayList<>();
        for (GridPoint grid : checkGrids) {
            List<IShape> shapes = gridMap.get(grid);
            if (shapes != null) {
                candidates.addAll(shapes.stream()
                        .filter(s -> x >= s.getLeft() && x <= s.getRight() &&
                                     y >= s.getTop() && y <= s.getBottom())
                        .collect(Collectors.toList()));
            }
        }

        return candidates.stream()
                .max(Comparator.comparingInt(s -> 
                        Integer.parseInt(s.getProperties().getProperty("z-index", "0"))))
                .orElse(null);
    }

    // 网格坐标辅助类，必须重写equals和hashCode
    private static class GridPoint {
        int x, y;
        GridPoint(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            GridPoint that = (GridPoint) o;
            return x == that.x && y == that.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }
}

• 优点：实现超简单，查询速度极快；缺点：大形状会被存在多个网格中，占用更多内存；形状分布极端不均时，部分网格会堆积大量形状，查询效率下降。

选型总结 #

• 静态数据（极少增删改）：优先选四叉树，实现可控，性能稳定。
• 动态数据/不规则大形状：优先选R树（用现成库，避免自己实现的坑）。
• 追求极简实现+形状尺寸均匀：选网格哈希。

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