2019年到現(xiàn)在還沒更過一篇，確實(shí)是這陣子趕項目，自個也一直處于打雜之中（前期項目調(diào)研拉馋、公司網(wǎng)絡(luò)調(diào)整、項目地圖制作等等）惨好。乘著五一空閑更一篇最近做的小栗子煌茴，希望能夠幫助到各位同學(xué)。

為什么會有這篇

作者在給一個園區(qū)做地圖時候日川，甲方有需求能夠針對這個園區(qū)進(jìn)行路徑規(guī)劃服務(wù)蔓腐，也即告知起止點(diǎn)（甚至途徑點(diǎn)），計算出一條路徑逗鸣。
這是一個典型的路徑規(guī)劃問題，各個地圖大廠都有路徑規(guī)劃服務(wù)绰精，但是針對園區(qū)內(nèi)還沒有撒璧。也有很多前輩基于pgRouting實(shí)現(xiàn)過，例如：基于pgrouting的任意兩點(diǎn)間的最短路徑查詢函數(shù)二
笨使，但是需要借助PostgreSQL卿樱、Postgis、GeoServer等硫椰。針對一個園區(qū)繁调，這些有點(diǎn)重萨蚕，工程施工也比較繁瑣。園區(qū)內(nèi)道路簡單蹄胰，節(jié)點(diǎn)也不算多岳遥，可以把Postgis替我們干的活我們自己做。
如果你正在做一個園區(qū)的最短路徑服務(wù)裕寨，并且希望服務(wù)輕量（不需要那么多依賴工具）這篇文章適合你浩蓉。

準(zhǔn)備工作

1、你有一個要做最短路徑規(guī)劃的園區(qū)平面圖（可能是甲方給你的CAD圖紙宾袜、或者你從OSM亦或百度高德谷歌地圖上臨摹的道路中心線Shp文件）捻艳，進(jìn)行空間配準(zhǔn)后將其導(dǎo)出為shp文件或geojson文件。

image.png

2庆猫、對這個文件進(jìn)行處理认轨，完成一部分Postgis替我們干的活。主要是給道路進(jìn)行編號月培、給道路節(jié)點(diǎn)進(jìn)行編號嘁字、給道路添加起止節(jié)點(diǎn)（引用道路節(jié)點(diǎn)）。生成兩個文件节视，暫且給它命名為（roadline拳锚、roadpoint）。
其屬性表如下

roadline.png

roadpoint.png

roadline是道路中心線的分段拌蜘，每條線段有由線段ID(ID)杆烁、起點(diǎn)編號(start)、終點(diǎn)編號(target)简卧、是否雙向(twoway)兔魂、權(quán)重(weight)構(gòu)成，其權(quán)重值即為路段長度举娩。

image.png

算法開發(fā)

Dijkstra是成熟的最短路徑算法，可以到github上找一個腳手架算法纹烹。把代碼下載并在本地調(diào)試页滚，它會幫助你理解該算法召边。
但是，github上的算法基本上是告訴你這條路徑應(yīng)該按什么樣的節(jié)點(diǎn)順序走裹驰，而我們的應(yīng)用中希望是獲得一條或者多條道路中心線（前端頁面最想獲得的就是一串道路中心線坐標(biāo)或者linestring 這樣的wkt）隧熙。所以我們得把算法改動一下，增加途徑的路段邦马。

構(gòu)造實(shí)體對象

首先是節(jié)點(diǎn)對象贱鼻，它包含這樣幾個字段，分別為節(jié)點(diǎn)編號滋将、節(jié)點(diǎn)相連的路段列表邻悬、節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)途經(jīng)路徑（由節(jié)點(diǎn)列表構(gòu)成）、節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)途經(jīng)的路段（由路段ID列表構(gòu)成）

public class Vertex implements Comparable<Vertex> {
    public String id; 
    public ArrayList<Edge> neighbours;
    public LinkedList<Vertex> path;
    public LinkedList<String> linkedgeid;
}

其次是路段對象随闽，它由起始節(jié)點(diǎn)父丰、終止節(jié)點(diǎn)、權(quán)重掘宪、雙向標(biāo)志位蛾扇、路段編號、路段Geometry對象構(gòu)成

public class Edge {
    public Vertex start;
    public Vertex target;
    public double weight;
    public String twoway;
    public String edgeid;
    public LineString lineString;
}

最后是圖魏滚，它就是由節(jié)點(diǎn)列表和路段列表構(gòu)成

public class Graph {
    private ArrayList<Vertex> vertices;
    private ArrayList<Edge> edges;
}

圖的初始化

Dijkstra算法最重要一步是圖的初始化工作镀首。
首先，讀取節(jié)點(diǎn)對應(yīng)的geojson文件鼠次，來初始化圖中的節(jié)點(diǎn)列表更哄。
其次，讀取路段對應(yīng)的geojson文件腥寇，構(gòu)建節(jié)點(diǎn)的連接關(guān)系成翩，并填充圖中的路段列表。（這里赦役，根據(jù)路段雙向標(biāo)志物進(jìn)行判斷麻敌，如果是雙向起止節(jié)點(diǎn)要添加兩次，如果是單向只添加一次）

算法實(shí)現(xiàn)

這部分可以參照postgis實(shí)現(xiàn)掂摔，把sql語句改寫為java代碼即可术羔。作者在這就直接上代碼。

    //輸入起點(diǎn)終點(diǎn)坐標(biāo)乙漓，計算最短路徑
    public static List calculateMinRoute(double startlon, double startlat, double endlon, double endlat, Graph graph) {
        List resultls = new ArrayList();
        Edge startEdge = calculateEdge(startlon, startlat, graph.getEdges());
        Edge endEdge = calculateEdge(endlon, endlat, graph.getEdges());
        List ss = calculatePath(startEdge.start, endEdge.start, graph);
        List st = calculatePath(startEdge.start, endEdge.target, graph);
        List ts = calculatePath(startEdge.target, endEdge.start, graph);
        List tt = calculatePath(startEdge.target, endEdge.target, graph);
        List<Edge> minls = ss;
        double minlenss = calculateWeight(ss);
        double minlenst = calculateWeight(st);
        double minlents = calculateWeight(ts);
        double minlentt = calculateWeight(tt);
        if(minlenss > minlenst) {
            minls = st;
        }
        if(minlenst > minlents) {
            minls = ts;
        }
        if(minlents > minlentt) {
            minls = tt;
        }

        LineMerger lineMerger = new LineMerger();
        List<Geometry> list = new ArrayList<Geometry>();
        list.add(startEdge.getLineString());
        for(Edge edge:minls) {
            if(edge.start.getId() != startEdge.start.getId() && edge.target.getId() != startEdge.target.getId()) {
                list.add(edge.getLineString());
            }
        }
        if(startEdge.start.getId() != endEdge.start.getId() && startEdge.target.getId() != endEdge.target.getId()) {
            list.add(endEdge.getLineString());
        }
        lineMerger.add(list);
        WKTWriter writer = new WKTWriter();
        //將所有線段進(jìn)行合并(如若首位坐標(biāo)不匹配级历，可能合并后不止一條線段)
        Collection<Geometry> mergerLineStrings = lineMerger.getMergedLineStrings();
        if(mergerLineStrings.size() == 1) {
            LocationIndexedLine mergeline=new LocationIndexedLine(mergerLineStrings.iterator().next());
            Coordinate spoint = new Coordinate(startlon, startlat);
            LinearLocation shere=mergeline.project(spoint);

            Coordinate epoint = new Coordinate(endlon, endlat);
            LinearLocation ehere=mergeline.project(epoint);

            LinearLocation temp;
            if(shere.compareTo(ehere) > 0) {
                temp = shere;
                shere = ehere;
                ehere = temp;
            }

            LineString result = (LineString)mergeline.extractLine(shere, ehere);
            resultls.add(writer.write(result));
        }
    }

這里用到來geotools中的linemerge功能（在此特別感謝polong，每每遇到問題都能從他那找到答案）

結(jié)果

讓前端幫我測試了一下簇秒，效果還不錯鱼喉。

image.png

image.png

image.png