這個演算法經常用，例如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)); } }
使用這個演算法后，能夠將點減少很多，在視覺上差距不大，適用于很多點的時候，繪制困難，通過這個演算法減少點的數量.
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/272415.html
標籤：.NET技术
上一篇：Access System.Data.OleDb.OleDbException:“標準運算式中資料型別不匹配。”