subway/operation-simp.js at master · B515/subway · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
function dis_dis(x1, y1, x2, y2) {
  //直线距离
  var k = Math.PI / 180;
  var c =
    Math.cos(y1 * k) * Math.cos(y2 * k) * Math.cos((x1 - x2) * k) +
    Math.sin(y1 * k) * Math.sin(y2 * k);
  var d = 6371008 * Math.acos(c);
  return d;
}
function dis(x1, y1, x2, y2) {
  //曼哈顿距离
  var d1 = dis_dis(x1, y1, x2, y1);
  var d2 = dis_dis(x2, y1, x2, y2);
  return d1 + d2;
}


function minopen(open) {              //open表排序
  var minv = stopinfo[open[0]].f;
  var min = 0;
  var minn = stopinfo[open[0]].nm;
  // if(open==0) alert("xxx");
  for (var i = 0; i < open.length; i++) {
    if (stopinfo[open[i]].f < minv) {
      minv = stopinfo[open[i]].f;
      min = i;
      minn = stopinfo[open[i]].nm;
    } else continue;
  }
  open.unshift(minn);
  open.splice(min + 1, 1);
}

function nxtstp(n, i) {                       //下一站
  return stopinfo[stopinfo[n].fllwstop[i]];
}


function findpath() {
  clearcan();
  var open = [];
  var close = [];
  var start = document.getElementById("startstop").value;
  var aim = document.getElementById("aimstop").value;
  open.push(start); //起始节点放入open表
  stopinfo[start].g = 0; //初始化起点的g(x)
  stopinfo[start].h = 0; //初始化起点的h(x)
  stopinfo[start].f = 0; //初始化起点的f(x)
  while (open.length != 0) {
    //open表非空时循环
    n = open.shift(); //当前节点放入open表
    if (n == aim) {
      var result = [];

      var xxx = stopinfo[n].nm;
      xian(stopinfo[xxx].xx,stopinfo[xxx].yy,stopinfo[stopinfo[xxx].father].xx,stopinfo[stopinfo[xxx].father].yy);
      yuan(stopinfo[xxx].xx,stopinfo[xxx].yy);
      result.unshift("\n"+stopinfo[n].nm);
      while (xxx != start) {

        xian(stopinfo[xxx].xx,stopinfo[xxx].yy,stopinfo[stopinfo[xxx].father].xx,stopinfo[stopinfo[xxx].father].yy);
        xxx = stopinfo[stopinfo[xxx].father].nm;
        result.unshift("\n"+xxx+"\n");
        yuan(stopinfo[xxx].xx,stopinfo[xxx].yy);

	  }
	  document.getElementById("show").value=result.join('');

      return;
    } //找到目标节点时退出

    for (var i = 0; i < stopinfo[n].fllwstop.length; i++) {
      //循环m次（m为与此站相邻站点数）
      //下一站站名：nxtstp(n,i).nm
      if (open.indexOf(nxtstp(n, i).nm) > -1) {
        nxtstp(n, i).father = stopinfo[n].nm;
      }
      if (close.indexOf(nxtstp(n, i).nm) > -1) continue;
      else {
        nxtstp(n, i).father = stopinfo[n].nm;
        nxtstp(n, i).g = stopinfo[n].g + nxtstp(n, i)["to" + n]; //计算g(x)
        //计算f(x)↓
        nxtstp(n, i).f =
          nxtstp(n, i).g +
          dis(nxtstp(n, i).x, nxtstp(n, i).y, stopinfo[aim].x, stopinfo[aim].y);
        open.push(nxtstp(n, i).nm); //将x插入open表中
      }
    }
    close.push(n); //将节点n插入close表中
    minopen(open); //按f(n)将open表排序
  }
}