c# – Polygon找到从开始到结束的最短路径

谢谢@gusman

>添加栅格
>计算点之间的距离
>搜索Dijkstra.NET的最佳路线

using Dijkstra.NET.Contract;
using Dijkstra.NET.Model;
using Dijkstra.NET.ShortestPath;
using System;
using System.Collections.Generic;
using System.Drawing;
using System.Drawing.Drawing2D;

namespace Test.Polygon
{
    class Program
    {
        static void Main(string[] args)
        {
            var points = new List<Point> { new Point(210,480) };

            var start = new Point(190,500);
            var target = new Point(840,80);

            var image = new Bitmap(1000,600);
            using (var graphics = Graphics.FromImage(image))
            {
                graphics.Clear(Color.White);
                graphics.FillPie(Brushes.Blue,360);
                graphics.FillPie(Brushes.Red,360);
                graphics.DrawPolygon(new Pen(Color.Black,points.ToArray());
            }

            var path = new GraphicsPath(FillMode.Winding);
            path.AddPolygon(points.ToArray());

            var pointsForConnect = DrawRaster(5,image,path);


            var dictionary = new Dictionary<uint,Point>();
            dictionary.Add(0,start);
            dictionary.Add(1,target);

            var graph = new Graph<int,string>();

            var i = 2;
            foreach (var point in pointsForConnect)
            {
                dictionary.Add((uint)i,point);
                graph.AddNode(i);
                i++;
            }

            foreach (var point in dictionary)
            {
                foreach (var point2 in dictionary)
                {
                    if (point.Equals(point2))
                    {
                        continue;
                    }

                    double dist = Math.Sqrt(Math.Pow(point2.Value.X - point.Value.X,2) + Math.Pow(point2.Value.Y - point.Value.Y,2));

                    if (dist > 50)
                    {
                        continue;
                    }
                    graph.Connect(point.Key,point2.Key,(int)dist,null);
                    //graph.Connect()
                }
            }


            var dijkstra = new Dijkstra<int,string>(graph);
            IShortestPathResult result = dijkstra.Process(0,1); //result contains the shortest path
            var shortestRouteIds = result.GetPath();

            var shortestRoutePoints = new List<Point>();
            foreach(var x in shortestRouteIds)
            {
                shortestRoutePoints.Add(dictionary[x]);
            }

            DrawDriver(shortestRoutePoints,image);

            image.Save("example.bmp");
        }

        private static void DrawDriver(List<Point> points,Bitmap image)
        {
            var pen = new Pen(Color.LightGreen,5);

            for (var i = 0; i < points.Count - 1; i++)
            {
                var x = points[i].X;
                var y = points[i].Y;

                var x1 = points[i + 1].X;
                var y1 = points[i + 1].Y;

                DrawLineInt(image,new Point(x,y),new Point(x1,y1),pen);
            }
        }

        private static void DrawLineInt(Bitmap bmp,Point p1,Point p2,Pen pen)
        {
            using (var graphics = Graphics.FromImage(bmp))
            {
                graphics.DrawLine(pen,p1.X,p1.Y,p2.X,p2.Y);
            }
        }

        private static List<Point> DrawRaster(int edge,Bitmap image,GraphicsPath path)
        {
            var points = new List<Point>();

            var countHorizontal = image.Width / edge;
            var countVertical = image.Height / edge;

            using (var graphics = Graphics.FromImage(image))
            {
                for (int x = 0; x < countHorizontal; x++)
                {
                    for (int y = 0; y < countVertical; y++)
                    {
                        var boxX = (x * edge) + (edge / 2);
                        var boxY = (y * edge) + (edge / 2);

                        if (!path.IsVisible(boxX,boxY))
                        {
                            continue;
                        }

                        points.Add(new Point(boxX,boxY));

                        graphics.DrawRectangle(Pens.LightGray,x * edge,y * edge,edge,edge);
                    }
                }
            }

            return points;
        }
    }
}