空間索引（Spatial Indexing）

回憶下數(shù)據(jù)庫最基本的操作：增刪改查以及稍復(fù)雜些的比如連接操作程奠，基本都需要先鎖定數(shù)據(jù)位置，再執(zhí)行操作祭钉。而定位這個步驟瞄沙，如果沒有index，基本都是O(n)的時間復(fù)雜度慌核，這是一個非尘嗑常“耗時”的操作】遄浚“找”這個操作就需要定位垫桂。注意這里的定位不再是指在存儲器上的位置，而是在空間中的位置粟按，這里的空間诬滩，是由數(shù)據(jù)的維度張成的空間〖卣空間數(shù)據(jù)碱呼，也即是這些擁有多維度的數(shù)據(jù)蒙挑。這是空間數(shù)據(jù)的一個比較延展性的說法宗侦。但通常，空間數(shù)據(jù)都focus on 幾何類型數(shù)據(jù)忆蚀，比如點矾利，線姑裂，面，球等男旗，當(dāng)然這些點舶斧、線都是可以任意維度的。對于空間數(shù)據(jù)的搜索察皇，我們需要空間索引spatial index來提升搜素效率（速度）茴厉。目前主流數(shù)據(jù)（SQL server,MySQL,PostgreSQL,etc）都已加入了對spatial data的支持，這其中最主要的就是數(shù)據(jù)類型和索引的支持什荣。

R-tree

MBR

為了統(tǒng)一描述空間類型矾缓，比如點，線稻爬，面等嗜闻，Guttman首先提出了MBR的概念，即Minimum Bounding Box桅锄。MBR的含義是用一個最小的矩形（通常默認(rèn)矩形的邊平行于坐標(biāo)軸）琉雳，來框住這個幾何體。

MBR

R-tree

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

R-tree

JTS生成R樹索引

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

// 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類：所有的空間數(shù)據(jù)類型抓半，點喂急，線，面笛求，多點廊移，環(huán)，多邊形等等都是繼承自Geometry類的探入。
Envelope類：該類就是描述一個空間幾何對象的外包矩形狡孔，由max_x,max_y,min_x,min_y組成。

JTS常用的方法蜂嗽，以及R樹索引基本使用：

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來創(chuàng)建Geometry對象
    @Autowired
    private GeometryFactory geometryFactory = new GeometryFactory();

    /**
     * @Description: 創(chuàng)建一個點
     * @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)建一個點苗膝，WKT字符串創(chuàng)建 ，WKT字符串是SQL標(biāo)準(zhǔn)定義的一個實現(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)建多個點
     * @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)建一個圓植旧，圓心(x,y) 半徑RADIUS
     *
     * @param x
     * @param y
     * @param RADIUS
     * @return
     */
    public Polygon createCircle(double x, double y, final double RADIUS) {
        final int SIDES = 32;//圓上面的點個數(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個)
//        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

利用JTS構(gòu)建R樹索引

利用JTS構(gòu)建R樹索引

空間索引（Spatial Indexing）

R-tree

MBR

R-tree

JTS生成R樹索引