道格拉斯-普克抽稀算法

道格拉斯-普克抽稀算法,是用来对大量冗余的图形数据点进行压缩以提取必要的数据点。

文章包括三部分

  1. 算法原理
  2. 代码实现(csharp)
  3. 实际应用举例对比(图)

道格拉斯普克算法原理

该算法实现抽稀的过程是:

1)对曲线的首末点虚连一条直线,求曲线上所有点与直线的距离,并找出最大距离值dmax,用dmax与事先给定的阈值D相比:
2)若dmax<D,则将这条曲线上的中间点全部舍去;则该直线段作为曲线的近似,该段曲线处理完毕。
  若dmax≥D,保留dmax对应的坐标点,并以该点为界,把曲线分为两部分,对这两部分重复使用该方法,即重复1),2)步,直到所有dmax均<D,即完成对曲线的抽稀。
 
显然,本算法的抽稀精度也与阈值相关,阈值越大,简化程度越大,点减少的越多,反之,化简程度越低,点保留的越多,形状也越趋于原曲线。

网上找了个示意图:

douglas-peuker.JPG
图一:douglas-peuker 算法示意图 ,来源:百度百科

代码实现

几年前用 c# 封装的一个关于地图的工具包,包含 道格拉斯普克抽稀算法-用于 历史轨迹回放;点面射线算法-用于电子围栏,判断点是否在不规则平面多边形内;各种地图的经纬度纠偏-用于火星坐标和真实坐标的转换(可能存在最近几年地图供应商算法已经改变了);下面给出道格拉斯普克抽稀算法,下一篇说下 平面内判断点在多边形内的射线算法;

坐标对象GeometryModels.cs,包含点,线,多边形的定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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; }
}
}

MassPointCompressUtil.cs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
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 转换为米
}
}
}

实际应用

以前系统10-30秒汇报一次经纬度,所有的点都在地图上绘制,简直反人性化。2012年主导中联GPS应用项目后应用了该算法,目前中联大部分GPS应用相关项目都应用了该算法

10米阀值
图二:2012年 中联搅拌车调度系统,贵阳某客户搅拌车 轨迹回放 ,10米阀值

500米阀值
图三:2012年 中联搅拌车调度系统,贵阳某客户搅拌车 轨迹回放 ,500米阀值

坚持原创技术分享,您的支持将鼓励我继续创作!
分享