道格拉斯-普克抽稀算法

using System;
using System.Collections.Generic;
using System.Linq;
using System.Web;

/**
* GeometryModels 坐标对象
* shenlongguang
* https://github.com/ifengkou
*/
namespace L.MapUtil
{
    public enum TransType
    {
        Baidu,
        Mapbar,
        Mars
    }

    public class GeometryModels
    {
    }
    //点
    public class Point
    {
        public double X { set; get; }public double Y { set; get; }
        public Point(double x, double y) { this.X = x; this.Y = y; }
        public Point() { }
    }
    //线
    public class Line
    {
        public Point a { set; get; }public Point b { set; get; }
        public Line(Point start, Point end) { this.a = start; this.b = end; }
    }
    //多边形
    public class Polygon
    {
        public List<Line> Plines { get; set; }
    }
}

using System;
using System.Collections.Generic;

/**
* MassPointCompressUtil 海量点压缩工具
* shenlongguang
* https://github.com/ifengkou
*/
namespace L.MapUtil
{	
    class MassPointCompressUtil
    {
    	 /**
    	 * Points 待压缩点集合
    	 * Tolerance 抽稀阈值
    	 */
        public static List<Point> MassPointCompress
            (List<Point> Points, Double Tolerance)
        {
            //使用普克-道格拉斯 算法 压缩点集合
            if (Points == null || Points.Count < 3|| Tolerance>0)
                return Points;

            Int32 firstPoint = 0;
            Int32 lastPoint = Points.Count - 1;
            //用于保存计算后的所有点的下标
            List<Int32> pointIndexsToKeep = new List<Int32>();
            //Add the first and last index to the keepers
            pointIndexsToKeep.Add(firstPoint);
            pointIndexsToKeep.Add(lastPoint);
            //The first and the last point cannot be the same
            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;
        }

        private static void DouglasPeuckerReduction(List<Point>
            points, Int32 firstPoint, Int32 lastPoint, Double tolerance,
            ref List<Int32> pointIndexsToKeep)
        {
            Double maxDistance = 0;
            Int32 indexFarthest = 0;
            //找出离开始点和结束点连成的直线 最远距离的点。maxDistance为最多距离，indexFarthest，为最远点的下标
            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)
            {
                //Add the largest point that exceeds the tolerance
                pointIndexsToKeep.Add(indexFarthest);
                //分成两部分，进行计算
                DouglasPeuckerReduction(points, firstPoint,
                indexFarthest, tolerance, ref pointIndexsToKeep);
                DouglasPeuckerReduction(points, indexFarthest,
                lastPoint, tolerance, ref pointIndexsToKeep);
            }
        }

        //
        //计算点point到point1和point2连成的直线之间的距离
        private 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)²+(x1-x2)²)                               *Base of Triangle*
            //Area = .5*Base*H                                          *Solve for height
            //Height = Area/.5/Base
            //行列式算法。计算梯形面积- 两边的2个直角三角形面积
            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));//点1到点2的距离
            Double height = area / bottom * 2;

            return height*100000;//*10000 转换为米
        }
    }
}