WPF 折線/坐標點繪制 曲線抽稀 (Douglas-Peucker)道格拉斯-普克演算法

這個演算法經常用，例如GIS，資料保存，資料繪制都會用到，

演算法是1973提出的，久經考驗的演算法，具體詳情可以參考百度，

演算法比較簡單，大意是：

① 給出一個限定值表示距離

② 點集合或者坐標集合的首尾自動相連接成為直線，并會記錄首尾兩點到輸出集合

③ 記錄后尋找集合中距離這個直線最遠的點，當這個點的距離超過限定值時，記錄這個點，并由此將集合分為兩段，首到點，點到尾

④ 對每個線段重復步驟②，步驟③，直至結束

也可以參考其他網友給出的演算法推導. 

其中 找出最遠點的點的演算法，可以利用 三個點形成的面積，也就是三角形的面積，

其中求出點到線的距離，也就是三角形的高，

我們可以認為首尾連接的線是底部邊，我們有底部邊的起點和終點坐標，可以利用向量公式，尾坐標減去首坐標，求出向量坐標后，再利用向量的求模公式求出長度，

最后三角形面積除以底的長度乘與2就等于高度了，

截圖

代碼是現成的，雖然實作也不困難， 偷懶....

 public class Douglas_Peucker
    {
        /// <summary>
        /// Douglas-Peucker演算法
        /// </summary>
        /// <param name="Points">坐標點集合</param>
        /// <param name="Tolerance">限定值</param>
        /// <returns></returns>
        public static List<Point> DouglasPeuckerReduction
            (List<Point> Points, Double Tolerance)
        {
            if (Points == null || Points.Count < 3)
                return Points;

            Int32 firstPoint = 0;
            Int32 lastPoint = Points.Count - 1;
            List<Int32> pointIndexsToKeep = new List<Int32>();

            //默認添加首尾兩點
            pointIndexsToKeep.Add(firstPoint);
            pointIndexsToKeep.Add(lastPoint);

            //首尾兩點不能相同
            while (Points[firstPoint].Equals(Points[lastPoint]))
            {
                lastPoint--;
            }
            //遞回計算
            DouglasPeuckerReduction(Points, firstPoint, lastPoint,
            Tolerance, ref pointIndexsToKeep);
            //回傳集合
            List<Point> returnPoints = new List<Point>();
            pointIndexsToKeep.Sort();
            foreach (Int32 index in pointIndexsToKeep)
            {
                returnPoints.Add(Points[index]);
            }

            return returnPoints;
        }

        /// <summary>
        /// 遞回計算每個點到線段的長度，并分段遞回重復計算
        /// </summary>
        /// <param name="points">點集合</param>
        /// <param name="firstPoint">首點</param>
        /// <param name="lastPoint">尾點</param>
        /// <param name="tolerance">限定值</param>
        /// <param name="pointIndexsToKeep">點集合下標</param>
        private static void DouglasPeuckerReduction(List<Point>
            points, Int32 firstPoint, Int32 lastPoint, Double tolerance,
            ref List<Int32> pointIndexsToKeep)
        {
            Double maxDistance = 0;
            Int32 indexFarthest = 0;
            //遍歷每個點
            for (Int32 index = firstPoint; index < lastPoint; index++)
            {
                Double distance = PerpendicularDistance
                    (points[firstPoint], points[lastPoint], points[index]);
                //只尋找線段上最長的點
                if (distance > maxDistance)
                {
                    //替換值
                    maxDistance = distance;
                    //記錄下標
                    indexFarthest = index;
                }
            }
            //確定最大值超過限定值且不為首點
            if (maxDistance > tolerance && indexFarthest != 0)
            {
                //記錄最大距離的點的下標
                pointIndexsToKeep.Add(indexFarthest);
                //分段計算 Startpoint-MaxDistance 
                DouglasPeuckerReduction(points, firstPoint,
                indexFarthest, tolerance, ref pointIndexsToKeep);
                //分段計算 MaxDistance-Lastpoint
                DouglasPeuckerReduction(points, indexFarthest,
                lastPoint, tolerance, ref pointIndexsToKeep);
            }
        }

        /// <summary>
        /// 求出點到兩點的距離
        /// </summary>
        /// <param name="pt1">線段的起點</param>
        /// <param name="pt2">線段的終點</param>
        /// <param name="p">計算的點</param>
        /// <returns></returns>
        public static Double PerpendicularDistance
            (Point Point1, Point Point2, Point Point)
        {
            //Area = |(1/2)(x1y2 + x2y3 + x3y1 - x2y1 - x3y2 - x1y3)|   *Area of triangle
            //Base = v((x1-x2)2+(x1-x2)2)                               *Base of Triangle*
            //Area = .5*Base*H                                          *Solve for height
            //Height = Area/.5/Base
            //求面積
            Double area = Math.Abs(.5 * (Point1.X * Point2.Y + Point2.X *
            Point.Y + Point.X * Point1.Y - Point2.X * Point1.Y - Point.X *
            Point2.Y - Point1.X * Point.Y));
            //求首尾兩點的長度
            Double bottom = Math.Sqrt(Math.Pow(Point1.X - Point2.X, 2) +
            Math.Pow(Point1.Y - Point2.Y, 2));
            //三角形面積除以底*2=高
            //三角形面積除以高*2=底
            Double height = area / bottom * 2;

            return height;

            //Another option
            //Double A = Point.X - Point1.X;
            //Double B = Point.Y - Point1.Y;
            //Double C = Point2.X - Point1.X;
            //Double D = Point2.Y - Point1.Y;

            //Double dot = A * C + B * D;
            //Double len_sq = C * C + D * D;
            //Double param = dot / len_sq;

            //Double xx, yy;

            //if (param < 0)
            //{
            //    xx = Point1.X;
            //    yy = Point1.Y;
            //}
            //else if (param > 1)
            //{
            //    xx = Point2.X;
            //    yy = Point2.Y;
            //}
            //else
            //{
            //    xx = Point1.X + param * C;
            //    yy = Point1.Y + param * D;
            //}

            //Double d = DistanceBetweenOn2DPlane(Point, new Point(xx, yy));
        }
    }

使用這個演算法后，能夠將點減少很多，在視覺上差距不大，適用于很多點的時候，繪制困難，通過這個演算法減少點的數量.

標籤：WPF

上一篇：WPF 折線/坐標點繪制 曲線抽稀 (Douglas-Peucker)道格拉斯-普克演算法

下一篇：C#實作高斯擬合