基于谷歌地图的Dijkstra算法水路路径规划

时间:2022-09-08 07:38:16

  最终效果图如下:

基于谷歌地图的Dijkstra算法水路路径规划

还是图、邻接表,可以模拟出几个对象=》节点、边、路径。三个类分别如下:

Node 节点:

using System;
using System.Collections.Generic; namespace Road.Plan
{
public class Node
{
private string id;
private IList<Edge> edgeList; public double Lat
{
get;
set;
} public double Lng
{
get;
set;
} public Node(string nid)
{
id = nid;
edgeList = new List<Edge>();
} public string Id
{
get
{
return id;
}
} public IList<Edge> EdgeList
{
get
{
return edgeList;
}
}
}
}

  Edge 边:

using System;
using System.Web.Script.Serialization; namespace Road.Plan
{
public class Edge
{
[ScriptIgnore]
public Node StartNode
{
get;
set;
}
[ScriptIgnore]
public Node EndNode
{
get;
set;
}
public int Weight
{
get;
set;
}
}
}

  Graph 图:

using System;
using System.Collections.Generic; namespace Road.Plan
{
/// <summary>
/// 由于边存在节点里了,邻接表的方式的图就这么简单
/// </summary>
public class Graph
{
public List<Node> NodeList = new List<Node>();
}
}

  路径Path:

using System;
using System.Collections.Generic; namespace Road.Plan
{
public class Path
{
//起始点 到 这个点
public string CurrentNodeId;
//该点是否已经计算
public bool IsProcessed = false;
//路径 权重合计
public int Weight = ;
//路径表示
public List<Node> PathNodeList = new List<Node>();
}
}

  路径规划辅助类:

using System;
using System.Collections.Generic;
using System.Linq; namespace Road.Plan
{
/// <summary>
/// 计算最短路径帮助类
/// </summary>
public class CaculateHelper
{
private Dictionary<string, Path> dicPath = new Dictionary<string, Path>();
public Dictionary<string, Path> DicPath
{
get
{
return dicPath;
}
} public void IniFirstNode(Graph graph, string StartNodeId)
{
Node OriginNode = null;
foreach (Node node in graph.NodeList)
{
if (node.Id == StartNodeId)
{
OriginNode = node;
}
else
{
Path path = new Path();
path.CurrentNodeId = node.Id;
dicPath.Add(path.CurrentNodeId, path); //初始化A->到所有边都是默认的Path 99999999
}
} //如果有A直接进入的边,则设置为相应权重值,和记录下路径
foreach (Edge edge in OriginNode.EdgeList)
{
Path path = new Path();
path.CurrentNodeId = edge.EndNode.Id;
path.Weight = edge.Weight;
path.PathNodeList.Add(edge.StartNode);
dicPath[path.CurrentNodeId] = path;
}
} public Node GetFromNodeMinWeightNode(Graph graph)
{
Node CNode = null;
KeyValuePair<string, Path> KVPPath = dicPath.Where(m => !m.Value.IsProcessed).OrderBy(m => m.Value.Weight).FirstOrDefault();
if (KVPPath.Key != null)
{
CNode = graph.NodeList.FirstOrDefault(m => m.Id == KVPPath.Value.CurrentNodeId);
}
return CNode;
} /// <summary>
/// 计算最短权值路径
/// </summary>
public void CatelateMinWeightRoad(Graph graph, string StartNodeId)
{
//取从第一个点出发,最小权值且未被访问果的节点的点
Node CNode = GetFromNodeMinWeightNode(graph);
//这段代码是核心 循环每个顶点,看看经过该顶点是否会让权值变小,如果会则存起此路径。直到再未访问过的点
while (CNode != null)
{
Path CurrentPath = dicPath[CNode.Id];
foreach (Edge edge in CNode.EdgeList)
{
if (edge.EndNode.Id == StartNodeId)
{
continue;
}
Path TargetPath = dicPath[edge.EndNode.Id]; int tempWeight = CurrentPath.Weight + edge.Weight;
if (tempWeight < TargetPath.Weight)
{
TargetPath.Weight = tempWeight;
TargetPath.PathNodeList.Clear(); for (int i = ; i < CurrentPath.PathNodeList.Count; i++)
{
TargetPath.PathNodeList.Add(CurrentPath.PathNodeList[i]);
} TargetPath.PathNodeList.Add(CNode);
}
} //标志为已处理
dicPath[CNode.Id].IsProcessed = true;
//再次获取权值最小的点
CNode = GetFromNodeMinWeightNode(graph);
}
}
}
}

  此处需要1个Controller、3个Action、1个页面。

  第一步,打开地图、并初始化好“运算-图”。

  第二步,获取所有节点,并将节点在地图上显示出来。

  第三步,获取运算结果,并在地图上根据计算结果将线划出来。

  Controller代码如下:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Web;
using System.Web.Mvc;
using Road.Plan; namespace Road.Controllers
{
public class HomeController : Controller
{
static Graph graph = new Graph(); public ActionResult GetAllNodes()
{
return Json(graph.NodeList, JsonRequestBehavior.AllowGet);
} public ActionResult Index()
{
graph.NodeList.Clear(); #region 初始化航路-图 Node Node1 = new Node("");
Node1.Lat = 23.1589850342836;
Node1.Lng = 112.7859878540039;
graph.NodeList.Add(Node1); Node Node2 = new Node("");
Node2.Lat = 23.136255816129122;
Node2.Lng = 112.79937744140625;
graph.NodeList.Add(Node2); Node Node3 = new Node("");
Node3.Lat = 23.11447003284563;
Node3.Lng = 112.79869079589844;
graph.NodeList.Add(Node3); Node Node4 = new Node("");
Node4.Lat = 23.142885569598484;
Node4.Lng = 112.80890464782715;
graph.NodeList.Add(Node4); Node Node5 = new Node("");
Node5.Lat = 23.144621879424374;
Node5.Lng = 112.81577110290527;
graph.NodeList.Add(Node5); Node Node6 = new Node("");
Node6.Lat = 23.151566893799817;
Node6.Lng = 112.82074928283691;
graph.NodeList.Add(Node6); Node Node7 = new Node("");
Node7.Lat = 23.15551276434145;
Node7.Lng = 112.82984733581543;
graph.NodeList.Add(Node7); Node Node8 = new Node("");
Node8.Lat = 23.1545657660099;
Node8.Lng = 112.84452438354492;
graph.NodeList.Add(Node8); Node Node9 = new Node("");
Node9.Lat = 23.167507497056675;
Node9.Lng = 112.81705856323242;
graph.NodeList.Add(Node9); //***************** 1 Node *******************
//1 -> 2
Edge aEdge1 = new Edge();
aEdge1.StartNode = Node1;
aEdge1.EndNode = Node2;
aEdge1.Weight = ;
Node1.EdgeList.Add(aEdge1); //***************** 2 Node *******************
//2 -> 3
Edge bEdge3 = new Edge();
bEdge3.StartNode = Node2;
bEdge3.EndNode = Node3;
bEdge3.Weight = ;
Node2.EdgeList.Add(bEdge3); //2 -> 1
Edge bEdge1 = new Edge();
bEdge1.StartNode = Node2;
bEdge1.EndNode = Node1;
bEdge1.Weight = ;
Node2.EdgeList.Add(bEdge1); //2 -> 4
Edge bEdge4 = new Edge();
bEdge4.StartNode = Node2;
bEdge4.EndNode = Node4;
bEdge4.Weight = ;
Node2.EdgeList.Add(bEdge4); //***************** 3 Node *******************
//3 -> 2
Edge cEdge2 = new Edge();
cEdge2.StartNode = Node3;
cEdge2.EndNode = Node2;
cEdge2.Weight = ;
Node3.EdgeList.Add(cEdge2); //***************** 4 Node *******************
//4 -> 2
Edge dEdge2 = new Edge();
dEdge2.StartNode = Node4;
dEdge2.EndNode = Node2;
dEdge2.Weight = ;
Node4.EdgeList.Add(dEdge2); //4 -> 5
Edge dEdge5 = new Edge();
dEdge5.StartNode = Node4;
dEdge5.EndNode = Node5;
dEdge5.Weight = ;
Node4.EdgeList.Add(dEdge5); //***************** 5 Node *******************
//5 -> 6
Edge eEdge6 = new Edge();
eEdge6.StartNode = Node5;
eEdge6.EndNode = Node6;
eEdge6.Weight = ;
Node5.EdgeList.Add(eEdge6); //5 -> 4
Edge eEdge4 = new Edge();
eEdge4.StartNode = Node5;
eEdge4.EndNode = Node4;
eEdge4.Weight = ;
Node5.EdgeList.Add(eEdge4); //***************** 6 Node *******************
//6 -> 5
Edge fEdge5 = new Edge();
fEdge5.StartNode = Node6;
fEdge5.EndNode = Node5;
fEdge5.Weight = ;
Node6.EdgeList.Add(fEdge5); //6 -> 7
Edge fEdge7 = new Edge();
fEdge7.StartNode = Node6;
fEdge7.EndNode = Node7;
fEdge7.Weight = ;
Node6.EdgeList.Add(fEdge7); //***************** 7 Node *******************
//7 -> 6
Edge gEdge6 = new Edge();
gEdge6.StartNode = Node7;
gEdge6.EndNode = Node6;
gEdge6.Weight = ;
Node7.EdgeList.Add(gEdge6); //7 -> 8
Edge gEdge8 = new Edge();
gEdge8.StartNode = Node7;
gEdge8.EndNode = Node8;
gEdge8.Weight = ;
Node7.EdgeList.Add(gEdge8); //7 -> 9
Edge gEdge9 = new Edge();
gEdge9.StartNode = Node7;
gEdge9.EndNode = Node9;
gEdge9.Weight = ;
Node7.EdgeList.Add(gEdge9); //***************** 8 Node *******************
//8 -> 7
Edge hEdge7 = new Edge();
hEdge7.StartNode = Node8;
hEdge7.EndNode = Node7;
hEdge7.Weight = ;
Node8.EdgeList.Add(hEdge7); //***************** 9 Node *******************
//9 -> 7
Edge iEdge7 = new Edge();
iEdge7.StartNode = Node9;
iEdge7.EndNode = Node7;
iEdge7.Weight = ;
Node9.EdgeList.Add(iEdge7); #endregion return View();
} /// <summary>
/// 计算起始点,结束点的最短路径
/// </summary>
/// <param name="StartNodeId"></param>
/// <param name="EndNodeId"></param>
/// <returns></returns>
public ActionResult GetWaterWay(string StartNodeId, string EndNodeId)
{
CaculateHelper CH = new CaculateHelper();
//第一步,初始化初始化源点 A 到 其他各点的 权重以及 路径(完成 A->B A->C A->E A->D 边权重,与A无直接边的则默认99999999)
CH.IniFirstNode(graph, StartNodeId);
//第二步,从权重最小的点开始,一直到权值最大的点
CH.CatelateMinWeightRoad(graph, StartNodeId); //组合返回值
Path ShowPath = CH.DicPath[EndNodeId];
ShowPath.PathNodeList.Add(graph.NodeList.First(m => m.Id == EndNodeId)); //补上结束点
return Json(ShowPath.PathNodeList);
}
}
}

  页面HTML代码如下:

<!DOCTYPE html>
<html>
<head>
<meta name="viewport" content="initial-scale=1.0, user-scalable=no">
<meta charset="utf-8">
<title>Complex icons</title>
<style>
html, body, #map-canvas {
height: 100%;
margin: 0px;
padding: 0px;
}
</style>
<script src="/jquery-1.10.2.min.js"></script>
<script src="http://ditu.google.cn/maps/api/js?sensor=false" type="text/javascript"></script> <script>
var map;
var lat = 23.144621879424374;
var lng = 112.81577110290527; var myLatlng = new google.maps.LatLng(lat, lng); //添加一个标记
function addMarker(lat, lng, title) {
var LatLng = new google.maps.LatLng(lat, lng);
var marker = new google.maps.Marker({
map: map,
position: LatLng,
title: title
});
return marker;
} function LatLng(lat, lng) {
return {
lat: lat,
lng: lng
};
} //线条选项
function lineOption() {
var lineOption = {
strokeColor: "#FF0000",
strokeOpacity: 1.0,
strokeWeight: 2,
coordinates: []
};
return lineOption;
} //画线
function addLine(lineOption) {
var linecoordinates = [];
for (var i = 0; i < lineOption.coordinates.length; i++) {
linecoordinates.push(new google.maps.LatLng(lineOption.coordinates[i].lat, lineOption.coordinates[i].lng));
} //显示线
var line = new google.maps.Polyline({
path: linecoordinates,
strokeColor: lineOption.strokeColor,
strokeOpacity: lineOption.strokeOpacity,
strokeWeight: lineOption.strokeWeight,
map: map
});
return line;
} var MarkerId = 1;
//初始化谷歌地图
function initialize() {
//设置地图中心
var mapOptions = {
zoom: 12,
center: myLatlng
}
map = new google.maps.Map(document.getElementById('map-canvas'), mapOptions); //google.maps.event.addListener(map, 'click', function (e) {
// var str = $("#position").html();
// var MID = MarkerId++;
// addMarker(e.latLng.lat(), e.latLng.lng(), MID);
// $("#position").html(str + " " + MID + " " + e.latLng.lat() + " " + e.latLng.lng() + "<br/>");
//}); $.ajax({
url: "/Home/GetAllNodes",
dataType: "json",
type: "post",
success: function (data) {
for (var i = 0; i < data.length; i++)
{
addMarker(data[i].Lat, data[i].Lng, data[i].Id);
}
}
}) $.ajax({
url: "/Home/GetWaterWay",
dataType: "json",
type: "post",
data:{
StartNodeId: "1",
EndNodeId: "9"
},
success: function (data) {
var lo = lineOption();
lo.strokeWeight = 4;
lo.strokeColor = "Green";
lo.strokeOpacity = 0.8;
//用返回的路线画线
for (var i = 0; i < data.length; i++)
{
lo.coordinates.push(LatLng(data[i].Lat, data[i].Lng));
}
addLine(lo);
}
})
} //监听页面事件,当页面加载完毕,加载谷歌地图
google.maps.event.addDomListener(window, 'load', initialize); </script>
</head>
<body>
<div id="map-canvas" style="height:600px;"></div>
<div id="position"></div>
</body>
</html>

基于谷歌地图的Dijkstra算法水路路径规划的更多相关文章

  1. 怎样基于谷歌地图的Server缓存公布Image Service服务

    怎样基于谷歌地图的Server缓存公布Image Service服务 第一步:下载地图数据 下载安装水经注万能地图下载器,启动时仅仅选择电子.谷歌(这里能够依据自己的须要选择).例如以下图所看到的. ...

  2. js基于谷歌地图API绘制可编辑圆形与多边形

    之前的工作中需要在谷歌地图上绘制可编辑多边形区域,所以基于谷歌地图API封装了个html页面,通过调用js绘制多边形并返回各点的经纬度坐标:当然首先你要保证你的电脑可以打开谷歌地图... 新建一个ht ...

  3. L2-001&period; 紧急救援 &lpar;Dijkstra算法打印路径&rpar;

    作为一个城市的应急救援队伍的负责人,你有一张特殊的全国地图.在地图上显示有多个分散的城市和一些连接城市的快速道路.每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上.当其他城市有紧急求 ...

  4. 利用dijkstra算法规划线路

    # dijkstra# 1.在数据库内预先存放了北京市内最新的道路节点,选用优化了得dijkstra算法进行线路规划.    当输入起点和终点后,会计算出最短的路径.同时还能选择查看路径经过的道路节点 ...

  5. 单源最短路径算法:迪杰斯特拉 &lpar;Dijkstra&rpar; 算法(二)

    一.基于邻接表的Dijkstra算法 如前一篇文章所述,在 Dijkstra 的算法中,维护了两组,一组包含已经包含在最短路径树中的顶点列表,另一组包含尚未包含的顶点.使用邻接表表示,可以使用 BFS ...

  6. ROS源码解读&lpar;二&rpar;--全局路径规划

    博客转载自:https://blog.csdn.net/xmy306538517/article/details/79032324 ROS中,机器人全局路径规划默认使用的是navfn包 ,move_b ...

  7. 机器人自主移动的秘密:SLAM与路径规划有什么关系?(三)

    博客转载自:https://www.leiphone.com/news/201612/lvDXqY82OGNqEiyl.html 雷锋网(公众号:雷锋网)按:本文作者SLAMTEC(思岚科技公号sla ...

  8. &lbrack;python&rsqb; A&ast;算法基于栅格地图的全局路径规划

    # 所有节点的g值并没有初始化为无穷大 # 当两个子节点的f值一样时,程序选择最先搜索到的一个作为父节点加入closed # 对相同数值的不同对待,导致不同版本的A*算法找到等长的不同路径 # 最后c ...

  9. 基于dijkstra算法求地铁站最短路径以及打印出所有的路径

    拓展dijkstra算法,实现利用vector存储多条路径: #include <iostream> #include <vector> #include <stack& ...

随机推荐

  1. 基于TCP和多线程实现无线鼠标键盘-GestureDetector

    为了实现无线鼠标,需要识别出用户在手机屏幕上的滑动动作,这就需要用到GestureDetector类. 首先是activity_main.xml: <LinearLayout xmlns:and ...

  2. 记一次CSR上线及总结

    终于到上线的时候了,可以好好休息了.放松了,但在没有经过用户确认之前,一切皆有可能发生...... 经历: 项目终于完成,上线文档已准备就绪,等待上线时刻. 在上线之前,忘记了解目前环境的部署架构,注 ...

  3. 关于 redis、memcache mongoDB 的对比

    from:http://yang.u85.us/memcache_redis_mongodb.pdf 从以下几个维度,对 redis.memcache.mongoDB 做了对比.1.性能都比较高,性能 ...

  4. eclipse工具背景色模板-程序员保护好自己的眼睛

    做为coder,要保护好自己的眼睛,eclipse 强烈推荐 Eclipse Color Theme插件,该插件包含多种当前流行的主题选择. 安装方法: 安装方法:1.先安装一个Eclipse Col ...

  5. 分析SIX锁和锁分区导致的死锁

    什么是SIX锁? 官方文档锁模式中说到: 意向排他共享 (SIX):保护针对层次结构中某些(而并非所有)低层资源请求或获取的共享锁以及针对某些(而并非所有)低层资源请求或获取的意向排他锁. *资源允 ...

  6. Android Timer用法

    Android考虑到线程安全问题,不允许在线程中执行UI线程,在Android中,有一个类:android.os.Handler,这个可以实现各处线程间的消息传递.先看段代码,这个实例化了一个Hand ...

  7. Codeforces 339E

    #include <cstdio> #include <algorithm> #include <cmath> #include <cstring> # ...

  8. jQuery&period;mobile&period;changePage&lpar;&rpar; &vert; jQuery Mobile API Documentation

    jQuery.mobile.changePage() | jQuery Mobile API Documentation <script> $.mobile.changePage( &qu ...

  9. iOS开发之音频播放AVAudioPlayer 类的介绍

    主要提供以下了几种播放音频的方法: 1. System Sound Services System Sound Services是最底层也是最简单的声音播放服务,调用 AudioServicesPla ...

  10. (五)STL算法

    .算法 1.算法通过迭代器来操作容器中的数据: 2.算法为模板函数: 二.迭代器与算法 1.根据移动能力,将迭代器分成了五类 2.使用萃取,输出各个容器中,迭代器的类别 3.其中istream, os ...