finish path finding by dijitrla

asmrobot

2019-11-03 8e3b276ae8638ef8a94d9e3f987482b253823596

finish path finding by dijitrla

 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')" />

 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

 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);
        }







 src/RichCreator.Utility/PathFinding/Dijkstra.cs

New file
@@ -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;
        }
    }
}

 src/RichCreator.Utility/PathFinding/DijkstraFinding_old/Dijkstra.cs

 src/RichCreator.Utility/PathFinding/DijkstraFinding_old/Edge.cs

 src/RichCreator.Utility/PathFinding/DijkstraFinding_old/Node.cs

 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" />

 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>();
        }


    }

 src/RichCreator.Utility/Structs/HousePathInfoObj.cs

New file
@@ -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;

        }
    }
}

 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;

 src/RichCreator.Utility/Structs/ParametersPointObj.cs

New file
@@ -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);
        }
    }
}

 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;
            }

 src/RichCreator.Utility/Structs/ZTLinePointObj.cs

New file
@@ -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));
        }
    }
}

 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
        
    }
}

 src/RichCreator.Utility/Structs/ZTPointObj.cs

New file
@@ -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);
        }
    }
}

 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);
        }

       
        
    }
}

 src/RichCreator.Utility/Structs/ZTPolygonObj.cs

New file
@@ -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);
        }
    }
}

 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;
    //    }
    //}
}