1. ホーム
  2. 質問と答え
  3. どのように私はDijkstraまたはA *アルゴリズムを実装できるように私はエッジシステムを作ることができますか？

どのように私はDijkstraまたはA *アルゴリズムを実装できるように私はエッジシステムを作ることができますか？

2017-05-22 12 views
0

DijkstraのアルゴリズムをgeoJsonファイルで提供されている機能のリストに適用したいのですが、最大100個の機能があります。どのように私はDijkstraまたはA *アルゴリズムを実装できるように私はエッジシステムを作ることができますか？

  1. 抽出されたすべてのポイントを機能から、私はこの使用して索引のからポイントのような隣接リストを構築している

2.（変数がポイントと呼ばれる）：私はこれまでやっていること leaflet Dijkstra's algorithm so 0-1-10は、ポイントでインデックス0のポイントになり、1は同じ、3番目は互いに離れています。 3.隣接配列を構築しましたが、使用方法が表示されません 画像に表示されている例は、完全な機能ではありません。出発点のみを探しています。

  • 全て黒点iがダイクストラまたは*アルゴリズムを実装することができるように

    • がどのようにエッジ・システムを作ることができる（LAT、ラング）ある

    私の質問はどのように私はAからBに行くことができますか？ ご意見をお待ちしております。

    編集1：追加されたコード

    編集2：更新された質問

    \t var start = [34.000750, 71.485753]; 
 
      var end = [34.000937, 71.485180]; 
 
      
 
      \t var points=[]; 
 
      \t var nodes=[]; 
 
      \t var features=[]; 
 
      \t var adjacent=[]; 
 

 
      \t var map = L.map('map').setView(start, 17);; 
 

 
\t  map.attributionControl.addAttribution('<a href="https://github.com/tomchadwin/qgis2web" target="_blank">qgis2web</a>'); 
 
     var bounds_group = new L.featureGroup([]); 
 
     var basemap0 = L.tileLayer('http://{s}.tile.openstreetmap.org/{z}/{x}/{y}.png', { 
 
      attribution: '&copy; <a href="http://openstreetmap.org">OpenStreetMap</a> contributors,<a href="http://creativecommons.org/licenses/by-sa/2.0/">CC-BY-SA</a>', 
 
      maxZoom: 22 
 
     }); 
 
     basemap0.addTo(map); 
 
     L.geoJSON(data).addTo(map); 
 
\t  //OpenStreetMap_BlackAndWhite.addTo(map) 
 
    \t   //basemap0.addTo(map); 
 
      \t function getid(){ 
 
      \t \t var possible = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"; 
 
      \t \t var d = possible.charAt(Math.floor(Math.random() * possible.length)); 
 
      \t \t while(nodes.indexOf(d) >-1){ 
 
      \t \t \t d = possible.charAt(Math.floor(Math.random() * possible.length)); 
 
      \t \t } 
 
     \t \t return d; 
 
      \t } 
 
      L.geoJSON(data, { 
 
       onEachFeature: function(feature, layer) { 
 
        //console.log(feature); 
 
        points.push.apply(points,feature.geometry.coordinates); 
 
        features.push(feature.geometry.coordinates); 
 
        // return L.Polyline(layer, geojsonMarkerOptions); 
 
       } 
 
      }); 
 

 
      function init(){ 
 
      \t var marks= []; 
 
\t    for (var i = 0; i < features.length; i++) { 
 
\t     var s = features[i]; 
 

 
\t     //var m = L.marker([s[1],s[0]]); 
 
\t     //marks.push(m); 
 
\t     for (var j = 0; j < s.length; j++) { 
 
\t      var k = s[j]; 
 

 
\t      var m = L.marker([k[1],k[0]]); 
 
\t      m.on('click',function(e){ 
 
\t       console.log(this.getLatLng()); 
 
\t      }) 
 
\t      marks.push(m); 
 
\t     } 
 
\t     
 
\t    } 
 
\t    var heuristik 
 
\t    for (var i = 0; i < marks.length-1; i++) { 
 
\t     var lt = marks[i].getLatLng().distanceTo(marks[i+1].getLatLng()); 
 
\t     var a =i; 
 
\t     var b =i+1; 
 
\t     if(lt != 0){ 
 
\t     console.log(a,b,lt,); 
 

 
\t     adjacent.push([a,b,lt]); 
 
\t     } 
 
\t     //Array.prototype.push.apply(adjacent,{a,b,lt}); 
 
\t  
 
\t    } 
 
\t    //console.log(adjacent) 
 
      }
    html,body { 
 
\t \t width: 100%; 
 
\t \t height: 100%; 
 
\t \t overflow: hidden; 
 
\t } 
 
\t #map{ 
 
\t \t width: 100%; 
 
\t \t height: 100%; 
 
\t } \t
    <link rel="stylesheet" href="https://unpkg.com/[email protected]/dist/leaflet.css" /> 
 
<script src="https://unpkg.com/[email protected]/dist/leaflet.js"></script> 
 
<script src="https://raw.githubusercontent.com/andrewhayward/dijkstra/master/graph.js"></script> 
 
    
 
    \t \t <script></script> 
 
\t \t <script> 
 
    var data = { 
 
"type": "FeatureCollection", 
 
"crs": { "type": "name", "properties": { "name": "urn:ogc:def:crs:OGC:1.3:CRS84" } }, 
 
"features": [ 
 
{ "type": "Feature", "properties": { "Place": "Kmc Road" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.484445376090477, 34.000556224204104 ], [ 71.484619381903997, 34.00055622349123 ], [ 71.485795423886529, 34.000556218673154 ], [ 71.486389444907786, 34.000556088482497 ] ] } }, 
 
{ "type": "Feature", "properties": { "Place": "UET Main Road" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.486384748456004, 34.002041741407623 ], [ 71.485121131034504, 34.002036564553677 ], [ 71.484897906943033, 34.002035650037541 ], [ 71.484080666224514, 34.002032301923023 ] ] } }, 
 
{ "type": "Feature", "properties": { "Place": "Road 2" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.486389444907786, 34.000556088482497 ], [ 71.486384748456004, 34.002041741407623 ], [ 71.48638137935751, 34.003043552173651 ], [ 71.486380078137188, 34.003430473641167 ], [ 71.486380045906941, 34.003440057392226 ] ] } }, 
 
{ "type": "Feature", "properties": { "Place": "Hostel Road" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.486380078137188, 34.003430473641167 ], [ 71.484890807505366, 34.00343866205165 ], [ 71.483730352446614, 34.003445042545671 ] ] } }, 
 
{ "type": "Feature", "properties": { "Place": "Commerce College Road" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.483730352446614, 34.003445042545671 ], [ 71.483792886191907, 34.003192857311085 ], [ 71.484080666224514, 34.002032301923023 ], [ 71.484445376090477, 34.000556224204104 ] ] } }, 
 
{ "type": "Feature", "properties": { "Place": "Civil Engineering" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485795429415916, 34.000635421476822 ], [ 71.485793037373725, 34.000750625722446 ], [ 71.485761836269248, 34.000750627900693 ] ] } }, 
 
{ "type": "Feature", "properties": { "Place": "Structure Labs & Library" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485793037373725, 34.000750625722446 ], [ 71.485824238478202, 34.000750623544199 ] ] } }, 
 
{ "type": "Feature", "properties": { "Place": "Concrete Testing Lab" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485793037373725, 34.000750625722446 ], [ 71.485797844581057, 34.000851428955635 ], [ 71.485838646025371, 34.000851426107154 ], [ 71.485841053985538, 34.000964229932706 ] ] } }, 
 
{ "type": "Feature", "properties": { "Place": "Hydraulic Lab" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485797844581057, 34.000851428955635 ], [ 71.485800253043891, 34.000971433036057 ], [ 71.485783452449184, 34.000971434208964 ], [ 71.485785871468138, 34.001242643641845 ], [ 71.485809872317731, 34.001242641966272 ] ] } }, 
 
{ "type": "Feature", "properties": { "Place": "Civil Parking" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485795429415916, 34.000635421476822 ], [ 71.485529019817847, 34.000633039990753 ] ] } }, 
 
{ "type": "Feature", "properties": { "Place": "CS & IT" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485797844581057, 34.000851428955635 ], [ 71.485181022746431, 34.000851472017921 ], [ 71.485181028778499, 34.000937875076467 ] ] } }, 
 
{ "type": "Feature", "properties": { "Place": "Earthquake Center" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485181022746431, 34.000851472017921 ], [ 71.485181021908645, 34.000839471593132 ], [ 71.485181018725044, 34.000793869978892 ], [ 71.485046613967313, 34.000793879362114 ] ] } }, 
 
{ "type": "Feature", "properties": { "Place": "New Earthquake Center" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485181021908645, 34.000839471593132 ], [ 71.484837809926972, 34.000841895638814 ], [ 71.484837796857477, 34.000654689011959 ], [ 71.484837795852144, 34.000640288502204 ], [ 71.484621788205772, 34.000640303582379 ] ] } }, 
 
{ "type": "Feature", "properties": { "Place": "Girls Common Room" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485181028778499, 34.000937875076467 ], [ 71.485181035313246, 34.001031478389898 ], [ 71.485181040507527, 34.001105881023648 ] ] } }, 
 
{ "type": "Feature", "properties": { "Place": "Mechanical Engineering" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485181040507527, 34.001105881023648 ], [ 71.485181063088987, 34.001429336832032 ] ] } }, 
 
{ "type": "Feature", "properties": { "Place": "New Earthquake Gate" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.484621788205772, 34.000640303582379 ], [ 71.484619381903997, 34.00055622349123 ] ] } }, 
 
{ "type": "Feature", "properties": { "Place": "Civil Main Gate" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485795429415916, 34.000635421476822 ], [ 71.485795423886529, 34.000556218673154 ] ] } }, 
 
{ "type": "Feature", "properties": { "Place": "New Academic Block" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485181063088987, 34.001429336832032 ], [ 71.485125861392447, 34.001433029533452 ], [ 71.485128269185054, 34.001543433274037 ], [ 71.48599229960297, 34.001540972868369 ], [ 71.485982728920817, 34.001965788576456 ], [ 71.485677917963386, 34.001963409771299 ], [ 71.485663520302097, 34.00200421222096 ], [ 71.485557916396317, 34.002001819508536 ], [ 71.485567513887673, 34.001961017393988 ], [ 71.485118698167781, 34.001963448812212 ], [ 71.485125876678964, 34.001651992925943 ], [ 71.485128269352614, 34.001545833359003 ] ] } }, 
 
{ "type": "Feature", "properties": { "Place": "Tennis Lawn" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485181035313246, 34.001031478389898 ], [ 71.484926626229907, 34.001030384828667 ], [ 71.484926669794874, 34.001654406918178 ], [ 71.485125876678964, 34.001651992925943 ] ] } }, 
 
{ "type": "Feature", "properties": { "Place": "Agriculture Engineering" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.484897906943033, 34.002035650037541 ], [ 71.484890084806153, 34.002365054141571 ], [ 71.484888323226841, 34.002439237380912 ] ] } }, 
 
{ "type": "Feature", "properties": { "Place": "Chemical & Industrial Egineering" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.484888323226841, 34.002439237380912 ], [ 71.484883546063472, 34.002768782456975 ] ] } }, 
 
{ "type": "Feature", "properties": { "Place": "Main Gate Entrance" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485118698167781, 34.001963448812212 ], [ 71.485121131034504, 34.002036564553677 ] ] } }, 
 
{ "type": "Feature", "properties": { "Place": "Computer System Parking" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.484883546063472, 34.002768782456975 ], [ 71.484888363916895, 34.003022079805255 ], [ 71.484600352381278, 34.003002899232484 ] ] } }, 
 
{ "type": "Feature", "properties": { "Place": "Computer System Engineering" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.484888363916895, 34.003022079805255 ], [ 71.484888365089802, 34.003038880399977 ], [ 71.48488837681883, 34.003206886347151 ] ] } }, 
 
{ "type": "Feature", "properties": { "Place": "Hostel Road Entrance" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.48488837681883, 34.003206886347151 ], [ 71.484888930241823, 34.003259657448353 ], [ 71.484890807505366, 34.00343866205165 ] ] } }, 
 
{ "type": "Feature", "properties": { "Place": "Canteen" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.484888930241823, 34.003259657448353 ], [ 71.485097187393905, 34.003252473383881 ] ] } }, 
 
{ "type": "Feature", "properties": { "Place": "High Tension Lab" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.484888365089802, 34.003038880399977 ], [ 71.485572389638421, 34.003043632815995 ] ] } }, 
 
{ "type": "Feature", "properties": { "Place": "New Admin Block (CMS)" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485572389638421, 34.003043632815995 ], [ 71.485975604079186, 34.00304600475129 ] ] } }, 
 
{ "type": "Feature", "properties": { "Place": "Road 2 Gate" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485975604079186, 34.00304600475129 ], [ 71.486088447014453, 34.003045322708608 ], [ 71.48638137935751, 34.003043552173651 ] ] } }, 
 
{ "type": "Feature", "properties": { "Place": "VC Lawn" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.486088447014453, 34.003045322708608 ], [ 71.486085990058683, 34.002789187952963 ] ] } }, 
 
{ "type": "Feature", "properties": { "Place": "Electrical Engineering" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485572389638421, 34.003043632815995 ], [ 71.485569981549489, 34.002928984566658 ] ] } }, 
 
{ "type": "Feature", "properties": { "Place": "Provost Office" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.486085990058683, 34.002789187952963 ], [ 71.486090753237178, 34.00225932450293 ], [ 71.485711539310884, 34.002252150722143 ], [ 71.485469132237981, 34.002273768410092 ], [ 71.485303533078067, 34.00236978336995 ], [ 71.485121126788684, 34.002372196189278 ] ] } }, 
 
{ "type": "Feature", "properties": { "Place": "Electrical Lawn" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.485121126788684, 34.002372196189278 ], [ 71.484890084806153, 34.002365054141571 ] ] } }, 
 
{ "type": "Feature", "properties": { "Place": "Director of Works" }, "geometry": { "type": "LineString", "coordinates": [ [ 71.483792886191907, 34.003192857311085 ], [ 71.483894742186976, 34.003214711632012 ] ] } } 
 
] 
 
} 
 

 
    </script> 
 
    
 
    
 
\t 
 
\t <div id="map"> 
 
\t \t 
 
\t </div> 
 
\t

    出典

    2017-05-22 sdx11

    +0

    だから、問題は何ですか？任意のコードまたは実際の問題がなければ、我々はあなたがきっとすでに見てきたダイクストラの作品は、あなたが持っていないどのように再反復以上のことをすることはできませんか？また、スタートとゴールの両方を持っているようだから、ダイクストラの代わりにA *を使うのはどうですか？ –

    +0

    は@tobias_kはい私がしたが、ハードの部分は、各エッジのコストを考え出すと目標に動いている、私は*のおかげで試してみて、質問 – sdx11

    +0

    を更新します私は本当ににGeoJSONを知らないが、それは地理座標だ場合には、 2点間のユークリッド距離を使ってエッジコストとして使うことはできませんか？ （そこ球面上の距離を計算するより複雑な方法もありますが、短い距離のために、これは十分に良いことがあります。） –

    答えて

    1

    ご質問は広すぎます。あなたはプラットフォームを指定しません（Webブラウザで最短パスを計算するのはJSバックエンドで、GeoJSONカラムを持つPostGIS DBテーブルでですか？）ので、私たちに推測されます。リーフレットはさまざまなデータソースからデータを読み込むことができるため、リーフレットの機能は情報を追加しないことに注意してください。また、フロントエンド側で最短パスを計算することを保証するものでもありません。

    何百もの経路探索アルゴリズムの実装のはそう、すでにあります

    ウェブブラウザ

    出典

    2017-05-23 09:26:41 IvanSanchez

    +0

    ありがとう、私はパーLiedmanのからにGeoJSONパスファインダーは、私はにGeoJSONパスファインダーを試してみました、私 – sdx11

    +0

    ための正しい選択だと思いますLiedmanのそれは私のためには機能しません+ドキュメントの欠如、私はエッジシステムを使用して自分のアルゴリズムを構築するのが好きです、どのように私はその提案を行うことができますか？ 、私のエッジシステムは間違っています！ 、私は2つのノードの間のエッジであるために連続するノードでリレーできません – sdx11

    関連する問題

     関連する問題