.net中使用 道格拉斯-普特 抽希轨迹点

Douglas一Peukcer算法由D.Douglas和T.Peueker于1973年提出，简称D一P算法，是目前公认的线状要素化简经典算法。现有的线化简算法中，有相当一部分都是在该算法基础上进行改进产生的。它的优点是具有平移和旋转不变性，给定曲线与阂值后，抽样结果一定。

思路:对每一条曲线的首末点虚连一条直线,求所有点与直线的距离,并找出最大距离值dmax ,用dmax与限差D相比:若dmax < D ,这条曲线上的中间点全部舍去;若dmax ≥D ,保留dmax 对应的坐标点,并以该点为界,把曲线分为两部分,对这两部分重复使用该方法。

GpsPositionDto

public class GpsPositionDto

	{

		/// <summary>

		/// 转换后的纬度

		/// </summary>

		public decimal GpsWebLng { get; set; }

		/// <summary>

		/// 转换后的经度

		/// </summary>

		public decimal GpsWebLat { get; set; }

		/// <summary>

		/// 时间

		/// </summary>

		public DateTime Gpstime { get; set; }

                //其他参数自己加

}

　　

/// <summary>

	/// 道格拉斯-普特

	/// </summary>

	public class DouglasPeucker

	{

		/// <summary>

		/// 距离

		/// </summary>

		/// <param name="point1"></param>

		/// <param name="point2"></param>

		/// <returns></returns>

		public static double CalculationDistance(GpsPositionDto point1, GpsPositionDto point2)

		{

			var lat1 = (double)point1.GpsWebLat;

			var lat2 = (double)point2.GpsWebLat;

			var lng1 = (double)point1.GpsWebLng;

			var lng2 = (double)point2.GpsWebLng;

			var radLat1 = lat1 * Math.PI / 180.0;

			var radLat2 = lat2 * Math.PI / 180.0;

			var a = radLat1 - radLat2;

			var b = (lng1 * Math.PI / 180.0) - (lng2 * Math.PI / 180.0);

			var s = 2 * Math.Asin(Math.Sqrt(Math.Pow(Math.Sin(a / 2), 2)

				+ Math.Cos(radLat1) * Math.Cos(radLat2) * Math.Pow(Math.Sin(b / 2), 2)));

			return s * 6370996.81;

		}

		/// <summary>

		/// 直线距离

		/// </summary>

		/// <param name="start"></param>

		/// <param name="end"></param>

		/// <param name="center"></param>

		/// <returns></returns>

		public static double DistToSegment(GpsPositionDto start, GpsPositionDto end, GpsPositionDto center)

		{

			var a = Math.Abs(CalculationDistance(start, end));

			var b = Math.Abs(CalculationDistance(start, center));

			var c = Math.Abs(CalculationDistance(end, center));

			var p = (a + b + c) / 2.0;

			var s = Math.Sqrt(Math.Abs(p * (p - a) * (p - b) * (p - c)));

			return s * 2.0 / a;

		}

		/// <summary>

		/// 递归方式压缩轨迹

		/// </summary>

		/// <param name="coordinate"></param>

		/// <param name="result"></param>

		/// <param name="start"></param>

		/// <param name="end"></param>

		/// <param name="dMax"></param>

		/// <returns></returns>

		public static IList<GpsPositionDto> CompressLine(IList<GpsPositionDto> coordinate, IList<GpsPositionDto> result, int start, int end, double dMax)

		{

			if (start < end)

			{

				var maxDist = 0D;

				var currentIndex = 0;

				var startPoint = coordinate[start];

				var endPoint = coordinate[end];

				for (var i = start + 1; i < end; i++)

				{

					var currentDist = DistToSegment(startPoint, endPoint, coordinate[i]);

					if (currentDist > maxDist)

					{

						maxDist = currentDist;

						currentIndex = i;

					}

				}

				if (maxDist >= dMax)

				{

					//将当前点加入到过滤数组中

					result.Add(coordinate[currentIndex]);

					//将原来的线段以当前点为中心拆成两段，分别进行递归处理

					CompressLine(coordinate, result, start, currentIndex, dMax);

					CompressLine(coordinate, result, currentIndex, end, dMax);

				}

			}

			return result;

		}

		/// <summary>

		/// 抽希

		/// </summary>

		/// <param name="coordinate">原始轨迹Array</param>

		/// <param name="dMax">允许最大距离误差</param>

		/// <returns>抽稀后的轨迹</returns>

		public static IList<GpsPositionDto> Dilution(IList<GpsPositionDto> coordinate, double dMax = 10)

		{

			if (!(coordinate.Count > 2))

			{

				return null;

			}

			var result = CompressLine(coordinate, new List<GpsPositionDto>(), 0, coordinate.Count - 1, dMax);

			result.Add(coordinate[0]);

			result.Add(coordinate[coordinate.Count - 1]);

			//排序

			var resultLatLng = result.OrderBy(s => s.Gpstime).ToList();

			return resultLatLng;

		}

	}