空間索引（Spatial Indexing）

回憶下數(shù)據(jù)庫(kù)最基本的操作：增刪改查以及稍復(fù)雜些的比如連接操作，基本都需要先鎖定數(shù)據(jù)位置，再執(zhí)行操作。而定位這個(gè)步驟，如果沒(méi)有index，基本都是O(n)的時(shí)間復(fù)雜度，這是一個(gè)非?！昂臅r(shí)”的操作。“找”這個(gè)操作就需要定位。注意這里的定位不再是指在存儲(chǔ)器上的位置，而是在空間中的位置，這里的空間，是由數(shù)據(jù)的維度張成的空間。空間數(shù)據(jù)，也即是這些擁有多維度的數(shù)據(jù)。這是空間數(shù)據(jù)的一個(gè)比較延展性的說(shuō)法。但通常，空間數(shù)據(jù)都focus on 幾何類(lèi)型數(shù)據(jù)，比如點(diǎn)，線(xiàn)，面，球等，當(dāng)然這些點(diǎn)、線(xiàn)都是可以任意維度的。對(duì)于空間數(shù)據(jù)的搜索，我們需要空間索引spatial index來(lái)提升搜素效率（速度）。目前主流數(shù)據(jù)（SQL server,MySQL,PostgreSQL,etc）都已加入了對(duì)spatial data的支持，這其中最主要的就是數(shù)據(jù)類(lèi)型和索引的支持。

R-tree

MBR

為了統(tǒng)一描述空間類(lèi)型，比如點(diǎn)，線(xiàn)，面等，Guttman首先提出了MBR的概念，即Minimum Bounding Box。MBR的含義是用一個(gè)最小的矩形（通常默認(rèn)矩形的邊平行于坐標(biāo)軸），來(lái)框住這個(gè)幾何體。

MBR

R-tree

R-tree主要吸納了B+tree的思想，對(duì)數(shù)據(jù)進(jìn)行分割。

R-tree

JTS生成R樹(shù)索引

JTS提供了如下的空間數(shù)據(jù)類(lèi)型，還提供了讀取各種空間描述文件（WTK等），線(xiàn)簡(jiǎn)化，空間操作（求交，計(jì)算距離，計(jì)算外包矩形等），建立空間索引等多種算法。
參考這篇文章：https://blog.csdn.net/wk1134314305/article/details/76408181
引入依賴(lài)包：

// Gradle
compile group: 'com.vividsolutions', name: 'jts', version: '1.13'
// Maven
<dependency>
<groupId>com.vividsolutions</groupId>
    <artifactId>jts</artifactId>
    <version>1.13</version>
</dependency>

Geometry類(lèi)：所有的空間數(shù)據(jù)類(lèi)型，點(diǎn)，線(xiàn)，面，多點(diǎn)，環(huán)，多邊形等等都是繼承自Geometry類(lèi)的。
Envelope類(lèi)：該類(lèi)就是描述一個(gè)空間幾何對(duì)象的外包矩形，由max_x,max_y,min_x,min_y組成。

JTS常用的方法，以及R樹(shù)索引基本使用：

package com.geotools.geotoolsdemo;

import com.vividsolutions.jts.geom.*;
import com.vividsolutions.jts.io.ParseException;
import com.vividsolutions.jts.io.WKTReader;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.stereotype.Component;

/**
 * @program: geotoolsdemo
 * @description: JTS導(dǎo)入使用
 * @author: zhudan
 * @create: 2020/7/3 11:39
 */
@Component
public class GeometryDemo {
    //使用JTS的GeometryFactory來(lái)創(chuàng)建Geometry對(duì)象
    @Autowired
    private GeometryFactory geometryFactory = new GeometryFactory();

    /**
     * @Description: 創(chuàng)建一個(gè)點(diǎn)
     * @return: com.vividsolutions.jts.geom.Point
     */
    public Point createPoint() {
        Coordinate coord = new Coordinate(118.798128, 31.968592);
        Point point = geometryFactory.createPoint(coord);
        return point;
    }

    /**
     * @Description: 從WKT創(chuàng)建一個(gè)點(diǎn)，WKT字符串創(chuàng)建 ，WKT字符串是SQL標(biāo)準(zhǔn)定義的一個(gè)實(shí)現(xiàn)
     * @return: com.vividsolutions.jts.geom.Point
     */
    public Point createPointByWKT() throws ParseException {
        WKTReader reader = new WKTReader(geometryFactory);
        Point point = (Point) reader.read("POINT (118.798128 31.968592)");
        return point;
    }

    /**
     * @Description: 從WKT創(chuàng)建多個(gè)點(diǎn)
     * @return: com.vividsolutions.jts.geom.MultiPoint
     */
    @Autowired
    public MultiPoint createMulPointByWKT(String wellKnownText) throws ParseException {
        WKTReader reader = new WKTReader(geometryFactory);
//        MultiPoint mpoint = (MultiPoint) reader.read("MULTIPOINT(119.013388 31.715519, 119.32488 31.435678)");
        MultiPoint mpoint = (MultiPoint) reader.read(wellKnownText);
        return mpoint;
    }

    /**
     * @Description: create a line
     * @return: com.vividsolutions.jts.geom.LineString
     */
    public LineString createLine() {
        Coordinate[] coords = new Coordinate[]{new Coordinate(119.013388, 31.715519), new Coordinate(119.32488, 31.435678)};
        LineString line = geometryFactory.createLineString(coords);
        return line;
    }

    /**
     * @Description: create a line by WKT
     * @return: com.vividsolutions.jts.geom.LineString
     */
    public LineString createLineByWKT() throws ParseException {
        WKTReader reader = new WKTReader(geometryFactory);
        LineString line = (LineString) reader.read("LINESTRING(119.013388 31.715519, 119.32488 31.435678)");
        return line;
    }

    /**
     * @Description: create multiLine
     * @return: com.vividsolutions.jts.geom.MultiLineString
     */
    public MultiLineString createMLine() {
        Coordinate[] coords1 = new Coordinate[]{new Coordinate(119.013388, 31.715519), new Coordinate(119.32488, 31.435678)};
        LineString line1 = geometryFactory.createLineString(coords1);
        Coordinate[] coords2 = new Coordinate[]{new Coordinate(118.797499, 32.087104), new Coordinate(118.798128, 31.968592)};
        LineString line2 = geometryFactory.createLineString(coords2);
        LineString[] lineStrings = new LineString[2];
        lineStrings[0] = line1;
        lineStrings[1] = line2;
        MultiLineString ms = geometryFactory.createMultiLineString(lineStrings);
        return ms;
    }

    /**
     * @Description: create multiLine by WKT
     * @return: com.vividsolutions.jts.geom.MultiLineString
     */
    public MultiLineString createMLineByWKT() throws ParseException {
        WKTReader reader = new WKTReader(geometryFactory);
        MultiLineString line = (MultiLineString) reader.read("MULTILINESTRING((119.013388 31.715519, 119.32488 31.435678),(118.797499 32.087104,118.798128 31.968592))");
        return line;
    }

    /**
     * @Description: create a polygon(多邊形)
     * @return:
     */
    public Polygon createPolygon() {
        Coordinate[] coords = new Coordinate[]{new Coordinate(20, 10), new Coordinate(30, 0), new Coordinate(40, 10),
                new Coordinate(30, 20), new Coordinate(20, 10)};
        Polygon polygon = geometryFactory.createPolygon(coords);
        return polygon;
    }

    /**
     * @Description: create a polygon(多邊形) by WKT
     * @return:
     */
    public Polygon createPolygonByWKT() throws ParseException {
        WKTReader reader = new WKTReader(geometryFactory);
        Polygon polygon = (Polygon) reader.read("POLYGON((20 10, 30 0, 40 10, 30 20, 20 10))");
        return polygon;
    }

    /**
     * @Description: create multi polygon(多邊形) by WKT
     * @return:
     */
    public MultiPolygon createMulPolygonByWKT() throws ParseException {
        WKTReader reader = new WKTReader(geometryFactory);
        MultiPolygon mpolygon = (MultiPolygon) reader.read("MULTIPOLYGON(((40 10, 30 0, 40 10, 30 20, 40 10),(30 10, 30 0, 40 10, 30 20, 30 10)))");
        return mpolygon;
    }

    /**
     * @Description: create GeometryCollection  contain point or multiPoint or line or multiLine or polygon or multiPolygon
     * @return: com.vividsolutions.jts.geom.GeometryCollection
     */
    public GeometryCollection createGeoCollect() throws ParseException {
        LineString line = createLine();
        Polygon poly = createPolygonByWKT();
        Geometry g1 = geometryFactory.createGeometry(line);
        Geometry g2 = geometryFactory.createGeometry(poly);
        Geometry[] garray = new Geometry[]{g1, g2};
        GeometryCollection gc = geometryFactory.createGeometryCollection(garray);
        return gc;
    }

    /**
     * create a Circle  創(chuàng)建一個(gè)圓，圓心(x,y) 半徑RADIUS
     *
     * @param x
     * @param y
     * @param RADIUS
     * @return
     */
    public Polygon createCircle(double x, double y, final double RADIUS) {
        final int SIDES = 32;//圓上面的點(diǎn)個(gè)數(shù)
        Coordinate coords[] = new Coordinate[SIDES + 1];
        for (int i = 0; i < SIDES; i++) {
            double angle = ((double) i / (double) SIDES) * Math.PI * 2.0;
            double dx = Math.cos(angle) * RADIUS;
            double dy = Math.sin(angle) * RADIUS;
            coords[i] = new Coordinate((double) x + dx, (double) y + dy);
        }
        coords[SIDES] = coords[0];
        LinearRing ring = geometryFactory.createLinearRing(coords);
        Polygon polygon = geometryFactory.createPolygon(ring, null);
        return polygon;
    }

    /**
     * @param args
     * @throws ParseException
     */
    public static void main(String[] args) throws ParseException {
        GeometryDemo gt = new GeometryDemo();
        Polygon p1 = gt.createCircle(0, 1, 2);
        //圓上所有的坐標(biāo)(32個(gè))
//        Coordinate coords[] = p1.getCoordinates();
//        for (Coordinate coord : coords) {
//            System.out.println(coord.x + "," + coord.y);
//        }

        Polygon p2 = gt.createCircle(1, 0, 2);
        STRtree stRtree = new STRtree();
        stRtree.insert(p1.getEnvelopeInternal(), p1);
        stRtree.insert(p2.getEnvelopeInternal(), p2);

        List results = stRtree.query(new Envelope(0, 0, 0, 0));
        for (int i = 0; i < results.size(); i++) {
            System.out.println(results.get(i));
        }
    }
}

參考：
https://zhuanlan.zhihu.com/p/38597148
https://blog.csdn.net/wk1134314305/article/details/76408181