多边形寻找从起点到终点的最短路径

Question

我正在寻找多边形（路径）中的最短路径。它从左下角的中心边界（蓝色）开始，以右上角的中心边界（红色）结束。不允许离开路径。

我可以使用哪种算法来计算这条路线？我需要一个点列表来绘制最短路径。例子代码会很好。

我的多边形起点和终点示例

var points = new List<Point> { new Point(210, 540), new Point(330, 420), new Point(360, 420), new Point(420, 390), new Point(450, 330), new Point(480, 315), new Point(510, 270), new Point(570, 240), new Point(630, 240), new Point(690, 180), new Point(750, 150), new Point(810, 120), new Point(864, 120), new Point(864, 60), new Point(810, 60), new Point(750, 90), new Point(690, 120), new Point(630, 150), new Point(570, 150), new Point(510, 210), new Point(480, 255), new Point(450, 270), new Point(420, 330), new Point(360, 360), new Point(330, 360), new Point(156, 480) };

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

image.Save("example.bmp");

- live2

---

一种“简单”的方法是将你的多边形放置在虚拟网格中，然后使用A*算法来寻找路径。 - Gusman

我会选择一种凸包算法。如果路径复杂，可能需要换侧。 - gdir

请查看 Dijkstra 算法。 - Ben

一个限制问题的观察：在任意多边形内两点之间的最短路径是一条分段线性路径，路径的顶点将是目标端点或多边形的某些凹顶点（指向内部的顶点）。 - Kyle

Answer 1

解决方案

感谢 @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, 540), new Point(330, 420), new Point(360, 420), new Point(420, 390), new Point(450, 330), new Point(480, 315), new Point(510, 270), new Point(570, 240), new Point(630, 240), new Point(690, 180), new Point(750, 150), new Point(810, 120), new Point(864, 120), new Point(864, 60), new Point(810, 60), new Point(750, 90), new Point(690, 120), new Point(630, 150), new Point(570, 150), new Point(510, 210), new Point(480, 255), new Point(450, 270), new Point(420, 330), new Point(360, 360), new Point(330, 360), new Point(156, 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, 190, 500, 10, 10, 0, 360);
                graphics.FillPie(Brushes.Red, 840, 80, 10, 10, 0, 360);
                graphics.DrawPolygon(new Pen(Color.Black, 2), 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;
        }
    }
}

- live2

---

那看起来不像是最短的路径。假设您从蓝点开始：在第一次接触墙壁和红点之间的部分，路径不应再次接触墙壁。那部分应该是一条直线。 - gdir

@gdir 我认为这是光栅的问题，你有凸包的示例吗？ - live2

不，我没有针对那个问题的现成实现。我已经使用凸包算法解决了不同的问题，但是代码不适用于你的问题。我建议从起点和终点之间的直线开始。然后检查直线是否与墙的一侧相交。如果是，则找到距离该直线最远的墙侧上的点。然后将您的路径分为两部分：从起点到墙上点的直线和从墙上点到终点的直线。然后在这两条直线上递归应用相同的步骤。 - gdir