第13章 - 空间索引体系

import org.locationtech.jts.geom.Coordinate;
import org.locationtech.jts.geom.Envelope;
import org.locationtech.jts.geom.GeometryFactory;
import org.locationtech.jts.geom.Point;
import org.locationtech.jts.index.strtree.STRtree;

public class GridQueryDemo {
    public static void main(String[] args) {
        GeometryFactory gf = new GeometryFactory();
        Point[] pts = new Point[100 * 100];
        STRtree index = new STRtree();

        for (int i = 0; i < 100; i++) {
            for (int j = 0; j < 100; j++) {
                Point p = gf.createPoint(new Coordinate(i, j));
                pts[i * 100 + j] = p;
                // 只把包络放进索引，几何对象本身作为 item 保存
                index.insert(p.getEnvelopeInternal(), p);
            }
        }

        Envelope window = new Envelope(95, 105, 95, 105);

        // 全表扫描：每个点都要和窗口比一次
        int scanHits = 0;
        for (Point p : pts) {
            if (window.contains(p.getCoordinate())) scanHits++;
        }

        // 索引查询：只访问可能命中的叶节点
        int indexHits = index.query(window).size();

        System.out.println("全表扫描：10000 次判定，命中 " + scanHits + " 个点");
        System.out.println("STRtree：query 返回 " + indexHits + " 个候选");
        System.out.println("tree.size()=" + index.size() + ", tree.depth()=" + index.depth());
    }
}

public interface SpatialIndex {
    /** 插入一个由 Envelope 指定范围的空间对象 */
    void insert(Envelope itemEnv, Object item);

    /** 查询与 searchEnv 相交的所有对象，返回 List */
    List query(Envelope searchEnv);

    /** 查询与 searchEnv 相交的所有对象，逐个交给 visitor */
    void query(Envelope searchEnv, ItemVisitor visitor);

    /** 从索引中删除一个对象 */
    boolean remove(Envelope itemEnv, Object item);
}

public interface ItemVisitor {
    void visitItem(Object item);
}

public class ArrayListVisitor implements ItemVisitor {
    private ArrayList items = new ArrayList();
    public void visitItem(Object item) { items.add(item); }
    public ArrayList getItems() { return items; }
}

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

import org.locationtech.jts.geom.Envelope;
import org.locationtech.jts.geom.Geometry;
import org.locationtech.jts.geom.GeometryFactory;
import org.locationtech.jts.geom.Polygon;
import org.locationtech.jts.index.ItemVisitor;
import org.locationtech.jts.index.strtree.STRtree;
import org.locationtech.jts.io.WKTReader;

public class VisitorFilterDemo {
    public static void main(String[] args) throws Exception {
        WKTReader reader = new WKTReader();
        GeometryFactory gf = new GeometryFactory();
        STRtree tree = new STRtree();

        String[] wkts = {
            "POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0))",
            "POLYGON ((20 0, 30 0, 30 10, 20 10, 20 0))",
            "POLYGON ((0 20, 10 20, 10 30, 0 30, 0 20))",
            "POLYGON ((20 20, 30 20, 30 30, 20 30, 20 20))"
        };
        for (String wkt : wkts) {
            Geometry g = reader.read(wkt);
            tree.insert(g.getEnvelopeInternal(), g);
        }

        // 查询几何是一个覆盖左上、右下两块的斜三角形
        Geometry query = reader.read(
            "POLYGON ((0 0, 30 0, 30 30, 0 0))");
        final List<Geometry> exactHits = new ArrayList<Geometry>();
        final int[] primaryCount = new int[1];

        tree.query(query.getEnvelopeInternal(), new ItemVisitor() {
            @Override
            public void visitItem(Object item) {
                primaryCount[0]++;
                Geometry g = (Geometry) item;
                // 二级过滤：索引只保证包络相交
                if (g.intersects(query)) {
                    exactHits.add(g);
                }
            }
        });

        System.out.println("一级过滤放行：" + primaryCount[0] + " 个");
        System.out.println("二级过滤命中：" + exactHits.size() + " 个");
        for (Geometry g : exactHits) {
            System.out.println("  " + g);
        }
    }
}

Envelope env = new Envelope();
for (Geometry g : geometries) {
    env.init(g.getEnvelopeInternal()); // 复用同一个对象
    tree.insert(env, g);               // 危险：所有条目共享同一个包络
}

for (Geometry g : geometries) {
    tree.insert(g.getEnvelopeInternal(), g);   // 几何自带包络，只读使用
}

public void insert(Envelope itemEnv, Object item) {
    if (itemEnv.isNull()) { return; }   // 空包络直接丢弃
    super.insert(itemEnv, item);
}

import org.locationtech.jts.geom.Coordinate;
import org.locationtech.jts.geom.Envelope;
import org.locationtech.jts.index.quadtree.Quadtree;

public class DegenerateEnvelopeDemo {
    public static void main(String[] args) {
        Envelope pt = new Envelope(new Coordinate(5, 5));
        System.out.println("原始点包络: " + pt + ", width=" + pt.getWidth());
        System.out.println("isNull=" + pt.isNull());

        Quadtree qt = new Quadtree();
        qt.insert(pt, "A");
        System.out.println("Quadtree.size=" + qt.size() + ", query=" + qt.query(pt));

        STRtreeInsertDemo();
    }

    private static void STRtreeInsertDemo() {
        org.locationtech.jts.index.strtree.STRtree tree =
            new org.locationtech.jts.index.strtree.STRtree();
        tree.insert(new Envelope(), "empty");          // 空包络被忽略
        tree.insert(new Envelope(new Coordinate(1, 1)), "point");
        System.out.println("STRtree.size=" + tree.size());
    }
}

import java.util.List;

import org.locationtech.jts.geom.Envelope;
import org.locationtech.jts.geom.Geometry;
import org.locationtech.jts.geom.GeometryFactory;
import org.locationtech.jts.index.strtree.GeometryItemDistance;
import org.locationtech.jts.index.strtree.STRtree;
import org.locationtech.jts.io.WKTReader;

public class STRtreeBasicDemo {
    public static void main(String[] args) throws Exception {
        WKTReader reader = new WKTReader();
        GeometryFactory gf = new GeometryFactory();
        STRtree tree = new STRtree();

        String[] wkts = {
            "POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0))",
            "POLYGON ((20 0, 30 0, 30 10, 20 10, 20 0))",
            "POLYGON ((0 20, 10 20, 10 30, 0 30, 0 20))",
            "POLYGON ((20 20, 30 20, 30 30, 20 30, 20 20))"
        };
        for (String wkt : wkts) {
            Geometry g = reader.read(wkt);
            tree.insert(g.getEnvelopeInternal(), g);
        }

        // 1) 范围查询：返回 List
        Envelope q = new Envelope(5, 25, 5, 25);
        List hits = tree.query(q);
        System.out.println("范围查询命中：" + hits.size() + " 个");
        for (Object o : hits) {
            System.out.println("  " + ((Geometry) o).getEnvelopeInternal());
        }

        // 2) 最近邻：查询对象不必在索引里
        Geometry probe = gf.createPoint(new org.locationtech.jts.geom.Coordinate(12, 12));
        Object nearest = tree.nearestNeighbour(
            probe.getEnvelopeInternal(), probe, new GeometryItemDistance());
        System.out.println("最近邻：" + nearest);

        // 3) k 近邻：返回按距离由近到远排列的数组
        Object[] knn = tree.nearestNeighbour(
            probe.getEnvelopeInternal(), probe, new GeometryItemDistance(), 3);
        System.out.println("k=3 近邻个数：" + knn.length);
        for (Object o : knn) {
            System.out.println("  " + ((Geometry) o).getEnvelopeInternal()
                + " 距离=" + ((Geometry) o).distance(probe));
        }
    }
}

STRtree tree = new STRtree();
for (Geometry g : geometries) {
    tree.insert(g.getEnvelopeInternal(), g);
}
tree.build();          // 显式构建，之后只读
// 多线程共享 tree 做查询

import org.locationtech.jts.index.strtree.ItemBoundable;
import org.locationtech.jts.index.strtree.ItemDistance;

import org.locationtech.jts.geom.Geometry;

/**
 * 只按包络中心点距离计算的廉价度量。
 * 仅用于演示：这种度量不满足“包络距离下界”的前提时，
 * 剪枝可能得到错误结果。
 */
public class EnvelopeCentreDistance implements ItemDistance {
    @Override
    public double distance(ItemBoundable item1, ItemBoundable item2) {
        Geometry g1 = (Geometry) item1.getItem();
        Geometry g2 = (Geometry) item2.getItem();
        return g1.getEnvelopeInternal().centre()
            .distance(g2.getEnvelopeInternal().centre());
    }
}

STRtree tree = new STRtree();
Set<String> seen = new HashSet<String>();
for (Geometry g : geometries) {
    String id = (String) g.getUserData();
    if (!seen.add(id)) continue;         // 按业务主键去重
    tree.insert(g.getEnvelopeInternal(), g);
}

import java.util.List;

import org.locationtech.jts.geom.Envelope;
import org.locationtech.jts.geom.Geometry;
import org.locationtech.jts.index.quadtree.Quadtree;
import org.locationtech.jts.io.WKTReader;

public class QuadtreeDemo {
    public static void main(String[] args) throws Exception {
        WKTReader reader = new WKTReader();
        Quadtree tree = new Quadtree();

        String[] wkts = {
            "POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0))",
            "POLYGON ((20 0, 30 0, 30 10, 20 10, 20 0))",
            "POLYGON ((0 20, 10 20, 10 30, 0 30, 0 20))",
            "POLYGON ((20 20, 30 20, 30 30, 20 30, 20 20))"
        };
        for (String wkt : wkts) {
            Geometry g = reader.read(wkt);
            tree.insert(g.getEnvelopeInternal(), g);
        }

        Envelope window = new Envelope(5, 25, 5, 25);
        List hits = tree.query(window);
        System.out.println("size=" + tree.size() + ", query=" + hits.size()
            + ", depth=" + tree.depth() + ", queryAll=" + tree.queryAll().size());

        // 删除：Quadtree 支持动态维护
        Geometry first = reader.read(wkts[0]);
        boolean removed = tree.remove(first.getEnvelopeInternal(), first);
        System.out.println("remove=" + removed + ", size=" + tree.size()
            + ", query=" + tree.query(window).size());
    }
}

Geometry a = reader.read("POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0))");
Geometry b = reader.read("POLYGON ((10 0, 10 10, 0 10, 0 0, 10 0))");
System.out.println("a.equals(b)=" + a.equals(b));           // false
System.out.println("a.equalsTopo(b)=" + a.equalsTopo(b));   // true
System.out.println("a.equalsNorm(b)=" + a.equalsNorm(b));   // true 或 false，取决于规范化结果

public class SIRtree extends AbstractSTRtree {
    public void insert(double x1, double x2, Object item);
    public List query(double x);        // 查询包含点 x 的区间
    public List query(double x1, double x2);  // 查询与 [x1,x2] 相交的区间
}

import java.util.List;

import org.locationtech.jts.index.strtree.SIRtree;

public class SIRtreeDemo {
    public static void main(String[] args) {
        SIRtree tree = new SIRtree();
        tree.insert(1, 5, "A");
        tree.insert(3, 9, "B");
        tree.insert(20, 30, "C");

        System.out.println("query(4)  = " + tree.query(4));
        System.out.println("query(10) = " + tree.query(10));
        System.out.println("query(2,6)= " + tree.query(2, 6));
    }
}

public void insert(double min, double max, Object item) {
    if (root != null)
        throw new IllegalStateException("Index cannot be added to once it has been queried");
    leaves.add(new IntervalRTreeLeafNode(min, max, item));
}

public void query(double min, double max, ItemVisitor visitor);

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

import org.locationtech.jts.index.ItemVisitor;
import org.locationtech.jts.index.intervalrtree.SortedPackedIntervalRTree;

public class IntervalRTreeDemo {
    public static void main(String[] args) {
        SortedPackedIntervalRTree tree = new SortedPackedIntervalRTree();
        tree.insert(1, 5, "A");
        tree.insert(3, 9, "B");
        tree.insert(20, 30, "C");

        final List<Object> hits = new ArrayList<Object>();
        tree.query(4, 6, new ItemVisitor() {
            @Override
            public void visitItem(Object item) { hits.add(item); }
        });
        System.out.println("query(4,6)=" + hits);
    }
}

import org.locationtech.jts.geom.Coordinate;
import org.locationtech.jts.geom.Envelope;
import org.locationtech.jts.index.VertexSequencePackedRtree;

public class VertexRtreeDemo {
    public static void main(String[] args) {
        Coordinate[] pts = new Coordinate[] {
            new Coordinate(0, 0), new Coordinate(10, 0),
            new Coordinate(10, 10), new Coordinate(0, 10),
            new Coordinate(5, 5)
        };
        VertexSequencePackedRtree index = new VertexSequencePackedRtree(pts);
        int[] hits = index.query(new Envelope(4, 6, 4, 6));
        System.out.println("命中下标：");
        for (int i : hits) {
            System.out.println("  " + i + " -> " + pts[i]);
        }
    }
}

import java.util.List;

import org.locationtech.jts.geom.Coordinate;
import org.locationtech.jts.geom.Envelope;
import org.locationtech.jts.geom.GeometryFactory;
import org.locationtech.jts.geom.Point;
import org.locationtech.jts.index.hprtree.HPRtree;

public class HPRtreeDemo {
    public static void main(String[] args) {
        GeometryFactory gf = new GeometryFactory();
        HPRtree tree = new HPRtree();   // 默认节点容量 16

        for (int i = 0; i < 20; i++) {
            Point p = gf.createPoint(new Coordinate(i, 0));
            tree.insert(p.getEnvelopeInternal(), p);
        }
        System.out.println("size=" + tree.size());

        // 惰性构建；items 少于等于节点容量时不会建内部节点
        List hits = tree.query(new Envelope(5, 14, 0, 0));
        System.out.println("query(5..14)=" + hits.size());
        System.out.println("节点包络数=" + tree.getBounds().length);
    }
}

import java.util.List;

import org.locationtech.jts.geom.Coordinate;
import org.locationtech.jts.geom.Envelope;
import org.locationtech.jts.index.kdtree.KdNode;
import org.locationtech.jts.index.kdtree.KdTree;

public class KdTreeDemo {
    public static void main(String[] args) {
        KdTree tree = new KdTree(0.5);       // 容差 0.5
        tree.insert(new Coordinate(0, 0), "P0");
        tree.insert(new Coordinate(1, 0), "P1");
        KdNode dup = tree.insert(new Coordinate(0.2, 0), "P2");

        System.out.println("size=" + tree.size() + ", depth=" + tree.depth());
        System.out.println("重合点 data=" + dup.getData() + ", count=" + dup.getCount());

        List hits = tree.query(new Envelope(-0.1, 0.2, -0.1, 0.1));
        System.out.println("query 命中节点数=" + hits.size());

        // 1.20 没有 getNodes()，想遍历全部节点就查一个大包络
        List all = tree.query(new Envelope(-1, 2, -1, 1));
        Coordinate[] coords = KdTree.toCoordinates(all, true);
        System.out.println("全部节点数=" + all.size()
            + ", 展开重复点后坐标数=" + coords.length);

        // 1.20 的 findBestMatchNode 是 private，手动找最近点
        Coordinate q = new Coordinate(0.9, 0.1);
        KdNode best = null;
        double bestDist = Double.MAX_VALUE;
        for (Object o : all) {
            KdNode n = (KdNode) o;
            double d = n.getCoordinate().distance(q);
            if (d < bestDist) {
                bestDist = d;
                best = n;
            }
        }
        System.out.println("最近点=" + best.getCoordinate() + ", 距离=" + bestDist);

        // 点等值查询：按 snap 后的存储坐标查，按原始坐标查会返回 null
        KdNode stored = tree.query(new Coordinate(0, 0));
        System.out.println("query(0,0)=" + (stored == null ? null : stored.getCoordinate()));
        KdNode inserted = tree.query(new Coordinate(0.2, 0));
        System.out.println("query(0.2,0)=" + (inserted == null ? null : inserted.getCoordinate()));
    }
}

// JTS 1.21+
KdNode nearest = tree.nearestNeighbor(new Coordinate(0.9, 0.1));
List<KdNode> nearest3 = tree.nearestNeighbors(new Coordinate(0.9, 0.1), 3);

public class MonotoneChain {
    public MonotoneChain(Coordinate[] pts, int start, int end, Object context);
    public Envelope getEnvelope();                 // 懒计算包络
    public Envelope getEnvelope(double expansionDistance); // 带外扩，供容差查询
    public void select(Envelope searchEnv, MonotoneChainSelectAction mcs);
    public void computeOverlaps(MonotoneChain mc, MonotoneChainOverlapAction mco);
    public void computeOverlaps(MonotoneChain mc, double overlapTolerance,
                                MonotoneChainOverlapAction mco);
}

import java.util.List;

import org.locationtech.jts.geom.Coordinate;
import org.locationtech.jts.geom.Envelope;
import org.locationtech.jts.index.chain.MonotoneChain;
import org.locationtech.jts.index.chain.MonotoneChainBuilder;
import org.locationtech.jts.index.strtree.STRtree;

public class ChainIndexDemo {
    public static void main(String[] args) {
        Coordinate[] pts = new Coordinate[] {
            new Coordinate(0, 0), new Coordinate(1, 1), new Coordinate(2, 2),
            new Coordinate(3, 1), new Coordinate(4, 0), new Coordinate(4, -2)
        };

        STRtree index = new STRtree();
        List chains = MonotoneChainBuilder.getChains(pts, "road-1");
        for (Object o : chains) {
            MonotoneChain mc = (MonotoneChain) o;
            index.insert(mc.getEnvelope(), mc);
        }
        System.out.println("链数=" + chains.size());
        for (Object o : chains) {
            MonotoneChain mc = (MonotoneChain) o;
            System.out.println("  链 context=" + mc.getContext()
                + " 顶点范围=" + mc.getStartIndex() + ".." + mc.getEndIndex()
                + " env=" + mc.getEnvelope());
        }

        Envelope window = new Envelope(2.5, 4.1, -0.5, 1.1);
        System.out.println("窗口命中的链：");
        for (Object o : index.query(window)) {
            MonotoneChain mc = (MonotoneChain) o;
            System.out.println("  " + mc.getStartIndex() + ".." + mc.getEndIndex());
        }
    }
}

public class MemoryProbe {
    public static void main(String[] args) {
        System.gc();
        pause(300);
        long before = used();

        // 在这里构建索引
        Object index = buildIndex();

        System.gc();
        pause(300);
        long after = used();
        System.out.println("索引占用约 " + (after - before) / 1024 + " KB");
        System.out.println(index != null);
    }

    private static Object buildIndex() { return new Object(); }

    private static long used() {
        Runtime rt = Runtime.getRuntime();
        return rt.totalMemory() - rt.freeMemory();
    }

    private static void pause(long ms) {
        try { Thread.sleep(ms); } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
    }
}

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.locationtech.jts.geom.Coordinate;
import org.locationtech.jts.geom.Geometry;
import org.locationtech.jts.geom.GeometryFactory;
import org.locationtech.jts.geom.Point;
import org.locationtech.jts.index.strtree.STRtree;
import org.locationtech.jts.io.WKTReader;

public class SpatialJoinDemo {
    public static void main(String[] args) throws Exception {
        WKTReader reader = new WKTReader();
        GeometryFactory gf = new GeometryFactory();

        // 1. 面图层：四个 10x10 的网格，ID 即用户数据
        String[] zoneWkts = {
            "POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0))",
            "POLYGON ((10 0, 20 0, 20 10, 10 10, 10 0))",
            "POLYGON ((0 10, 10 10, 10 20, 0 20, 0 10))",
            "POLYGON ((10 10, 20 10, 20 20, 10 20, 10 10))"
        };
        STRtree zoneIndex = new STRtree();
        List<Geometry> zones = new ArrayList<Geometry>();
        for (int i = 0; i < zoneWkts.length; i++) {
            Geometry zone = reader.read(zoneWkts[i]);
            zone.setUserData("Z" + (i + 1));
            zones.add(zone);
            zoneIndex.insert(zone.getEnvelopeInternal(), zone);
        }

        // 2. 点图层：注意 (10,10) 落在四个网格的公共角点上
        double[][] coords = { {5, 5}, {15, 5}, {5, 15}, {15, 15}, {10, 10} };
        List<Point> points = new ArrayList<Point>();
        for (int i = 0; i < coords.length; i++) {
            Point p = gf.createPoint(new Coordinate(coords[i][0], coords[i][1]));
            p.setUserData("P" + (i + 1));
            points.add(p);
        }

        // 3. 点 -> 面：一次索引查询 + 精确谓词
        Map<String, Set<String>> zoneToPoints = new HashMap<String, Set<String>>();
        List<String> boundaryPoints = new ArrayList<String>();

        for (Point p : points) {
            List candidates = zoneIndex.query(p.getEnvelopeInternal());
            Set<String> matched = new HashSet<String>();
            for (Object o : candidates) {
                Geometry zone = (Geometry) o;
                if (!zone.intersects(p)) continue;
                matched.add((String) zone.getUserData());
                if (!zone.contains(p)) {
                    // intersects 为真但 contains 为假 => 点落在网格边界上
                    boundaryPoints.add((String) p.getUserData());
                }
            }
            for (String zid : matched) {
                if (!zoneToPoints.containsKey(zid)) {
                    zoneToPoints.put(zid, new HashSet<String>());
                }
                zoneToPoints.get(zid).add((String) p.getUserData());
            }
        }

        // 4. 统计输出
        int pairCount = 0;
        for (Map.Entry<String, Set<String>> e : zoneToPoints.entrySet()) {
            pairCount += e.getValue().size();
            System.out.println(e.getKey() + " -> " + e.getValue());
        }
        System.out.println("命中的唯一网格数=" + zoneToPoints.size());
        System.out.println("一对多配对数=" + pairCount);
        System.out.println("边界点（去重前）=" + boundaryPoints);
        System.out.println("边界点（去重后）=" + new HashSet<String>(boundaryPoints));
    }
}

STRtree pointIndex = new STRtree();
for (Point p : points) {
    pointIndex.insert(p.getEnvelopeInternal(), p);
}
for (Geometry zone : zones) {
    List candidates = pointIndex.query(zone.getEnvelopeInternal());
    int inside = 0;
    for (Object o : candidates) {
        if (zone.contains((Point) o)) inside++;
    }
    System.out.println(zone.getUserData() + " 内部点数=" + inside);
}

import org.locationtech.jts.geom.Geometry;
import org.locationtech.jts.operation.distance.IndexedFacetDistance;

public class NearestZoneDemo {
    public static void main(String[] args) throws Exception {
        // zones / probe 的构造省略，假设已有 Geometry 列表
        Geometry probe = new org.locationtech.jts.io.WKTReader().read("POINT (25 25)");
        double min = Double.MAX_VALUE;
        Geometry nearest = null;
        for (Geometry zone : zones) {
            double d = IndexedFacetDistance.distance(zone, probe);
            if (d < min) { min = d; nearest = zone; }
        }
        System.out.println("最近网格=" + nearest.getUserData() + ", 距离=" + min);
    }
}