【JTS】利用JTS生成R樹索引

前言

因為，筆者最近在做一個大資料量地圖線上展示的項目，是以需要利用一些手段來提升效率，例如地圖縮放的時候，需要展示浏覽器視窗下的實時點位，軌迹等資訊。在大比例尺下（也就是放大級别較大的時候），是以隻需要展示目前這個視窗大小内的資料。那麼怎麼知道目前視窗大小内的有哪些點位資訊呢，這個時候，R樹的索引就出現了，可以很好地解決這個問題。利用一個矩形框（浏覽器視窗大小）來進行R樹索引就可以找出矩形框内的點位了。

R樹索引是一種空間資料索引，具有高效的特點，在現實生活中，R樹可以用來存儲地圖上的空間資訊，例如餐館位址，或者地圖上用來構造街道，建築，湖泊邊緣和海岸線的多邊形。然後可以用它來回答“查找距離我2千米以内的博物館”，“檢索距離我2千米以内的所有路段”（然後顯示在導航系統中）或者“查找（直線距離）最近的加油站”這類問題。R樹還可以用來加速使用包括大圓距離在内的各種距離度量方式的最鄰近搜尋。

具體原理和用途可以參考下面兩個網頁：

R樹維基百科

R樹索引原理

而目前有很多成熟的第三方庫提供了這個功能，例如本文用到的JTS。

JTS的開發文檔和相應的jar包的下載下傳位址：JTS下載下傳

JTS提供了如下的空間資料類型，還提供了讀取各種空間描述檔案（WTK等），線簡化，空間操作（求交，計算距離，計算外包矩形等），建立空間索引等多種算法。

Point

MultiPoint

LineString

LinearRing 封閉的線條

MultiLineString 多條線

Polygon

MultiPolygon

GeometryCollection 包括點，線，面

裡面最主要的幾個類，GeometryFactory，Geometry，Envelope以及上面提到的幾種常用資料類型。

因為本文中主要用到空間索引和空間拓撲關系的計算，是以下面重點講解一下相關的内容。

1，幾個概念

Geometry類：所有的空間資料類型，點，線，面，多點，環，多邊形等等都是繼承自Geometry類的。

Envelope類：該類就是描述一個空間幾何對象的外包矩形，由max_x,max_y,min_x,min_y組成。

2，空間關系

空間關系主要是由九交模型來描述的，九交模型的講解可以參考：九交模型的講解

至于在JTS中的對應的關系，就是以下幾種：

【JTS】利用JTS生成R樹索引

3，空間索引

空間索引有很多種，下面就介紹網格索引和R樹索引，這部分很成熟，網格索引是最原始的空間索引了，R樹稍微“時髦”一點，效率更高。

這兩個可以參看：

地理資訊系統原理線上教程——空間索引

深入淺出空間索引：為什麼需要空間索引

深入淺出空間索引：2

相應的，如何利用JTS實作R樹索引呢？

以下是相應的代碼

SpatialUtil.java

package util;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map.Entry;

import com.vividsolutions.jts.geom.Coordinate;
import com.vividsolutions.jts.geom.CoordinateSequences;
import com.vividsolutions.jts.geom.Envelope;
import com.vividsolutions.jts.geom.Geometry;
import com.vividsolutions.jts.geom.GeometryFactory;
import com.vividsolutions.jts.geom.LineString;
import com.vividsolutions.jts.geom.LinearRing;
import com.vividsolutions.jts.geom.MultiPoint;
import com.vividsolutions.jts.geom.Polygon;
import com.vividsolutions.jts.geom.impl.CoordinateArraySequence;
import com.vividsolutions.jts.index.strtree.STRtree;

import config.GeoConfig;
import dao.QueryTrail;
import entity.CompareValue;
import entity.GPSPoint;
import entity.Grid;
import entity.Line;
import entity.Point;
import io.vertx.core.Vertx;
import io.vertx.core.buffer.Buffer;
import io.vertx.core.json.JsonObject;
import io.vertx.ext.web.client.HttpResponse;
import io.vertx.ext.web.client.WebClient;

public class SpatialUtil {
    static String result=new String();
    //下面是我用高德地圖API和JTS求解武漢市的邊界多邊形之後，求解出的武漢的外包矩形範圍（裡面用了vertx中的client）
    public static void getPolygonofWuhan(String[] args) {
        Vertx vertx = Vertx.vertx();
        WebClient client = WebClient.create(vertx);
        client.get(80, "restapi.amap.com",
                "/v3/config/district?keywords=%E6%AD%A6%E6%B1%89&subdistrict=0&key=高德地圖API申請的Token&extensions=all")
                .send(ar -> {
                    if (ar.succeeded()) {
                        // Obtain response
                        HttpResponse<Buffer> response = ar.result();
                        result = response.bodyAsString();
                        JsonObject jo = new JsonObject(result);
                        result = jo.getJsonArray("districts").getJsonObject(0).getString("polyline");
                        GeometryFactory factory=new GeometryFactory();
                        String[] xyStrings=result.replace("|", ";").split(";");
                        List<Coordinate> list=new ArrayList<>();
                        for(String xy:xyStrings){
                            String[] s_arr=xy.split(",");
                            double[] d_xy=new double[2];
                            d_xy[0]=Double.parseDouble(s_arr[0]);
                            d_xy[1]=Double.parseDouble(s_arr[1]);
                            Coordinate coor=new Coordinate(d_xy[0], d_xy[1]);
                            list.add(coor);
                        }
                        Coordinate[] coor_arr=list.toArray(new Coordinate[0]);
                        MultiPoint multiPoint=factory.createMultiPoint(coor_arr);
                        Geometry env=multiPoint.getEnvelope();
                        Coordinate[] MBR=env.getCoordinates();
                        for(int i=0;i<MBR.length;i++){
                            System.out.println(MBR[i].x+","+MBR[i].y);
                        }
                        client.close();
                        vertx.close();
                    } else {
                        System.out.println("Something went wrong " + ar.cause().getMessage());
                    }
                });
    }
    /**
     * 計算兩點的距離差在哪個門檻值範圍内
     * @param pt1
     * @param pt2
     * @param config    門檻值的設定
     * @return
     */
    public static CompareValue inTolerance(Point pt1,Point pt2,GeoConfig config){
        double delta=Math.sqrt(Math.pow(pt1.getX()-pt2.getX(),2)+Math.pow(pt1.getY()-pt2.getY(), 2));
        double max=config.getMaxGeoRange();
        double min=config.getMinGeoRange();
        if(delta<min){
            return CompareValue.LT;
        }else if(delta<=max&&delta>=min){
            return CompareValue.IN;
        }else{
            return CompareValue.GT;
        }
    }
    /**
     * 建立網格
     * @return
     */
    public static HashMap<String,Grid> createGrids(){
        HashMap<String,Grid> gridMap=new HashMap<>();
        double left_top_x=Double.parseDouble(PropertiesUtil.getProperties("common", "left-top").split(",")[0]);
        double left_top_y=Double.parseDouble(PropertiesUtil.getProperties("common", "left-top").split(",")[1]);
        double right_bottom_x=Double.parseDouble(PropertiesUtil.getProperties("common", "right-bottom").split(",")[0]);
        double right_bottom_y=Double.parseDouble(PropertiesUtil.getProperties("common", "right-bottom").split(",")[1]);
        int rows=Integer.parseInt(PropertiesUtil.getProperties("common", "rows"));
        int cols=Integer.parseInt(PropertiesUtil.getProperties("common", "cols"));
        double interval_x=Double.parseDouble(ParseDataType.parseD2s((right_bottom_x-left_top_x)/(cols*1.0),6));
        double interval_y=Double.parseDouble(ParseDataType.parseD2s((left_top_y-right_bottom_y)/(rows*1.0),6));
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                Grid grid=new Grid();
                grid.setCol(cols);
                grid.setRow(rows);
                grid.setIndex(i*cols+j+1);
                Point lefttop=new Point();
                Point rightbottom=new Point();
                lefttop.setX(left_top_x+j*interval_x);
                lefttop.setY(left_top_y-i*interval_y);
                if(j==cols-1){
                    rightbottom.setX(right_bottom_x);
                }else{
                    rightbottom.setX(left_top_x+(j+1)*interval_x);
                }
                if(i==rows-1){
                    rightbottom.setY(right_bottom_y);
                }else{
                    rightbottom.setY(left_top_y-(i+1)*interval_y);
                }
                grid.setLefttop(lefttop);
                grid.setRightbottom(rightbottom);
                gridMap.put(String.valueOf(grid.getRow())+"_"+String.valueOf(grid.getCol())+"_"+String.valueOf(grid.getIndex()),grid);
            }
        }
        return gridMap;
    }

    /**
     * 建立網格索引
     */
    public static HashMap<String, Grid> createGridIndex(){

        HashMap<String, Grid> gridmap=createGrids();

        int cols=Integer.parseInt(PropertiesUtil.getProperties("common", "cols"));
        int rows=Integer.parseInt(PropertiesUtil.getProperties("common", "rows"));
        String rbPt_s=PropertiesUtil.getProperties("common", "right-bottom");
        Point rbPt=new Point();
        rbPt.setX(Double.parseDouble(rbPt_s.split(",")[0]));
        rbPt.setY(Double.parseDouble(rbPt_s.split(",")[1]));
        String ltPt_s=PropertiesUtil.getProperties("common", "left-top");
        Point ltPt=new Point();
        ltPt.setX(Double.parseDouble(ltPt_s.split(",")[0]));
        ltPt.setY(Double.parseDouble(ltPt_s.split(",")[1]));
        double range_x=rbPt.getX()-ltPt.getX();
        double range_y=ltPt.getY()-rbPt.getY();
        QueryTrail query=new QueryTrail();
        HashMap<String, Line> map=query.getLine();
        GeoConfig config=new GeoConfig();
        config.setMaxGeoRange(Double.parseDouble(PropertiesUtil.getProperties("common", "maxGeoRange")));
        config.setMinGeoRange(Double.parseDouble(PropertiesUtil.getProperties("common", "minGeoRange")));
        GeometryFactory factory=new GeometryFactory();
        for(Entry<String, Line> entry:map.entrySet()){
            Line templine=entry.getValue().sort(true);
            List<Line> list=templine.filter(config);
            for(Line line:list){
                List<GPSPoint> gpslist=line.getCoors();
                List<Coordinate> coors=new ArrayList<>();
                for(GPSPoint xy:gpslist){
                    double x=xy.getX();
                    double y=xy.getY();
                    Coordinate coor=new Coordinate(x, y);
                    coors.add(coor);
                }
                Coordinate[] coor_arr=coors.toArray(new Coordinate[0]);
                if(coor_arr.length>1){
                    LineString l_s=factory.createLineString(coor_arr);
                    Envelope env=l_s.getEnvelopeInternal();
                    double max_x=env.getMaxX();
                    double min_x=env.getMinX();
                    double max_y=env.getMaxY();
                    double min_y=env.getMinY();
                    int max_j=(int)((max_x-ltPt.getX())/range_x*cols);
                    int max_i=(int)((ltPt.getY()-max_y)/range_y*rows);
                    int min_j=(int)((min_x-ltPt.getX())/range_x*cols);
                    int min_i=(int)((ltPt.getY()-min_y)/range_y*rows);
                    a:for(int i=max_i;i<=min_i;i++){
                        for(int j=min_j;j<=max_j;j++){
                            Grid grid=gridmap.get(String.valueOf(rows)+"_"+String.valueOf(cols)+"_"+String.valueOf(i*cols+j+1));
                            Coordinate[] coor_arr1=new Coordinate[5];
                            coor_arr1[0]=new Coordinate(grid.getLefttop().getX(), grid.getLefttop().getY());
                            coor_arr1[1]=new Coordinate(grid.getLefttop().getX(), grid.getRightbottom().getY());
                            coor_arr1[2]=new Coordinate(grid.getRightbottom().getX(), grid.getRightbottom().getY());
                            coor_arr1[3]=new Coordinate(grid.getRightbottom().getX(), grid.getLefttop().getY());
                            coor_arr1[4]=new Coordinate(grid.getLefttop().getX(), grid.getLefttop().getY());
                            CoordinateArraySequence seq=new CoordinateArraySequence(coor_arr1);
                            LinearRing ring = new LinearRing(seq, new GeometryFactory());
                            Polygon poly=new Polygon(ring, null, new GeometryFactory());
                            if(l_s.crosses(poly)||poly.covers(l_s)){
                                grid.addLine(line);
                                break a;
                            }
                        }
                    }
                }else{
                    GPSPoint point=gpslist.get(0);
                    int j=(int)((point.getX()-ltPt.getX())/range_x*cols);
                    int i=(int)((ltPt.getY()-point.getY())/range_y*rows);
                    Grid grid=gridmap.get(String.valueOf(rows)+"_"+String.valueOf(cols)+"_"+String.valueOf(i*cols+j+1));
                    grid.addLine(line);
                }
            }
        }
        System.out.println("網格索引建立成功！");
        return gridmap;
    }


    /**
     * 建立R樹索引
     * @return
     */
    public static STRtree createRtree(){
        QueryTrail query=new QueryTrail();
        HashMap<String, Line> map=query.getLine();
        GeoConfig config=new GeoConfig();
        config.setMaxGeoRange(Double.parseDouble(PropertiesUtil.getProperties("common", "maxGeoRange")));
        config.setMinGeoRange(Double.parseDouble(PropertiesUtil.getProperties("common", "minGeoRange")));
        STRtree tree=new STRtree();
        for(Entry<String, Line> entry:map.entrySet()){
            Line templine=entry.getValue().sort(true);
            List<Line> list=templine.filter(config);
            for(Line line:list){
                GeometryFactory factory=new GeometryFactory();
                List<Coordinate> coors=new ArrayList<>();
                List<GPSPoint> gpslist=line.getCoors();
                for(GPSPoint xy:gpslist){
                    double x=xy.getX();
                    double y=xy.getY();
                    Coordinate coor=new Coordinate(x, y);
                    coors.add(coor);
                }
                Coordinate[] coor_arr=coors.toArray(new Coordinate[0]);
                if(coor_arr.length>1){
                    LineString lineStr=factory.createLineString(coor_arr);
                    Envelope env=lineStr.getEnvelopeInternal();
                    tree.insert(env, lineStr);
                }else{
                    com.vividsolutions.jts.geom.Point point=factory.createPoint(coor_arr[0]);
                    Envelope env=point.getEnvelopeInternal();
                    tree.insert(env, point);
                }
            }
        }
        tree.build();
        System.out.println("R樹索引建立成功！");
        return tree;
    }
    /**
     * R樹查詢
     * @param tree
     * @param searchGeo
     * @return
     */
    public static List<Geometry> query(STRtree tree,Geometry searchGeo){
        List <Geometry> result=new ArrayList<>();
        @SuppressWarnings("rawtypes")
        List list=tree.query(searchGeo.getEnvelopeInternal());
        for(int i=0;i<list.size();i++){
            Geometry lineStr=(Geometry)list.get(i);
            if(lineStr.intersects(searchGeo)){
                result.add(lineStr);
            }
        }
        return result;
    }
    //根據兩點生成矩形搜尋框
    public static Geometry generateSearchGeo(double left_top_x,double left_top_y,double right_bottom_x,double right_bottom_y){
        Coordinate[] coors=new Coordinate[4];
        coors[0]=new Coordinate(left_top_x, left_top_y);
        coors[1]=new Coordinate(right_bottom_x, left_top_y);
        coors[2]=new Coordinate(left_top_x, right_bottom_y);
        coors[3]=new Coordinate(right_bottom_x, right_bottom_y);
        LinearRing ring=new LinearRing(new CoordinateArraySequence(coors),new GeometryFactory());
        return ring;
    }

}

common.properties：

#兩點間最大間隔(經緯度內插補點，目前按照江的寬度)
maxGeoRange=0.002
#maxGeoRange=0.012
#兩點間最小間隔(經緯度內插補點，目前按照地圖上一棟樓的寬度)
minGeoRange=0.0005
#minGeoRange=0.0017
#武漢市外包矩形的範圍
#左上角
left-top=113.702282,31.36127
#左下角
left-bottom=113.702282,29.969079
#右上角
right-top=115.082574,31.36127
#右下角
right-bottom=115.082574,29.969079
#設定的網格的行數
rows=10
#設定的網格的列數
cols=10
#坐标保留小數點後幾位
CoorAbs=10000

GPSPoint.java：

package entity;

import java.util.Date;

/**
 * 點，描述點的位置，所屬網格和所屬線條
 * @author KingWang
 *
 */
public class GPSPoint extends Point{
    private Date date=new Date();
    private Grid grid=new Grid();
    private Line line=new Line();

    public Date getDate() {
        return date;
    }
    public void setDate(Date date) {
        this.date = date;
    }
    public Grid getGrid() {
        return grid;
    }
    public void setGrid(Grid grid) {
        this.grid = grid;
    }
    public Line getLine() {
        return line;
    }
    public void setLine(Line line) {
        this.line = line;
    }

}

Grid.java：

package entity;

import java.util.HashSet;

public class Grid {
    private int index=0;
    private int col=0;
    private int row=0;
    private Point lefttop=new Point();
    private Point rightbottom=new Point();
    private HashSet<Line> set=new HashSet<>();
    public int getIndex() {
        return index;
    }
    public void setIndex(int index) {
        this.index = index;
    }
    public int getCol() {
        return col;
    }
    public void setCol(int col) {
        this.col = col;
    }
    public int getRow() {
        return row;
    }
    public void setRow(int row) {
        this.row = row;
    }
    public Point getLefttop() {
        return lefttop;
    }
    public void setLefttop(Point lefttop) {
        this.lefttop = lefttop;
    }
    public Point getRightbottom() {
        return rightbottom;
    }
    public void setRightbottom(Point rightbottom) {
        this.rightbottom = rightbottom;
    }
    public HashSet<Line> getSet() {
        return set;
    }
    public void setSet(HashSet<Line> set) {
        this.set = set;
    }
    public void addLine(Line line){
        this.set.add(line);
    }
}

Line.java：

package entity;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;
import java.util.concurrent.CopyOnWriteArrayList;

import config.GeoConfig;
import util.SpatialUtil;
/**
 * 線，點串，描述整條軌迹
 * @author KingWang
 *
 */
public class Line {
    /**
     * 軌迹的id
     */
    private String id="";
    /**
     * 按照順序存儲點軌迹
     */
    private List<GPSPoint> coors=new ArrayList<>();
    /**
     * 經過的網格，按照軌迹順序存儲
     */
    private List<Grid> grids=new ArrayList<>();

    public String getId() {
        return id;
    }
    public void setId(String id) {
        this.id = id;
    }
    public List<GPSPoint> getCoors() {
        return coors;
    }
    public void setCoors(List<GPSPoint> coors) {
        this.coors = coors;
    }
    public List<Grid> getGrids() {
        return grids;
    }
    public void setGrids(List<Grid> grids) {
        this.grids = grids;
    }
    public void addPoint(GPSPoint p){
        this.coors.add(p);
    }

    public void removePoint(int index){
        this.coors.remove(index);
    }

    public Line sort(boolean isTimeAsc){
        List<GPSPoint> list=this.getCoors();
        Collections.sort(list, (point1,point2)->{
            if(point1.getDate().after(point2.getDate())){
                if(isTimeAsc){
                    return 1;
                }else{
                    return -1;
                }
            }else{
                if(isTimeAsc){
                    return -1;
                }else{
                    return 1;
                }
            }
        });
        return this;
    }
    /**
     * 對線坐标串進行粗處理,太密的點删掉，太遠的點打斷成兩段
     * @param config
     * @return
     */
    public List<Line> filter(GeoConfig config){
        List<Line> resultList=new ArrayList<>();
        List<GPSPoint> list=new CopyOnWriteArrayList<>(this.getCoors());
        Point lastPt=new Point();
        int i=0;
        int lastCutIndex=0;
        for(GPSPoint point:list){
            if(i>0&&SpatialUtil.inTolerance(lastPt,point,config)==CompareValue.GT){
                List<GPSPoint> list_temp=new ArrayList<>();
                list_temp.addAll(list.subList(lastCutIndex, i));
                Line line_temp=new Line();
                line_temp.setCoors(list_temp);
                line_temp.setId(String.valueOf(System.currentTimeMillis()+new Random().nextInt(10)));
                resultList.add(line_temp);
                lastCutIndex=i;
            }else if(i>0&&SpatialUtil.inTolerance(lastPt, point, config)==CompareValue.LT){
                list.remove(i);
                i--;
            }
            lastPt=point;
            i++;
        }
        if(lastCutIndex==i){
            Line line_temp=new Line();
            line_temp.setCoors(this.getCoors());
            line_temp.setId(String.valueOf(System.currentTimeMillis()+new Random().nextInt(10)));
            resultList.add(line_temp);
        }else{
            List<GPSPoint> list_temp=new ArrayList<>();
            list_temp.addAll(list.subList(lastCutIndex, i));
            Line line_temp=new Line();
            line_temp.setCoors(list_temp);
            line_temp.setId(String.valueOf(System.currentTimeMillis()+new Random().nextInt(10)));
            resultList.add(line_temp);
        }
        return resultList;
    }
}

Point.java：

package entity;

import config.GeoConfig;

/**
 * 點，描述點的位置
 * @author KingWang
 *
 */
public class Point {
    private double x=0.0;
    private double y=0.0;

    public double getX() {
        return x;
    }

    public void setX(double x) {
        this.x = x;
    }

    public double getY() {
        return y;
    }

    public void setY(double y) {
        this.y = y;
    }
}

注：

這裡需要用到求解空間拓撲關系的函數。

具體參考部落客另外一篇文章關于拓撲關系的測試。

【JTS】利用JTS生成R樹索引

前言

1，幾個概念

2，空間關系

3，空間索引

JTS拓撲關系測試

繼續閱讀

關于Gradle配置的小結

Java小案例——随機數猜測随機數猜測

nginx location中斜線的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method