道格拉斯-普克算法
是什么
是一种用于简化曲线或折线的算法。它通过减少构成曲线的点的数量,同时尽可能保留曲线的形状,从而实现数据的压缩和简化。该算法在计算机图形学、地理信息系统(GIS)和地图绘制等领域中广泛应用。
应用场景
在渲染轨迹时,原始的轨迹点本来就已经很密集了,再经过平滑插值之后,密集程度更是翻倍。
在下图中可见,直线的中间区域,没有什么信息量的地方,却有大量的三角面被不必要地渲染。
因此,我想把这条轨迹的特征提取出来,只保留直线的开头和结尾的特征点,丢掉中间没用的点。
可以使用 道格拉斯-普克算法。
源数据有100多个点,处理之后只保留了14个关键特征点。
数据量大大减少,筛选掉了不必要的细节。
核心思想
递归地选择关键点,丢弃对曲线形状影响较小的点。
一、初始化
- 选择曲线的起点和终点作为初始关键点。
- 将这两点之间的所有点作为候选点。
二、递归处理
- 对于两个关键点之间的所有候选点,计算每个候选点到这两个关键点连线的所在直线的距离。
- 找到距离最远的点,如果其距离大于预设的阈值(ε),则将曲线分成两段,该点作为前一段的第二个关键点和后一段的第一个关键点,并递归地对这两段子曲线重复上述过程。
- 如果所有点的距离都小于阈值,则丢弃这些点,保留当前的关键点。
三、终止条件
当所有子曲线都处理完毕,且没有新的关键点被添加时,算法结束。
代码
/// <summary>
/// 使用道格拉斯-普克算法简化轨迹
/// </summary>
/// <param name="points">轨迹点的集合</param>
/// <param name="epsilon">移除距离线段一定距离的点,单位:像素</param>
/// <returns></returns>
public static List<Vector2> Simplify(List<Vector2> points, float epsilon = 20)
{
if (points.Count < 3) return points;
// 找到离首尾连线最远的点
float maxDistance = 0;
int index = 0;
LineSegment segment = new LineSegment(points[0], points[points.Count - 1]);
for (int i = 1; i < points.Count - 1; i++)
{
float distance = segment.DistanceToPoint(points[i]);
if (distance > maxDistance)
{
maxDistance = distance;
index = i;
}
}
// 递归处理子分段
if (maxDistance > epsilon)
{
List<Vector2> firstPart = Simplify(points.GetRange(0, index + 1), epsilon);
List<Vector2> secondPart = Simplify(points.GetRange(index, points.Count - index), epsilon);
return firstPart.Take(firstPart.Count - 1)
.Concat(secondPart)
.ToList();
}
else
{
// 直接保留首尾点
return new List<Vector2> { points[0], points[points.Count - 1] };
}
}
// 线段结构体辅助计算
private struct LineSegment
{
public readonly Vector2 Start;
public readonly Vector2 End;
public LineSegment(Vector2 start, Vector2 end)
{
Start = start;
End = end;
}
// 计算点到线段的垂直距离
public float DistanceToPoint(Vector2 point)
{
float lengthSqr = (End - Start).sqrMagnitude;
if (lengthSqr == 0) return Vector2.Distance(point, Start);
float t = Vector2.Dot(point - Start, End - Start) / lengthSqr;
t = Mathf.Clamp01(t);
Vector2 projection = Start + t * (End - Start);
return Vector2.Distance(point, projection);
}
}
注:epsilon需要通过多次测试,寻找出一个合适的值。阈值越大,线条越简单。