寻路算法---基于AutoCAD二次开发

在CAD中绘制首尾相连的直线，并据此构件点与点之间的连接关系，考虑到可能会有线连接的地方有一定的距离delta

点的信息，用于最开始情况下的点的信息集合

    /// <summary>
    /// 点对应的信息
    /// </summary>
    public class QjPointInfo
    {
        /// <summary>
        /// QjPoint
        /// </summary>
        public QjPoint point;
        /// <summary>
        /// 对应的QjCurve
        /// </summary>
        public QjCurve curve;
        /// <summary>
        /// 对应曲线另一个端点的信息
        /// </summary>
        public QjPointInfo qjPointInfo;

        public QjPointInfo(QjPoint point, QjCurve curve)
        {
            this.point = point;
            this.curve = curve;
        }
    }

QjPoint用于对应点的连接关系

 /// <summary>
 /// 对应点的连接关系
 /// </summary>
 public class QjPoint
 {
     /// <summary>
     /// 对应的当前点
     /// </summary>
     public Point3d point;
     /// <summary>
     /// 对应另一个点和连接另一个点的曲线
     /// </summary>
     public Dictionary<QjPoint,Curve> pcDict;
     /// <summary>
     /// 用于Dijkstra算法
     /// </summary>
     public Connect connect;
     /// <summary>
     /// 唯一编码，用于比较
     /// </summary>
     public string id;
     public double X
     {
         get { return point.X; }
     }

     public QjPoint(Point3d point)
     {
         this.point = point;
         pcDict = new Dictionary<QjPoint, Curve>();
         connect = new Connect();
         id = Guid.NewGuid().ToString();
     }

     public double DistanceTo(QjPoint qjPoint)
     {
         return this.point.DistanceTo(qjPoint.point);
     }
     /// <summary>
     /// 初始化Dijkstra的信息
     /// </summary>
     public void InitConnect()
     {
         connect = new Connect();
     }

 }

 public class Connect
 {
     /// <summary>
     /// 对应最短路径的上一个点
     /// </summary>
     public QjPoint path;
     /// <summary>
     /// 对应连接上一个点的曲线
     /// </summary>
     public Curve curve;
     /// <summary>
     /// 距离起始点的距离
     /// </summary>
     public double dis;
     /// <summary>
     /// 是否已经用过
     /// </summary>
     public bool visted;

     public Connect()
     {
         path = null;
         curve = null;
         dis = double.MaxValue;
         visted = false;
     }
 }

QjCurve用于记录每一条曲线的起始点、曲线和终止点

    public class QjCurve
    {
        public QjPoint startPoint;
        public QjPoint endPoint;
        public Curve curve;
        public QjCurve(Curve curve,QjPoint startPoint,QjPoint endPoint )
        {
            this.curve = curve;
            this.startPoint = startPoint;
            this.endPoint = endPoint;
        }
    }

首先需要构建所有的曲线信息

public void InitQjCurvesDict(List<Curve> curves, out List<QjPoint> qjPoints, out List<QjCurve> qjCurves)
{
    qjPoints = new List<QjPoint>();
    qjCurves = new List<QjCurve>();
    List<QjPointInfo> pointInfos = new List<QjPointInfo>();

    for (int i = 0; i < curves.Count; i++)
    {
        Curve curve = curves[i];
        ///创建曲线对应的起始点和终止点QjPoint
        QjPoint startPoint = new QjPoint(curve.StartPoint);
        QjPoint endPoint = new QjPoint(curve.EndPoint);
        ///创建QjCurve
        QjCurve qjCurve = new QjCurve(curve, startPoint, endPoint);
        qjCurves.Add(qjCurve);
        ///创建QjPointInfo
        QjPointInfo p1 = new QjPointInfo(startPoint, qjCurve);
        QjPointInfo p2 = new QjPointInfo(endPoint, qjCurve);

        p1.qjPointInfo = p2;
        p2.qjPointInfo = p1;

        pointInfos.Add(p1);
        pointInfos.Add(p2);
    }


    ///对所有点进行排序 为后续扫描线方法坐做准备
    pointInfos = pointInfos.OrderBy(p => p.point.X).ToList();
    ///扫描线方法需要的一个记录临时点集的points
    List<QjPointInfo> tempPointInfos = new List<QjPointInfo>();

    ///用于合并可认为视为同一个点的qjpoins
    Dictionary<QjPoint, List<QjCurve>> pcDict = new Dictionary<QjPoint, List<QjCurve>>();

    for (int i = 0; i < pointInfos.Count; i++)
    {
        QjPointInfo qjPointInfo = pointInfos[i];
        for (int j = 0; j < tempPointInfos.Count; j++)
        {
            QjPointInfo tempPointInfo = tempPointInfos[j];
            ///当点的X坐标小于当前的qjpoint，并且距离大于delta，
            ///保证在一定距离范围内的顶点视为同一个点
            ///就将其从tempPointInfos中移出，扫描线方法的核心
            if (tempPointInfo.point.X < qjPointInfo.point.X &&
                tempPointInfo.point.DistanceTo(qjPointInfo.point) > delta)
            {
                tempPointInfos.RemoveAt(j);
                j--;
            }
        }

        bool isContain = Solve(qjPointInfo, tempPointInfos);
        if (!isContain)
        {
            pcDict.Add(qjPointInfo.point, new List<QjCurve>());
        }
        pcDict[qjPointInfo.point].Add(qjPointInfo.curve);
        tempPointInfos.Add(qjPointInfo);
    }

    qjPoints = new List<QjPoint>();
    ///根据pcDict将qjpoint重铸，形成点和点的对应关系
    foreach (var item in pcDict)
    {
        QjPoint qjPoint = item.Key;
        for (int j = 0; j < item.Value.Count; j++)
        {
            if (qjPoint.point == item.Value[j].startPoint.point)
            {
                qjPoint.pcDict.Add(item.Value[j].endPoint, item.Value[j].curve);
            }
            else
            {
                qjPoint.pcDict.Add(item.Value[j].startPoint, item.Value[j].curve);
            }
        }
        qjPoints.Add(qjPoint);
    }
}


 /// <summary>
 /// 在tempPoints中找到qjpoint是否有重合的点，并且对qjpoint点的位置进行重置
 /// </summary>
 /// <param name="qjPointInfo"></param>
 /// <param name="tempPointInfos"></param>
 /// <returns></returns>
 public bool Solve(QjPointInfo qjPointInfo, List<QjPointInfo> tempPointInfos)
 {
     bool isContain = false;
     for (int i = 0; i < tempPointInfos.Count; i++)
     {
         if (qjPointInfo.point.DistanceTo(tempPointInfos[i].point) < delta)
         {
             if (qjPointInfo.curve.startPoint == qjPointInfo.point)
             {
                 qjPointInfo.curve.startPoint = tempPointInfos[i].point;
             }
             else
             {
                 qjPointInfo.curve.endPoint = tempPointInfos[i].point;
             }
             qjPointInfo.point = tempPointInfos[i].point;
             isContain = true;
         }
     }
     return isContain;
 }

 ///根据起始点、终止点利用Dijkstra算法找到最短路径

private List<Curve> GetCurvesByTwoPointAnQjCurves(Point3d pS, Point3d pE, List<QjPoint> qjPoints, List<QjCurve> qjCurves)
        {
            ///首先对所有的qjpoint的connect信息初始化
            qjPoints.ForEach(qjPoint => qjPoint.InitConnect());

            ///找到对应的起始点和终止点的qjpoint
            QjPoint qjStartPoint = GetPoint(pS, qjCurves, out Point3d clostPt1, out QjCurve qjCurve1);
            QjPoint qjEndPoint = GetPoint(pE, qjCurves, out Point3d clostPt2, out QjCurve qjCurve2);
            ///将起点到起点的dis设置为0，visted设置为true
            qjStartPoint.connect.dis = 0;
            qjStartPoint.connect.visted = true;

            Solve(qjStartPoint);
            List<Curve> ljQjCurves = new List<Curve>();

            while (true)
            {
                if (qjEndPoint.id == qjStartPoint.id || qjEndPoint.connect.curve == null)
                {
                    break;
                }
                Curve curve = qjEndPoint.connect.curve.Clone() as Curve;
                ljQjCurves.Add(curve);
                qjEndPoint = qjEndPoint.connect.path;
            }

            //调整起始点
            //如果起始点在起始的Curve上，那么就根据最后的的Curve和下一个curve来区分出Curve并进行替换
            if (clostPt1.DistanceTo(ljQjCurves.Last().GetClosestPointTo(clostPt1, false)) < 0.0001)
            {
                Curve curve = GetCurve(ljQjCurves[ljQjCurves.Count - 1], ljQjCurves[ljQjCurves.Count - 2], clostPt1);
                ljQjCurves[ljQjCurves.Count - 1] = curve;
            }
            //如果起始点不在起始的Curve上，那么就根据现有的Curve和最后的curve来区分出Curve进行Insert
            else
            {
                Curve curve = GetCurve(qjCurve1.curve, ljQjCurves[ljQjCurves.Count - 1], clostPt1);
                ljQjCurves.Add(curve);
            }
            Line line = new Line(pS, clostPt1);
            ljQjCurves.Add(line);

            //调整终止点
            if (clostPt2.DistanceTo(ljQjCurves.First().GetClosestPointTo(clostPt2, false)) < 0.01)
            {
                Curve curve = GetCurve(ljQjCurves[0], ljQjCurves[1], clostPt2);
                ljQjCurves[0] = curve;
            }
            else
            {
                Curve curve = GetCurve(qjCurve2.curve, ljQjCurves[0], clostPt2);
                ljQjCurves.Insert(0, curve);
            }
            line = new Line(pE, clostPt2);
            ljQjCurves.Insert(0, line);

            return ljQjCurves;
        }

 /// <summary>
 /// 最开始初始化startPoint的适合要将startPoint的dis初始化为0
 /// </summary>
 /// <param name="startPoint"></param>
 /// <param name="endPoint"></param>
 /// <param name="qjPoints"></param>
 public void Solve(QjPoint startPoint)
 {
     ///使用队列进行BFS算法来形成所有点到起点的最短路径
     Queue<QjPoint> qjPointQueue = new Queue<QjPoint>();
     qjPointQueue.Enqueue(startPoint);
     while (qjPointQueue.Count() != 0)
     {
         QjPoint qjPoint = qjPointQueue.Dequeue();
         qjPoint.connect.visted = true;
         foreach (var item in qjPoint.pcDict)
         {
             double dis = qjPoint.connect.dis + item.Value.Ex_GetLength();
             if (dis < item.Key.connect.dis)
             {
                 item.Key.connect.dis = dis;
                 item.Key.connect.path = qjPoint;
                 item.Key.connect.curve = item.Value;
             }
         }
         var keys = qjPoint.pcDict.Keys.OrderBy(k => k.connect.dis);

         foreach (var key in keys)
         {
             if (key.connect.visted == false)
             {
                 qjPointQueue.Enqueue(key);
             }
         }
     }
 }