From 8e3b276ae8638ef8a94d9e3f987482b253823596 Mon Sep 17 00:00:00 2001
From: asmrobot <asmrobot@hotmail.com>
Date: Sun, 03 Nov 2019 16:47:52 +0000
Subject: [PATCH] finish path finding by dijitrla
---
src/RichCreator.Editor/RichCreator.Editor.csproj | 6
src/RichCreator.Utility/Structs/ZTPolygonObj.cs | 57 ++
src/RichCreator.Utility/Structs/ZTLinePointObj.cs | 46 +
src/RichCreator.Utility/PathFinding/DijkstraFinding_old/Dijkstra.cs | 0
src/RichCreator.Utility/Structs/ZTPoint.cs | 26
src/RichCreator.Utility/PathFinding/DNFPathFinding.cs | 261 +++++++++
src/RichCreator.Editor/Tools/MapEditor.xaml.cs | 52 +
src/RichCreator.Utility/Structs/ZTPolygon.cs | 32
src/RichCreator.Utility/Structs/ZTLinePoint.cs | 73 -
src/RichCreator.Utility/Structs/HousePathInfo.cs | 60 -
src/RichCreator.Utility/Structs/ParametersPoint.cs | 5
src/test/Program.cs | 640 ++++++----------------
src/RichCreator.Utility/PathFinding/DijkstraFinding_old/Edge.cs | 0
src/RichCreator.Utility/Structs/HousePathInfoObj.cs | 137 ++++
src/RichCreator.Utility/Structs/ZTPointObj.cs | 35 +
src/RichCreator.Utility/PathFinding/Dijkstra.cs | 151 +++++
src/RichCreator.Utility/PathFinding/DijkstraFinding_old/Node.cs | 0
src/RichCreator.Utility/RichCreator.Utility.csproj | 13
src/RichCreator.Utility/Structs/ParametersPointObj.cs | 41 +
19 files changed, 1,039 insertions(+), 596 deletions(-)
diff --git a/src/RichCreator.Editor/RichCreator.Editor.csproj b/src/RichCreator.Editor/RichCreator.Editor.csproj
index 57a5dd4..2ed1a23 100644
--- a/src/RichCreator.Editor/RichCreator.Editor.csproj
+++ b/src/RichCreator.Editor/RichCreator.Editor.csproj
@@ -179,13 +179,13 @@
<None Include="App.config" />
</ItemGroup>
<ItemGroup>
+ <Resource Include="program.ico" />
+ </ItemGroup>
+ <ItemGroup>
<ProjectReference Include="..\RichCreator.Utility\RichCreator.Utility.csproj">
<Project>{ceeff4d3-cc6f-4afe-85fe-e590c87a9972}</Project>
<Name>RichCreator.Utility</Name>
</ProjectReference>
- </ItemGroup>
- <ItemGroup>
- <Resource Include="program.ico" />
</ItemGroup>
<Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />
<Import Project="..\packages\EMGU.CV.4.1.0.3420\build\EMGU.CV.targets" Condition="Exists('..\packages\EMGU.CV.4.1.0.3420\build\EMGU.CV.targets')" />
diff --git a/src/RichCreator.Editor/Tools/MapEditor.xaml.cs b/src/RichCreator.Editor/Tools/MapEditor.xaml.cs
index 8277eb4..5ec9536 100644
--- a/src/RichCreator.Editor/Tools/MapEditor.xaml.cs
+++ b/src/RichCreator.Editor/Tools/MapEditor.xaml.cs
@@ -1,5 +1,6 @@
using Emgu.CV;
using RichCreator.Utility;
+using RichCreator.Utility.PathFinding;
using RichCreator.Utility.PathFindings;
using RichCreator.Utility.Structs;
using System;
@@ -105,7 +106,7 @@
return;
}
- var info = ZTImage.Json.JsonParser.ToObject<HousePathInfo>(input.ColorString);
+ var info = HousePathInfo.FromJsonString(input.ColorString);
if (info == null)
{
return;
@@ -199,8 +200,28 @@
ZTPoint start = this.startEndFindPathPoint[0];
ZTPoint end = this.startEndFindPathPoint[1];
- List<ZTPoint> path=this.housePathInfo.FindPath(start, end);
- //todo:绘制路径
+ DNFPathFinding finder = new DNFPathFinding(this.housePathInfo);
+
+
+ List<ZTPoint> path=finder.FindPath(ref start, ref end);
+
+ if (path==null||path.Count <= 0)
+ {
+ MessageBox.Show("不用寻路");
+ return;
+ }
+ else
+ {
+ //绘制路径
+ ZTPoint lastPoint = start;
+ for (int i = 0; i < path.Count; i++)
+ {
+
+ Line line=GetPathLineUI(lastPoint, path[i]);
+ this.StartEndPointLayer.Children.Add(line);
+ lastPoint = path[i];
+ }
+ }
}
@@ -784,9 +805,9 @@
polygon.Stroke = new SolidColorBrush(Colors.Black);
polygon.Fill = new SolidColorBrush(Colors.Black);
polygon.Opacity = 0.7f;
- for (int i = 0; i < this.points.Count; i++)
+ for (int i = 0; i < ztpolygon.Points.Length; i++)
{
- polygon.Points.Add(this.points[i]);
+ polygon.Points.Add(new Point(ztpolygon.Points[i].X,ztpolygon.Points[i].Y));
}
return polygon;
@@ -898,6 +919,27 @@
return main;
}
+
+ /// <summary>
+ /// 创建路径线
+ /// </summary>
+ /// <param name="start"></param>
+ /// <param name="end"></param>
+ /// <returns></returns>
+ private Line GetPathLineUI(ZTPoint start, ZTPoint end)
+ {
+ Line edgeLine = new Line();
+ edgeLine.Stroke = new SolidColorBrush(Colors.Green);
+ edgeLine.StrokeThickness = 1;
+ edgeLine.X1 = start.X;
+ edgeLine.Y1 = start.Y;
+
+ edgeLine.X2 = end.X;
+ edgeLine.Y2 = end.Y;
+
+
+ return edgeLine;
+ }
#endregion
#region Tools
diff --git a/src/RichCreator.Utility/PathFinding/DNFPathFinding.cs b/src/RichCreator.Utility/PathFinding/DNFPathFinding.cs
index a69d520..b870865 100644
--- a/src/RichCreator.Utility/PathFinding/DNFPathFinding.cs
+++ b/src/RichCreator.Utility/PathFinding/DNFPathFinding.cs
@@ -1,4 +1,6 @@
-using System;
+using RichCreator.Utility.Structs;
+using RichCreator.Utility.Utilitys;
+using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
@@ -11,6 +13,12 @@
/// </summary>
public class DNFPathFinding
{
+
+ public DNFPathFinding(HousePathInfo houseInfo)
+ {
+ this.HouseInfo = houseInfo;
+ InitPathFinder();
+ }
//凛冬
private static readonly string[] Lingdong = new string[] {
string.Empty,//0
@@ -27,6 +35,257 @@
string.Empty ,//0
};
+ /// <summary>
+ /// 房间信息
+ /// </summary>
+ public HousePathInfo HouseInfo { get; private set; }
+
+ /// <summary>
+ /// 路径查找器
+ /// </summary>
+ public Dijkstra<ZTPoint> PathFinder { get; private set; }
+
+
+ /// <summary>
+ /// 寻找巡逻路线
+ /// </summary>
+ /// <param name="rolePosition"></param>
+ public void FindLoopPath(ZTPoint rolePosition)
+ {
+
+ }
+
+ /// <summary>
+ /// 两点之间寻路
+ /// </summary>
+ /// <param name="start"></param>
+ /// <param name="end"></param>
+ public List<ZTPoint> FindPath(ref ZTPoint start, ref ZTPoint end)
+ {
+
+ if (start.Equals(end))
+ {
+ return new List<ZTPoint>();
+ }
+
+ //查询两点间是否连通
+ if (Iscross(start, end))
+ {
+ //两点直接连通
+ return new List<ZTPoint>() { end };
+ }
+
+ //确保两点不在障碍物里
+ bool inObstacle = EnsureNotInObstacle(ref start);
+ inObstacle = EnsureNotInObstacle(ref end) || inObstacle;
+
+ //查询两点间是否连通
+ if (inObstacle && Iscross(start, end))
+ {
+ //两点直接连通
+ return new List<ZTPoint>() { end };
+ }
+
+
+ //把两点添加到寻路网中
+ AddToFinder(start, end);
+
+ //寻路，组合路径
+ List<ZTPoint> paths=this.PathFinder.ShortestPath(start, end);
+
+ //去除寻路网中
+ RemoveFromFinder(start, end);
+ return paths;
+ }
+
+ /// <summary>
+ /// 判断两点间是否连通
+ /// </summary>
+ /// <param name="start"></param>
+ /// <param name="end"></param>
+ /// <returns></returns>
+ private bool Iscross(ZTPoint start, ZTPoint end)
+ {
+
+ for (int i = 0; i < this.HouseInfo.Obstacles.Count; i++)
+ {
+ Intersection interSection = GeometryHelper.IntersectionOf(new ZTLinePoint(start, end), this.HouseInfo.Obstacles[i]);
+ if (interSection != Intersection.None)
+ {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ /// <summary>
+ /// 是否在障碍物里，如果在障碍物里则返回最近的不在障碍物点
+ /// </summary>
+ /// <param name="point"></param>
+ /// <returns>true:在障碍物，false:不在障碍物里</returns>
+ private bool EnsureNotInObstacle(ref ZTPoint point)
+ {
+ ZTPoint source = new ZTPoint(point.X, point.Y);
+ ZTPolygon obstacle = ZTPolygon.Empty;
+ for (int i = 0; i < this.HouseInfo.Obstacles.Count; i++)
+ {
+ ZTPolygon temp = this.HouseInfo.Obstacles[i];
+ if (GeometryHelper.IntersectionOf(point, temp) != Intersection.None)
+ {
+ obstacle = this.HouseInfo.Obstacles[i];
+ break;
+ }
+ }
+ if (obstacle.Equals(ZTPolygon.Empty))
+ {
+ //不在障碍物内
+ return false;
+ }
+
+ //计算距离障碍物外最近的距离
+ double distance = 0;
+ ZTPoint lastPoint = ZTPoint.Empty;
+ for (int i = 0; i < obstacle.Points.Length; i++)
+ {
+ if (i == 0)
+ {
+ lastPoint = obstacle.Points[i];
+ distance = GeometryHelper.GetPointDistance(lastPoint, point);
+ }
+ double lastDistance = GeometryHelper.GetNearestDistance(new ZTLinePoint(lastPoint, obstacle[i]), point);
+ if (lastDistance < distance)
+ {
+ distance = lastDistance;
+ }
+ if (distance <= 0)
+ {
+ distance = 0;
+ break;
+ }
+ }
+
+ //查找最近离开障碍物的点
+ ZTPoint testPoint = new ZTPoint(point.X, point.Y);
+ Int32 maxDistance = Math.Max(Math.Max(point.X, this.HouseInfo.Width - point.X), Math.Max(point.Y, this.HouseInfo.Height - point.Y));
+ for (int i = (Int32)distance; i < maxDistance; i++)
+ {
+ //下
+ if (point.Y + i <= this.HouseInfo.Height)
+ {
+ testPoint = new ZTPoint(point.X, point.Y + i);
+ if (GeometryHelper.IntersectionOf(testPoint, obstacle) == Intersection.None)
+ {
+ testPoint.Y += 10;
+ point = testPoint;
+ break;
+ }
+ }
+
+
+ //右
+ if (point.X <= this.HouseInfo.Width)
+ {
+ testPoint = new ZTPoint(point.X + i, point.Y);
+ if (GeometryHelper.IntersectionOf(testPoint, obstacle) == Intersection.None)
+ {
+ testPoint.X += 10;
+ point = testPoint;
+ break;
+ }
+ }
+
+ //左
+ if (point.X - i >= 0)
+ {
+ testPoint = new ZTPoint(point.X - i, point.Y);
+ if (GeometryHelper.IntersectionOf(testPoint, obstacle) == Intersection.None)
+ {
+ testPoint.X -= 10;
+ point = testPoint;
+ break;
+ }
+ }
+
+ //上
+ if (point.Y - i >= 0)
+ {
+ testPoint = new ZTPoint(point.X, point.Y - i);
+ if (GeometryHelper.IntersectionOf(testPoint, obstacle) == Intersection.None)
+ {
+ testPoint.Y -= 10;
+ point = testPoint;
+ break;
+ }
+ }
+ }
+
+ return true;
+ }
+
+ /// <summary>
+ /// 初始化寻路器
+ /// </summary>
+ private void InitPathFinder()
+ {
+ this.PathFinder = new Dijkstra<ZTPoint>();
+
+ //添加寻路路径
+ ZTLinePoint line;
+ for (int i = 0; i < this.HouseInfo.FindPathLines.Count; i++)
+ {
+ line = this.HouseInfo.FindPathLines[i];
+ this.PathFinder.AddVertex(line.P1, line.P2, line.GetDistance());
+ }
+
+ //添加巡逻路径
+ for (int i = 0; i < this.HouseInfo.LoopLines.Count; i++)
+ {
+ line = this.HouseInfo.LoopLines[i];
+ this.PathFinder.AddVertex(line.P1, line.P2, line.GetDistance());
+ }
+ }
+
+ /// <summary>
+ /// 向查找器中添加查找点
+ /// </summary>
+ /// <param name="start"></param>
+ /// <param name="end"></param>
+ private void AddToFinder(ZTPoint start,ZTPoint end)
+ {
+ Int32 distance = 0;
+ ZTPoint point;
+ for (int i = 0; i < this.HouseInfo.FindPathPoints.Count; i++)
+ {
+ point = this.HouseInfo.FindPathPoints[i];
+ if (Iscross(start, point))
+ {
+ distance = (Int32)GeometryHelper.GetPointDistance(start, point);
+ this.PathFinder.AddVertex(start, point, distance);
+ }
+
+ if (Iscross(end,point))
+ {
+ distance = (Int32)GeometryHelper.GetPointDistance(end, point);
+ this.PathFinder.AddVertex(end, point, distance);
+ }
+ }
+
+ }
+
+
+ /// <summary>
+ /// 从查找器中移除查找点
+ /// </summary>
+ /// <param name="start"></param>
+ /// <param name="end"></param>
+ private void RemoveFromFinder(ZTPoint start, ZTPoint end)
+ {
+ this.PathFinder.RemoveVertex(start);
+ this.PathFinder.RemoveVertex(end);
+ }
+
+
+
diff --git a/src/RichCreator.Utility/PathFinding/Dijkstra.cs b/src/RichCreator.Utility/PathFinding/Dijkstra.cs
new file mode 100644
index 0000000..0a06952
--- /dev/null
+++ b/src/RichCreator.Utility/PathFinding/Dijkstra.cs
@@ -0,0 +1,151 @@
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace RichCreator.Utility.PathFinding
+{
+ public class Dijkstra<T> where T : IEquatable<T>
+ {
+ private Dictionary<T, Dictionary<T, Int32>> vertices = new Dictionary<T, Dictionary<T, Int32>>();
+
+ /// <summary>
+ /// 添加顶点
+ /// </summary>
+ /// <param name="name">顶点名称</param>
+ /// <param name="edges">顶点所有的边</param>
+ public void AddVertex(T name, Dictionary<T, Int32> edges)
+ {
+ foreach (var item in edges)
+ {
+ AddVertex(name, item.Key, item.Value);
+ }
+ }
+
+ /// <summary>
+ /// 添加顶点
+ /// </summary>
+ /// <param name="name">顶点名称</param>
+ /// <param name="target">可连接顶点</param>
+ /// <param name="weight">权重</param>
+ public void AddVertex(T name, T target, Int32 weight)
+ {
+ if (!this.vertices.ContainsKey(name))
+ {
+ this.vertices.Add(name, new Dictionary<T, Int32>());
+ }
+
+ if (!this.vertices[name].ContainsKey(target))
+ {
+ this.vertices[name].Add(target, weight);
+ }
+
+
+ if (!this.vertices.ContainsKey(target))
+ {
+ this.vertices.Add(target, new Dictionary<T, Int32>());
+ }
+
+
+ if (!this.vertices[target].ContainsKey(name))
+ {
+ this.vertices[target].Add(name, weight);
+ }
+
+ }
+
+ /// <summary>
+ /// 移除顶点
+ /// </summary>
+ /// <param name="name"></param>
+ public void RemoveVertex(T name)
+ {
+ if (this.vertices.ContainsKey(name))
+ {
+ return;
+ }
+ this.vertices.Remove(name);
+ foreach (var item in this.vertices)
+ {
+ if (item.Value.ContainsKey(name))
+ {
+ item.Value.Remove(name);
+ }
+ }
+ }
+
+
+
+
+ /// <summary>
+ /// 查找最短路径
+ /// </summary>
+ /// <param name="start"></param>
+ /// <param name="finish"></param>
+ /// <returns></returns>
+
+ public List<T> ShortestPath(T start, T finish)
+ {
+ var previous = new Dictionary<T, T>();
+ var distances = new Dictionary<T, Int32>();
+ var nodes = new List<T>();
+
+ List<T> path = null;
+
+ foreach (var vertex in vertices)
+ {
+ if (vertex.Key.Equals(start))
+ {
+ distances[vertex.Key] = 0;
+ }
+ else
+ {
+ distances[vertex.Key] = Int32.MaxValue;
+ }
+
+ nodes.Add(vertex.Key);
+ }
+
+ while (nodes.Count != 0)
+ {
+ nodes.Sort((x, y) => distances[x] - distances[y]);
+
+ var smallest = nodes[0];
+ nodes.Remove(smallest);
+
+ if (smallest.Equals(finish))
+ {
+ path = new List<T>();
+ while (previous.ContainsKey(smallest))
+ {
+ path.Add(smallest);
+ smallest = previous[smallest];
+ }
+
+ //倒译排列
+ path.Reverse();
+
+ break;
+ }
+
+ if (distances[smallest] == Int32.MaxValue)
+ {
+ break;
+ }
+
+ foreach (var neighbor in vertices[smallest])
+ {
+ var alt = distances[smallest] + neighbor.Value;
+ if (alt < distances[neighbor.Key])
+ {
+ distances[neighbor.Key] = alt;
+ previous[neighbor.Key] = smallest;
+ }
+ }
+ }
+
+ return path;
+ }
+ }
+}
diff --git a/src/RichCreator.Utility/PathFinding/DijkstraFinding/Dijkstra.cs b/src/RichCreator.Utility/PathFinding/DijkstraFinding_old/Dijkstra.cs
similarity index 100%
rename from src/RichCreator.Utility/PathFinding/DijkstraFinding/Dijkstra.cs
rename to src/RichCreator.Utility/PathFinding/DijkstraFinding_old/Dijkstra.cs
diff --git a/src/RichCreator.Utility/PathFinding/DijkstraFinding/Edge.cs b/src/RichCreator.Utility/PathFinding/DijkstraFinding_old/Edge.cs
similarity index 100%
rename from src/RichCreator.Utility/PathFinding/DijkstraFinding/Edge.cs
rename to src/RichCreator.Utility/PathFinding/DijkstraFinding_old/Edge.cs
diff --git a/src/RichCreator.Utility/PathFinding/DijkstraFinding/Node.cs b/src/RichCreator.Utility/PathFinding/DijkstraFinding_old/Node.cs
similarity index 100%
rename from src/RichCreator.Utility/PathFinding/DijkstraFinding/Node.cs
rename to src/RichCreator.Utility/PathFinding/DijkstraFinding_old/Node.cs
diff --git a/src/RichCreator.Utility/RichCreator.Utility.csproj b/src/RichCreator.Utility/RichCreator.Utility.csproj
index 7d90e25..cfe6361 100644
--- a/src/RichCreator.Utility/RichCreator.Utility.csproj
+++ b/src/RichCreator.Utility/RichCreator.Utility.csproj
@@ -55,7 +55,9 @@
<HintPath>..\Libs\SharpDX.DXGI.dll</HintPath>
</Reference>
<Reference Include="System" />
- <Reference Include="System.Core" />
+ <Reference Include="System.Core">
+ <Private>False</Private>
+ </Reference>
<Reference Include="System.Drawing" />
<Reference Include="System.Web" />
<Reference Include="System.Windows" />
@@ -102,20 +104,22 @@
<Compile Include="PathFinding\AStarFinding\PathGrid.cs" />
<Compile Include="PathFinding\AStarFinding\PathNode.cs" />
<Compile Include="PathFinding\AStarFinding\Point2.cs" />
- <Compile Include="PathFinding\DijkstraFinding\Dijkstra.cs" />
- <Compile Include="PathFinding\DijkstraFinding\Edge.cs" />
- <Compile Include="PathFinding\DijkstraFinding\Node.cs" />
+ <Compile Include="PathFinding\Dijkstra.cs" />
<Compile Include="PathFinding\DNFPathFinding.cs" />
<Compile Include="Properties\AssemblyInfo.cs" />
<Compile Include="Structs\ColorArray.cs" />
<Compile Include="Structs\ColorArrayItem.cs" />
<Compile Include="Structs\Direction.cs" />
<Compile Include="Structs\HousePathInfo.cs" />
+ <Compile Include="Structs\HousePathInfoObj.cs" />
<Compile Include="Structs\ParametersPoint.cs" />
+ <Compile Include="Structs\ParametersPointObj.cs" />
<Compile Include="Structs\ZTLinePoint.cs" />
<Compile Include="Structs\MoveQueueItem.cs" />
<Compile Include="Structs\Orientation.cs" />
<Compile Include="Structs\FindPathInfo.cs" />
+ <Compile Include="Structs\ZTLinePointObj.cs" />
+ <Compile Include="Structs\ZTPointObj.cs" />
<Compile Include="Structs\ZTPolygon.cs" />
<Compile Include="Structs\ZTColor.cs" />
<Compile Include="Structs\ZTColorArrayItem.cs" />
@@ -124,6 +128,7 @@
<Compile Include="Structs\ZTHsvFloatColorArrayItem.cs" />
<Compile Include="Structs\ZTLine.cs" />
<Compile Include="Structs\ZTPoint.cs" />
+ <Compile Include="Structs\ZTPolygonObj.cs" />
<Compile Include="Structs\ZTRectangle.cs" />
<Compile Include="Structs\ZTSize.cs" />
<Compile Include="Structs\ZTSizeDouble.cs" />
diff --git a/src/RichCreator.Utility/Structs/HousePathInfo.cs b/src/RichCreator.Utility/Structs/HousePathInfo.cs
index 0f59774..f733316 100644
--- a/src/RichCreator.Utility/Structs/HousePathInfo.cs
+++ b/src/RichCreator.Utility/Structs/HousePathInfo.cs
@@ -1,5 +1,7 @@
-using System;
+using RichCreator.Utility.Utilitys;
+using System;
using System.Collections.Generic;
+using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
@@ -21,7 +23,7 @@
}
- public HousePathInfo(Int32 width,Int32 height):this()
+ public HousePathInfo(Int32 width, Int32 height) : this()
{
this.Width = width;
this.Height = height;
@@ -38,7 +40,7 @@
/// 高
/// </summary>
public int Height { get; set; }
-
+
@@ -57,7 +59,7 @@
/// <summary>
/// 寻路点
/// </summary>
- public List<ZTPoint> FindPathPoints{ get; set; }
+ public List<ZTPoint> FindPathPoints { get; set; }
/// <summary>
@@ -111,12 +113,12 @@
/// </summary>
/// <param name="obstacle"></param>
/// <returns></returns>
- private bool ExistsObstacle(out Int32 index,ZTPolygon obstacle)
+ private bool ExistsObstacle(out Int32 index, ZTPolygon obstacle)
{
index = 0;
for (int i = 0; i < Obstacles.Count; i++)
{
- if (Obstacles[i] == obstacle)
+ if (Obstacles[i] .Equals( obstacle))
{
index = i;
return true;
@@ -151,7 +153,7 @@
{
this.LocationPoints.Clear();
}
-
+
/// <summary>
/// 添加寻路点
@@ -178,7 +180,7 @@
public bool RemoveFindPathPoint(ZTPoint point)
{
Int32 index = 0;
- if (!ExistsFindPathPoint(out index,point))
+ if (!ExistsFindPathPoint(out index, point))
{
return true;
}
@@ -218,14 +220,14 @@
/// </summary>
/// <param name="line"></param>
/// <returns></returns>
- public bool AddLoopLine(ZTLinePoint line)
+ public bool AddLoopLine(ZTLinePoint line)
{
Int32 index = 0;
if (ExistsLoopLine(out index, line))
{
return false;
}
- if (line.P1 .Equals( line.P2))
+ if (line.P1.Equals(line.P2))
{
return false;
}
@@ -255,12 +257,12 @@
/// <param name="index"></param>
/// <param name="line"></param>
/// <returns></returns>
- private bool ExistsLoopLine(out Int32 index, ZTLinePoint line)
+ private bool ExistsLoopLine(out Int32 index, ZTLinePoint line)
{
index = 0;
for (int i = 0; i < this.LoopLines.Count; i++)
{
- if (this.LoopLines[i] == line)
+ if (this.LoopLines[i] .Equals( line))
{
index = i;
return true;
@@ -313,7 +315,7 @@
index = 0;
for (int i = 0; i < this.FindPathLines.Count; i++)
{
- if (this.FindPathLines[i] == line)
+ if (this.FindPathLines[i] .Equals( line))
{
index = i;
return true;
@@ -339,7 +341,7 @@
for (int i = 0; i < this.FindPathLines.Count; i++)
{
- if (this.FindPathLines[i].P1 .Equals( point) || this.FindPathLines[i].P2.Equals(point))
+ if (this.FindPathLines[i].P1.Equals(point) || this.FindPathLines[i].P2.Equals(point))
{
return true;
}
@@ -356,7 +358,8 @@
/// <returns></returns>
public string ToJsonString()
{
- string json = ZTImage.Json.JsonBuilder.ToJsonString(this);
+ HousePathInfoObj obj=HousePathInfoObj.From(this);
+ string json = ZTImage.Json.JsonBuilder.ToJsonString(obj);
return json;
}
@@ -367,33 +370,10 @@
/// <returns></returns>
public static HousePathInfo FromJsonString(string json)
{
- return ZTImage.Json.JsonParser.ToObject<HousePathInfo>(json);
+ HousePathInfoObj obj= ZTImage.Json.JsonParser.ToObject<HousePathInfoObj>(json);
+ return obj.To();
}
-
- /// <summary>
- /// 寻找巡逻路线
- /// </summary>
- /// <param name="rolePosition"></param>
- public void FindLoopPath(ZTPoint rolePosition)
- {
-
- }
-
- /// <summary>
- /// 两点之间寻路
- /// </summary>
- /// <param name="start"></param>
- /// <param name="end"></param>
- public List<ZTPoint> FindPath(ZTPoint start, ZTPoint end)
- {
- //查询两点间是否连通
- //查找两点是否在障碍物里,如果在则计算出来的最短距离
- //计算最近的寻路点
- //计算寻路点的最短路径
- //得出所有路径点
- return new List<ZTPoint>();
- }
}
diff --git a/src/RichCreator.Utility/Structs/HousePathInfoObj.cs b/src/RichCreator.Utility/Structs/HousePathInfoObj.cs
new file mode 100644
index 0000000..1ab203f
--- /dev/null
+++ b/src/RichCreator.Utility/Structs/HousePathInfoObj.cs
@@ -0,0 +1,137 @@
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace RichCreator.Utility.Structs
+{
+ public class HousePathInfoObj
+ {
+ public HousePathInfoObj()
+ {
+
+ }
+ public HousePathInfoObj(Int32 width, Int32 height)
+ {
+ this.Width = width;
+ this.Height = height;
+ }
+ /// <summary>
+ /// 宽
+ /// </summary>
+ public int Width { get; set; }
+
+ /// <summary>
+ /// 高
+ /// </summary>
+ public int Height { get; set; }
+
+
+
+
+ /// <summary>
+ /// 障碍物
+ /// </summary>
+ public List<ZTPolygonObj> Obstacles { get; set; }
+
+
+ /// <summary>
+ /// 定位点
+ /// </summary>
+ public List<ParametersPointObj> LocationPoints { get; set; }
+
+
+ /// <summary>
+ /// 寻路点
+ /// </summary>
+ public List<ZTPointObj> FindPathPoints { get; set; }
+
+
+ /// <summary>
+ /// 循逻线
+ /// </summary>
+ public List<ZTLinePointObj> LoopLines { get; set; }
+
+ /// <summary>
+ /// 寻路线
+ /// </summary>
+ public List<ZTLinePointObj> FindPathLines { get; set; }
+
+ public HousePathInfo To()
+ {
+ HousePathInfo info = new HousePathInfo(this.Width, this.Height);
+
+ info.Obstacles = new List<ZTPolygon>();
+ foreach (var item in this.Obstacles)
+ {
+ info.Obstacles.Add(item.To());
+ }
+
+ info.LocationPoints = new List<ParametersPoint>();
+ foreach (var item in this.LocationPoints)
+ {
+ info.LocationPoints.Add(item.To());
+ }
+
+ info.FindPathPoints = new List<ZTPoint>();
+ foreach (var item in this.FindPathPoints)
+ {
+ info.FindPathPoints.Add(item.To());
+ }
+
+ info.LoopLines = new List<ZTLinePoint>();
+ foreach (var item in this.LoopLines)
+ {
+ info.LoopLines.Add(item.To());
+ }
+
+ info.FindPathLines = new List<ZTLinePoint>();
+ foreach (var item in this.FindPathLines)
+ {
+ info.FindPathLines.Add(item.To());
+ }
+
+ return info;
+ }
+
+ public static HousePathInfoObj From(HousePathInfo info)
+ {
+ HousePathInfoObj infoObj = new HousePathInfoObj(info.Width, info.Height);
+
+ infoObj.Obstacles = new List<ZTPolygonObj>();
+ foreach (var item in info.Obstacles)
+ {
+ infoObj.Obstacles.Add(ZTPolygonObj.From(item));
+ }
+
+ infoObj.LocationPoints = new List<ParametersPointObj>();
+ foreach (var item in info.LocationPoints)
+ {
+ infoObj.LocationPoints.Add(ParametersPointObj.From(item));
+ }
+
+ infoObj.FindPathPoints = new List<ZTPointObj>();
+ foreach (var item in info.FindPathPoints)
+ {
+ infoObj.FindPathPoints.Add(ZTPointObj.From(item));
+ }
+
+ infoObj.LoopLines = new List<ZTLinePointObj>();
+ foreach (var item in info.LoopLines)
+ {
+ infoObj.LoopLines.Add(ZTLinePointObj.From(item));
+ }
+
+ infoObj.FindPathLines = new List<ZTLinePointObj>();
+ foreach (var item in info.FindPathLines)
+ {
+ infoObj.FindPathLines.Add(ZTLinePointObj.From(item));
+ }
+
+
+ return infoObj;
+
+ }
+ }
+}
diff --git a/src/RichCreator.Utility/Structs/ParametersPoint.cs b/src/RichCreator.Utility/Structs/ParametersPoint.cs
index 46feeeb..ec427e0 100644
--- a/src/RichCreator.Utility/Structs/ParametersPoint.cs
+++ b/src/RichCreator.Utility/Structs/ParametersPoint.cs
@@ -9,11 +9,8 @@
/// <summary>
/// 带参数的点
/// </summary>
- public class ParametersPoint
+ public struct ParametersPoint
{
- public ParametersPoint()
- { }
-
public ParametersPoint(ZTPoint point, Int32 number)
{
this.Point = point;
diff --git a/src/RichCreator.Utility/Structs/ParametersPointObj.cs b/src/RichCreator.Utility/Structs/ParametersPointObj.cs
new file mode 100644
index 0000000..531ec4c
--- /dev/null
+++ b/src/RichCreator.Utility/Structs/ParametersPointObj.cs
@@ -0,0 +1,41 @@
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace RichCreator.Utility.Structs
+{
+ public class ParametersPointObj
+ {
+ public ParametersPointObj()
+ {
+
+ }
+ public ParametersPointObj(ZTPointObj point, Int32 number)
+ {
+ this.Point = point;
+ this.Parameter = number;
+ }
+ /// <summary>
+ /// 点
+ /// </summary>
+ public ZTPointObj Point { get; set; }
+
+ /// <summary>
+ /// 参数
+ /// </summary>
+ public Int32 Parameter { get; set; }
+
+ public ParametersPoint To()
+ {
+ return new ParametersPoint(this.Point.To(), this.Parameter);
+ }
+
+
+ public static ParametersPointObj From(ParametersPoint obj)
+ {
+ return new ParametersPointObj(ZTPointObj.From(obj.Point), obj.Parameter);
+ }
+ }
+}
diff --git a/src/RichCreator.Utility/Structs/ZTLinePoint.cs b/src/RichCreator.Utility/Structs/ZTLinePoint.cs
index 367efb6..82ba1eb 100644
--- a/src/RichCreator.Utility/Structs/ZTLinePoint.cs
+++ b/src/RichCreator.Utility/Structs/ZTLinePoint.cs
@@ -1,4 +1,5 @@
-using System;
+using RichCreator.Utility.Utilitys;
+using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
@@ -9,76 +10,56 @@
/// <summary>
/// 线
/// </summary>
- public class ZTLinePoint
+ public struct ZTLinePoint:IEquatable<ZTLinePoint>
{
public static ZTLinePoint Empty;
-
- private ZTPoint p1;
- private ZTPoint p2;
-
- public ZTLinePoint()
- {
-
- }
-
+
public ZTLinePoint(ZTPoint p1, ZTPoint p2)
{
- this.p1 = p1;
- this.p2 = p2;
+ this.P1 = p1;
+ this.P2 = p2;
}
- public ZTPoint P1
+ public ZTPoint P1;
+
+ public ZTPoint P2;
+
+ public Int32 GetDistance()
{
- get { return p1; }
- set { p1 = value; }
+ return (Int32)GeometryHelper.GetPointDistance(this.P1, this.P2);
}
- public ZTPoint P2
- {
- get { return p2; }
- set { p2 = value; }
- }
-
- [ZTImage.Reflection.UnSerializedAttribute]
+
public Int32 X1
{
- get { return p1.X; }
- set { p1.X = value; }
+ get { return P1.X; }
+ set { P1.X = value; }
}
- [ZTImage.Reflection.UnSerializedAttribute]
+
public Int32 X2
{
- get { return p2.X; }
- set { p2.X = value; }
+ get { return P2.X; }
+ set { P2.X = value; }
}
- [ZTImage.Reflection.UnSerializedAttribute]
+
public Int32 Y1
{
- get { return p1.Y; }
- set { p1.Y = value; }
+ get { return P1.Y; }
+ set { P1.Y = value; }
}
- [ZTImage.Reflection.UnSerializedAttribute]
+
public Int32 Y2
{
- get { return p2.Y; }
- set { p2.Y = value; }
+ get { return P2.Y; }
+ set { P2.Y = value; }
}
-
- public static bool operator !=(ZTLinePoint a, ZTLinePoint b)
+
+ public bool Equals(ZTLinePoint other)
{
- if (a == b)
- {
- return false;
- }
- return true;
- }
-
- public static bool operator ==(ZTLinePoint a, ZTLinePoint b)
- {
- if ((a.p1 .Equals( b.p1) && a.p2.Equals(b.p2)) || (a.p1 .Equals( b.p2) && a.p2.Equals(b.p1)))
+ if ((this.P1.Equals(other.P1) && this.P2.Equals(other.P2)) || (this.P1.Equals(other.P2) && this.P2.Equals(other.P1)))
{
return true;
}
diff --git a/src/RichCreator.Utility/Structs/ZTLinePointObj.cs b/src/RichCreator.Utility/Structs/ZTLinePointObj.cs
new file mode 100644
index 0000000..72f2a29
--- /dev/null
+++ b/src/RichCreator.Utility/Structs/ZTLinePointObj.cs
@@ -0,0 +1,46 @@
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace RichCreator.Utility.Structs
+{
+ public class ZTLinePointObj
+ {
+ public ZTLinePointObj()
+ {
+
+ }
+ private ZTPointObj p1;
+ private ZTPointObj p2;
+
+
+ public ZTLinePointObj(ZTPointObj p1, ZTPointObj p2)
+ {
+ this.p1 = p1;
+ this.p2 = p2;
+ }
+
+ public ZTPointObj P1
+ {
+ get { return p1; }
+ set { p1 = value; }
+ }
+
+ public ZTPointObj P2
+ {
+ get { return p2; }
+ set { p2 = value; }
+ }
+ public ZTLinePoint To()
+ {
+ return new ZTLinePoint(this.p1.To(), this.p2.To());
+ }
+
+ public static ZTLinePointObj From(ZTLinePoint obj)
+ {
+ return new ZTLinePointObj(ZTPointObj.From(obj.P1), ZTPointObj.From(obj.P2));
+ }
+ }
+}
diff --git a/src/RichCreator.Utility/Structs/ZTPoint.cs b/src/RichCreator.Utility/Structs/ZTPoint.cs
index 5bc4c14..20a5b0c 100644
--- a/src/RichCreator.Utility/Structs/ZTPoint.cs
+++ b/src/RichCreator.Utility/Structs/ZTPoint.cs
@@ -9,21 +9,16 @@
/// <summary>
/// 点
/// </summary>
- public class ZTPoint
+ public struct ZTPoint:IEquatable<ZTPoint>
{
public static ZTPoint Empty = new ZTPoint(0,0);
-
- public ZTPoint()
- {
-
- }
+
public ZTPoint(Int32 x, Int32 y)
{
this.X = x;
this.Y = y;
}
-
public Int32 X { get; set; }
public Int32 Y { get; set; }
@@ -73,19 +68,24 @@
return new ZTPoint(this.X - val.X, this.Y - val.Y);
}
- #region IEquatable
+
+
+ public override int GetHashCode()
+ {
+ Int32 hashCode = 17;
+ hashCode = hashCode * 23 + this.X;
+ hashCode = hashCode * 23 + this.Y;
+ return hashCode;
+ }
+
public bool Equals(ZTPoint other)
{
- if (other == null)
- {
- return false;
- }
if (this.X == other.X && this.Y == other.Y)
{
return true;
}
return false;
}
- #endregion
+
}
}
diff --git a/src/RichCreator.Utility/Structs/ZTPointObj.cs b/src/RichCreator.Utility/Structs/ZTPointObj.cs
new file mode 100644
index 0000000..80b8927
--- /dev/null
+++ b/src/RichCreator.Utility/Structs/ZTPointObj.cs
@@ -0,0 +1,35 @@
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace RichCreator.Utility.Structs
+{
+ public class ZTPointObj
+ {
+ public ZTPointObj()
+ {
+
+ }
+ public ZTPointObj(Int32 x, Int32 y)
+ {
+ this.X = x;
+ this.Y = y;
+ }
+
+ public Int32 X { get; set; }
+
+ public Int32 Y { get; set; }
+
+ public ZTPoint To()
+ {
+ return new ZTPoint(this.X, this.Y);
+ }
+
+ public static ZTPointObj From(ZTPoint obj)
+ {
+ return new ZTPointObj(obj.X, obj.Y);
+ }
+ }
+}
diff --git a/src/RichCreator.Utility/Structs/ZTPolygon.cs b/src/RichCreator.Utility/Structs/ZTPolygon.cs
index bdd3141..d1ff6b4 100644
--- a/src/RichCreator.Utility/Structs/ZTPolygon.cs
+++ b/src/RichCreator.Utility/Structs/ZTPolygon.cs
@@ -10,14 +10,10 @@
/// <summary>
/// 多边形
/// </summary>
- public class ZTPolygon
+ public struct ZTPolygon :IEquatable<ZTPolygon>
{
-
+ public static ZTPolygon Empty = default(ZTPolygon);
- public ZTPolygon()
- {
-
- }
public ZTPolygon(ZTPoint[] points)
{
this.Points = points;
@@ -30,7 +26,7 @@
public int Length
{
- get { return Points.Length; }
+ get { return Points==null?0:Points.Length; }
}
public ZTPoint this[int index]
@@ -38,25 +34,17 @@
get { return Points[index]; }
set { Points[index] = value; }
}
-
- public static bool operator !=(ZTPolygon a, ZTPolygon b)
+
+ public bool Equals(ZTPolygon other)
{
- if (a == b)
+
+ if (this.Length != other.Length)
{
return false;
}
- return true;
- }
-
- public static bool operator ==(ZTPolygon a, ZTPolygon b)
- {
- if (a.Length != b.Length)
+ for (int i = 0; i < this.Length; i++)
{
- return false;
- }
- for (int i = 0; i < a.Length; i++)
- {
- if (!a[i].Equals(b[i]))
+ if (!this[i].Equals(other[i]))
{
return false;
}
@@ -74,6 +62,6 @@
return new ZTPolygon(points);
}
-
+
}
}
diff --git a/src/RichCreator.Utility/Structs/ZTPolygonObj.cs b/src/RichCreator.Utility/Structs/ZTPolygonObj.cs
new file mode 100644
index 0000000..3269f3d
--- /dev/null
+++ b/src/RichCreator.Utility/Structs/ZTPolygonObj.cs
@@ -0,0 +1,57 @@
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace RichCreator.Utility.Structs
+{
+ public class ZTPolygonObj
+ {
+ public ZTPolygonObj()
+ {
+
+ }
+ public ZTPolygonObj(ZTPointObj[] points)
+ {
+ this.Points = points;
+ }
+
+ public ZTPointObj[] Points
+ {
+ get; set;
+ }
+
+ public int Length
+ {
+ get { return Points.Length; }
+ }
+
+ public ZTPointObj this[int index]
+ {
+ get { return Points[index]; }
+ set { Points[index] = value; }
+ }
+
+ public ZTPolygon To()
+ {
+ ZTPoint[] pos = new ZTPoint[this.Points.Length];
+ for (int i = 0; i < pos.Length; i++)
+ {
+ pos[i] = this.Points[i].To();
+ }
+
+ return new ZTPolygon(pos);
+ }
+
+ public static ZTPolygonObj From(ZTPolygon obj)
+ {
+ ZTPointObj[] points = new ZTPointObj[obj.Points.Length];
+ for (int i = 0; i < obj.Points.Length; i++)
+ {
+ points[i] = ZTPointObj.From(obj.Points[i]);
+ }
+ return new ZTPolygonObj(points);
+ }
+ }
+}
diff --git a/src/test/Program.cs b/src/test/Program.cs
index a943b0e..5131453 100644
--- a/src/test/Program.cs
+++ b/src/test/Program.cs
@@ -5,486 +5,210 @@
using System.Threading.Tasks;
using System.Threading;
using System.Drawing;
-using static test.Graphics;
+using System.Reflection.Emit;
+using System.Reflection;
namespace test
{
-
-
- public struct person
+ public class Dijkstra<T> where T:IEquatable<T>
{
- public int age { get; set; }
+ private Dictionary<T, Dictionary<T, int>> vertices = new Dictionary<T, Dictionary<T, int>>();
- public string name { get; set; }
+ /// <summary>
+ /// 添加顶点
+ /// </summary>
+ /// <param name="name">顶点名称</param>
+ /// <param name="edges">顶点所有的边</param>
+ public void AddVertex(T name, Dictionary<T, int> edges)
+ {
+ foreach (var item in edges)
+ {
+ AddVertex(name, item.Key, item.Value);
+ }
+ }
+ /// <summary>
+ /// 添加顶点
+ /// </summary>
+ /// <param name="name">顶点名称</param>
+ /// <param name="target">可连接顶点</param>
+ /// <param name="weight">权重</param>
+ public void AddVertex(T name, T target, int weight)
+ {
+ if (!this.vertices.ContainsKey(name))
+ {
+ this.vertices.Add(name, new Dictionary<T, int>());
+ }
+
+ if (this.vertices[name].ContainsKey(target))
+ {
+ return;
+ }
+
+ this.vertices[name].Add(target, weight);
+ }
+
+ /// <summary>
+ /// 移除顶点
+ /// </summary>
+ /// <param name="name"></param>
+ public void RemoveVertex(T name)
+ {
+ if (this.vertices.ContainsKey(name))
+ {
+ return;
+ }
+ this.vertices.Remove(name);
+ foreach (var item in this.vertices)
+ {
+ if (item.Value.ContainsKey(name))
+ {
+ item.Value.Remove(name);
+ }
+ }
+ }
+
+
+
+
+ /// <summary>
+ /// 查找最短路径
+ /// </summary>
+ /// <param name="start"></param>
+ /// <param name="finish"></param>
+ /// <returns></returns>
+
+ public List<T> ShortestPath(T start, T finish)
+ {
+ var previous = new Dictionary<T, T>();
+ var distances = new Dictionary<T, int>();
+ var nodes = new List<T>();
+
+ List<T> path = null;
+
+ foreach (var vertex in vertices)
+ {
+ if (vertex.Key .Equals( start))
+ {
+ distances[vertex.Key] = 0;
+ }
+ else
+ {
+ distances[vertex.Key] = int.MaxValue;
+ }
+
+ nodes.Add(vertex.Key);
+ }
+
+ while (nodes.Count != 0)
+ {
+ nodes.Sort((x, y) => distances[x] - distances[y]);
+
+ var smallest = nodes[0];
+ nodes.Remove(smallest);
+
+ if (smallest .Equals( finish))
+ {
+ path = new List<T>();
+ while (previous.ContainsKey(smallest))
+ {
+ path.Add(smallest);
+ smallest = previous[smallest];
+ }
+
+ break;
+ }
+
+ if (distances[smallest] == int.MaxValue)
+ {
+ break;
+ }
+
+ foreach (var neighbor in vertices[smallest])
+ {
+ var alt = distances[smallest] + neighbor.Value;
+ if (alt < distances[neighbor.Key])
+ {
+ distances[neighbor.Key] = alt;
+ previous[neighbor.Key] = smallest;
+ }
+ }
+ }
+
+ return path;
+ }
}
+
+ public struct person:IEquatable<person>
+ {
+ public person(Int32 age,string name)
+ {
+ this.Age = age;
+ this.Name = name;
+ }
+ public int Age { get; set; }
+
+ public string Name { get; set; }
+
+ public bool Equals(person other)
+ {
+ if (this.Age == other.Age && Name.Equals(other.Name, StringComparison.Ordinal))
+ {
+ return true;
+ }
+ return false;
+ }
+
+ public override int GetHashCode()
+ {
+ Int32 hashcode = 17;
+ hashcode = hashcode * 23 + this.Age.GetHashCode();
+ hashcode = hashcode * 23 + this.Name.GetHashCode();
+ return hashcode;
+ }
+
+ public override string ToString()
+ {
+ return this.Name + "," + this.Age.ToString();
+ }
+
+
+
+ }
class Program
{
-
- //static void GetN(person p)
- //{
- // p = new person();
- // p.age = 2;
- //}
-
+
static void Main(string[] args)
{
+ person a = new person(235, "a0");
+ person b = new person(12, "b1");
+ person c = new person(34, "c2");
+ person d = new person(45, "d3");
+ person e = new person(56, "e4");
+ Dijkstra<person> dij = new Dijkstra<person>();
+ dij.AddVertex(a, new Dictionary<person, int>() { { b, 7 }, { d, 8 } });
+ dij.AddVertex(b, new Dictionary<person, int>() { { a, 7 }, { c, 2 },{ d,2} ,{ e,3} });
+ dij.AddVertex(c, new Dictionary<person, int>() { { b, 8 }, { e, 6 } });
+ dij.AddVertex(d, new Dictionary<person, int>() { { a, 8 },{ b,2} });
+ dij.AddVertex(e, new Dictionary<person, int>() { { b, 1 },{ c,2} });
+ dij.ShortestPath(d, e).ForEach(x => Console.WriteLine(x));
+ ZTImage.Diagnostics.CodeTimer.Timer("dij", 10000, () =>
+ {
+ //g.ShortestPath('A', 'H').ForEach(x => Console.WriteLine(x));
+ dij.ShortestPath(a, b);
- person p = new person();
- p.age = 12;
- p.name = "xylee";
-
-
- Console.WriteLine(ZTImage.Json.JsonBuilder.ToJsonString(p));
+ });
- //ZTPoint A = new ZTPoint(0, 1);
- //ZTPoint B = new ZTPoint(1, 0);
- //ZTPoint C = new ZTPoint(3, 0);
- //ZTPoint D = new ZTPoint(4, 1);
- //ZTPoint E = new ZTPoint(3, 2);
- //ZTPoint F = new ZTPoint(2, 1);
- //ZTPoint G = new ZTPoint(1, 2);
- //var edges = new List<Tuple<ZTPoint, ZTPoint, double>>()
- //{
- // new Tuple<ZTPoint,ZTPoint,double>(A,B,12),
- // new Tuple<ZTPoint,ZTPoint,double>(A,F,16),
- // new Tuple<ZTPoint,ZTPoint,double>(A,G,14),
- // new Tuple<ZTPoint,ZTPoint,double>(B,F,7),
- // new Tuple<ZTPoint,ZTPoint,double>(B,C,10),
- // new Tuple<ZTPoint,ZTPoint,double>(G,F,9),
- // new Tuple<ZTPoint,ZTPoint,double>(G,E,8),
- // new Tuple<ZTPoint,ZTPoint,double>(F,C,6),
- // new Tuple<ZTPoint,ZTPoint,double>(F,E,2),
- // new Tuple<ZTPoint,ZTPoint,double>(C,D,3),
- // new Tuple<ZTPoint,ZTPoint,double>(C,E,5),
- // new Tuple<ZTPoint,ZTPoint,double>(E,D,4),
- //};
-
- //var dij = new Dijkstra(edges);
- //var path = dij.Find(D, G);
-
- //for (int i = 0; i < path.Count; i++)
- //{
- // Console.WriteLine(path[i].ToString());
- //}
-
-
- Console.WriteLine("finish!~");
Console.ReadKey();
}
+
}
-
-
- /// <summary>
- /// 图
- /// </summary>
- public class Graphics
- {
- public const int MaxSize = 6;
- public const int INF = 32767; //INF表示∞
- public const int MAXV = 4; //最大顶点个数
- //结构体的成员定义里不能直接赋值，也就是等号后的应该移除，在你后面实例化整个结构体以后，
- //再对Study_Data[n].input=new double[50] 其他成员类似。顺便说下其实用class简单得多。
-
- public struct VertexType
- {
- public string VexNo; //顶点编号
- public string VexName; //顶点名称
- public string otherInfo; //顶点其他信息
- }; //顶点类型
- public struct MGraph //图的定义
- {
- public int[,] edges; //邻接矩阵
- public int n, e; //顶点数,弧数
- public VertexType[] vexs; //存放顶点信息
- }; //图的邻接矩阵类型
-
- static void Ppath(int[] path, int i, int v) //前向递归查找路径上的顶点
- {
- int k;
- k = path[i];
- if (k == v) return; //找到了起点则返回
- Ppath(path, k, v); //找顶点k的前一个顶点v
-
- Console.Write("{0},", k); //输出路径上的终点
- // Ppath(path, k, j); //找顶点k的前一个顶点j
- }
-
- static void Ppath(MGraph g, int[] path, int i, int v) //前向递归查找路径上的顶点
- {
- int k;
- k = path[i];
- if (k == v) return; //找到了起点则返回
- Ppath(path, k, v); //找顶点k的前一个顶点v
-
- Console.Write("{0},", g.vexs[k].VexName); //输出路径上的终点
- // Ppath(path, k, j); //找顶点k的前一个顶点j
- }
-
- static void Dispath(int[] dist, int[] path, int[] s, int n, int v)
- {
- int i;
- for (i = 0; i < n; i++)
- {
- if (s[i] == 1)
- {
- Console.Write(" 从{0}到{1}的最短路径长度为:{2}\t路径为:", v, i, dist[i]);
- Console.Write("{0},", v); //输出路径上的起点
- Ppath(path, i, v); //输出路径上的中间点
- Console.WriteLine("{0}", i); //输出路径上的终点
- }
- else
- Console.WriteLine("从{0}到{1}不存在路径\n", v, i);
- }
- }
-
- static void PutBothpath(MGraph g, int[] dist, int[] path, int[] s, int n, int v, int m)
- {
- int i;
- for (i = 0; i < n; i++)
- {
- if (s[i] == 1)
- {
- //Console.Write(" 从{0}到{1}的最短路径长度为:{2}\t路径为:", v, i, dist[i]);
- //Console.Write("{0},", v); //输出路径上的起点
- //Ppath(path, i, v); //输出路径上的中间点
- //Console.WriteLine("{0}", i); //输出路径上的终点
- if (i == m && dist[i] < INF)
- {
- Console.Write(" 从{0}到{1}的最短路径长度为:{2}\t路径为:", g.vexs[v].VexName, g.vexs[i].VexName, dist[i]);
- Console.Write("{0},", g.vexs[v].VexName); //输出路径上的起点
- //Ppath(path, i, v); //输出路径上的中间点
- Ppath(g, path, i, v);
- Console.WriteLine("{0}", g.vexs[i].VexName); //输出路径上的终点
- }
- }
- else
- Console.WriteLine("从{0}到{1}不存在路径\n", v, i);
- }
- }
-
- public static void Dijkstra(MGraph g, int v)
- {
- int[] dist = new int[MAXV];//从原点v到其他的各定点当前的最短路径长度
- int[] path = new int[MAXV];//path[i]表示从原点到定点i之间最短路径的前驱节点
- int[] s = new int[MAXV]; //选定的顶点的集合
- int mindis, i, j, u;
- u = 0;
- for (i = 0; i < g.n; i++)
- {
- dist[i] = g.edges[v, i]; //距离初始化
- s[i] = 0; //s[]置空 0表示i不在s集合中
- if (g.edges[v, i] < INF) //路径初始化
- path[i] = v;
- else
- path[i] = -1;
- }
- s[v] = 1; //源点编号v放入s中
- path[v] = 0;
- for (i = 0; i < g.n; i++) //循环直到所有顶点的最短路径都求出
- {
- mindis = INF; //mindis置最小长度初值
- for (j = 0; j < g.n; j++) //选取不在s中且具有最小距离的顶点u
- if (s[j] == 0 && dist[j] < mindis)
- {
- u = j;
- mindis = dist[j];
- }
- s[u] = 1; //顶点u加入s中
- for (j = 0; j < g.n; j++) //修改不在s中的顶点的距离
- if (s[j] == 0)
- if (g.edges[u, j] < INF && dist[u] + g.edges[u, j] < dist[j])
- {
- dist[j] = dist[u] + g.edges[u, j];
- path[j] = u;
- }
- }
- Dispath(dist, path, s, g.n, v); //输出最短路径
- //PutBothpath(g, dist, path, s, g.n, v, 3);
- }
-
- static void initdata()
- {
- int i, j;
- MGraph g;
- g.n = 4; g.e = 8;
- g.edges = new int[MAXV, MAXV];
- g.vexs = new VertexType[MAXV];
- //int [,] anArray = new int [2, 4] {{1,2,3,4},{5,6,7,8}};
- int[,] a = new int[MAXV, MAXV] {
- {0, 5,INF,7},
- {INF,0, 4,2},
- {3, 3, 0,2},
- {INF,INF,1,0}
- };
-
- for (i = 0; i < g.n; i++) //建立图的图的邻接矩阵
- {
- for (j = 0; j < g.n; j++)
- {
- g.edges[i, j] = a[i, j];///////////////////////////////////////////////
- }
- }
- Console.WriteLine("各顶点的最短路径:");
- }
-
- public static void initialVexInfo(MGraph g)
- {
- g.vexs[0].VexNo = "0361";
- g.vexs[0].VexName = "西安";
-
- g.vexs[1].VexNo = "010";
- g.vexs[1].VexName = "北京";
-
- g.vexs[2].VexNo = "0681";
- g.vexs[2].VexName = "武汉";
-
- g.vexs[3].VexNo = "0571";
- g.vexs[3].VexName = "杭州";
- }
- }
-
-
- //public class StationSched
- //{
- // /// <summary>
- // /// 所有的站点信息
- // /// </summary>
- // List<StationInfo> stations = new List<StationInfo>();
-
- // /// <summary>
- // /// 线路信息
- // /// </summary>
- // List<ShipInfo> lines = new List<ShipInfo>();
-
- // /// <summary>
- // /// 构造函数，初始化站点和线路信息
- // /// </summary>
- // public StationSched()
- // {
- // stations.Add(new StationInfo() { Sid = 1, Lid = 1 });//0
- // stations.Add(new StationInfo() { Sid = 2, Lid = 1 });//1
- // stations.Add(new StationInfo() { Sid = 3, Lid = 1 });//2
- // stations.Add(new StationInfo() { Sid = 4, Lid = 1 });//3
- // stations.Add(new StationInfo() { Sid = 5, Lid = 1 });//4
- // stations.Add(new StationInfo() { Sid = 6, Lid = 1 });//5
- // stations.Add(new StationInfo() { Sid = 7, Lid = 1 });//6
-
- // stations.Add(new StationInfo() { Sid = 19, Lid = 2 });//7
- // stations.Add(new StationInfo() { Sid = 18, Lid = 2 });
- // stations.Add(new StationInfo() { Sid = 17, Lid = 2 });
- // stations.Add(new StationInfo() { Sid = 3, Lid = 2 });
- // stations.Add(new StationInfo() { Sid = 13, Lid = 2 });
- // stations.Add(new StationInfo() { Sid = 16, Lid = 2 });
-
-
- // stations.Add(new StationInfo() { Sid = 15, Lid = 3 });//13
- // stations.Add(new StationInfo() { Sid = 14, Lid = 3 });
- // stations.Add(new StationInfo() { Sid = 13, Lid = 3 });
- // stations.Add(new StationInfo() { Sid = 12, Lid = 3 });
- // stations.Add(new StationInfo() { Sid = 11, Lid = 3 });
- // stations.Add(new StationInfo() { Sid = 5, Lid = 3 });
- // stations.Add(new StationInfo() { Sid = 10, Lid = 3 });
- // stations.Add(new StationInfo() { Sid = 9, Lid = 3 });
- // stations.Add(new StationInfo() { Sid = 8, Lid = 3 });
-
- // for (int i = 0; i < 6; i++)
- // {
- // lines.Add(new ShipInfo() { Curr = stations[i], Next = stations[i + 1] });
- // }
- // for (int i = 6; i > 0; i--)
- // {
- // lines.Add(new ShipInfo() { Curr = stations[i], Next = stations[i - 1] });
- // }
-
- // for (int i = 7; i < 12; i++)
- // {
- // lines.Add(new ShipInfo() { Curr = stations[i], Next = stations[i + 1] });
- // }
- // for (int i = 12; i > 7; i--)
- // {
- // lines.Add(new ShipInfo() { Curr = stations[i], Next = stations[i - 1] });
- // }
-
- // for (int i = 13; i < 21; i++)
- // {
- // lines.Add(new ShipInfo() { Curr = stations[i], Next = stations[i + 1] });
- // }
- // for (int i = 21; i > 13; i--)
- // {
- // lines.Add(new ShipInfo() { Curr = stations[i], Next = stations[i - 1] });
- // }
-
- // }
-
- // /// <summary>
- // /// 获取sid站点可以到达的站点信息，去除已经计算过的preid站点
- // /// </summary>
- // /// <param name="preid"></param>
- // /// <param name="sid"></param>
- // /// <returns></returns>
- // public List<StationInfo> GetNext(int preid, int sid)
- // {
- // List<StationInfo> list = new List<StationInfo>();
- // foreach (var item in lines)
- // {
- // if (item.Curr.Sid == sid && item.Next.Sid != preid) list.Add(item.Next);
- // }
- // return list;
- // }
-
- // /// <summary>
- // /// 获取线路信息
- // /// </summary>
- // /// <param name="s">起始站点编号</param>
- // /// <param name="e">结束站点编号</param>
- // /// <returns></returns>
- // public List<string> GetResult(int s, int e)
- // {
- // List<List<int>> temp = GetLine(s, e);
- // List<string> result = new List<string>();
- // List<List<int>> line = new List<List<int>>();
- // foreach (var item in temp)
- // {
- // if (item.Count > 0 && item[item.Count - 1] == e)
- // line.Add(item);
- // }
- // string src = "";
- // int currLine = -1;
- // foreach (var item in line)
- // {
- // currLine = GetLineNumber(item[0], item[1]);
- // src += "从[" + currLine + "号线]的[" + item[0] + "]上车";
- // for (int i = 1; i < item.Count; i++)
- // {
- // if (i == item.Count - 1)
- // {
- // src += ",在[" + item[i] + "]站点下车。";
- // result.Add(src);
- // src = "";
- // break;
- // }
- // int tempLine = GetLineNumber(item[i], item[i + 1]);
- // if (tempLine != currLine)
- // {
- // currLine = tempLine;
- // src += ",在[" + item[i] + "]站点换乘[" + currLine + "号线]";
- // }
- // }
-
- // }
-
- // return result;
- // }
-
- // /// <summary>
- // /// 根据相邻的两个点取当前的线路
- // /// </summary>
- // /// <param name="s"></param>
- // /// <param name="e"></param>
- // /// <returns></returns>
- // private int GetLineNumber(int l, int r)
- // {
- // foreach (var item in lines)
- // {
- // if ((item.Curr.Sid == l && item.Next.Sid == r) || (item.Curr.Sid == r && item.Next.Sid == l))
- // return item.Next.Lid;
- // }
- // return -1;
- // }
-
- // /// <summary>
- // /// 获取线路的ID集合
- // /// </summary>
- // /// <param name="s">起始站点编号</param>
- // /// <param name="e">结束站点编号</param>
- // /// <returns></returns>
- // private List<List<int>> GetLine(int s, int e)
- // {
- // List<List<int>> result = new List<List<int>>();
- // List<int> curr = new List<int>();
- // curr.Add(s);
- // result.Add(curr);
- // int currLine = 0;
- // int preSid = s;
- // int currSid = s;
- // while (true)
- // {
- // if (currLine >= result.Count) return result;
- // currSid = result[currLine][result[currLine].Count - 1];
- // if (currSid == e)
- // {
- // currLine += 1;
- // continue;
- // }
- // if (result[currLine].Count > 1)
- // preSid = result[currLine][result[currLine].Count - 2];
- // if (currSid <= 0)
- // {
- // currLine += 1;
- // continue;
- // }
- // List<StationInfo> temp = GetNext(preSid, currSid);
-
- // if (temp.Count == 0)
- // {//某条线路到头
- // currLine += 1;
- // }
- // else if (temp.Count == 1)
- // {//不需要换乘继续前进
- // result[currLine].Add(temp[0].Sid);
- // }
- // else
- // {//需要换乘了。
- // for (int i = 1; i < temp.Count; i++)
- // {
- // if (!result[currLine].Contains(temp[i].Sid))
- // {//防止死循环，过滤掉已经计算过的站点。
- // result.Add(result[currLine].GetRange(0, result[currLine].Count));
- // result[result.Count - 1].Add(temp[i].Sid);
- // }
- // }
- // result[currLine].Add(temp[0].Sid);
- // }
- // }
- // }
- //}
-
-
-
- ///// <summary>
- ///// 站点信息
- ///// </summary>
- //public class StationInfo
- //{
- // public int Lid { get; set; }
- // public int Sid { get; set; }
-
- // public override string ToString()
- // {
- // return "Sid:" + Sid + "--Lid:" + Lid;
- // }
- //}
-
- ///// <summary>
- ///// 关系信息
- ///// </summary>
- //public class ShipInfo
- //{
- // public StationInfo Curr { get; set; }
- // public StationInfo Next { get; set; }
-
- // public override string ToString()
- // {
- // return "Curr:" + Curr.Sid + "--Next:" + Next.Sid;
- // }
- //}
}
--
Gitblit v1.9.3