技术

道格拉斯普克算法

道格拉斯普克算法通常用于将轨迹保留大致形状的同时，减少轨迹的点个数。也可用来做基于关键点的轨迹分段。

大致原理如下:
给定一条轨迹

计算切割点：
0.定义切割阈值d
1.将起点和终点连接起来,构成一条线段a。
2.遍历计算除起点终点外所有点到这条直线的距离，直到点到线的距离b≥d，这个点就是需要保留的关键点。
以上图为例:这里从点1开始遍历,发现点c到线段a的距离b大于阈值，则c点就为切割垫。

以c点为切割点，将整个轨迹分为两个子轨迹.

对两个子轨迹重复上述操作，若在遍历过程所有点＜d,则只保留起点与终点即可。若发现有点到线的距离≥d,则继续切割。


Python代码:

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
import math

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    
    def get_point(self):
        return self.x, self.y

def point_to_line_distance(point: Point, start: Point, end: Point):

    """点到线的距离

  

    Args:

        point (_type_): 点坐标(x,y)

        start (_type_): 线段的起点 (x,y)

        end (_type_): 线段的终点(x,y)

  

    Returns:

        float: 点线距离

    """

    x, y = point.get_point()

    x1, y1 = start.get_point()

    x2, y2 = end.get_point()

  

    numerator = abs((y2 - y1) * x - (x2 - x1) * y + x2 * y1 - y2 * x1)

    denominator = ((y2 - y1)**2 + (x2 - x1)**2)**0.5

    if denominator==0:

        distance=0

    else:

        distance=numerator / denominator

    return distance
    
def douglas_peucker(traj, epsilon: float):

    """ 使用道格拉斯-普克算法划分并简化轨迹

  

    Args:

        traj (List[Point]): 轨迹列表

        epsilon (float): 控制分割的阈值

  

    Returns:

        segmented_trajectories: 每个分割段的原始轨迹列表

        simplified_trajectories: 每个分割段的简化轨迹列表    

    """

    if len(traj) < 3:

        return [traj], [traj]

  

    # 计算轨迹中每个点到直线的距离，并找到距离最大的点

    dmax = 0

    index = 0

    end = len(traj) - 1

    for i in range(1, end):

        d = point_to_line_distance(traj[i], traj[0], traj[end])

        if d > dmax:

            index = i

            dmax = d

  

    # 如果最大距离大于阈值，则将轨迹划分为两部分并递归处理

    if dmax > epsilon:

        part1, simplified_part1 = douglas_peucker(traj[:index + 1], epsilon)

        part2, simplified_part2 = douglas_peucker(traj[index:], epsilon)

        return part1 + part2, simplified_part1 + simplified_part2

    else:

        # 对分割后的段进行简化处理

        simplified_traj = [traj[0], traj[end]]

        return [traj], [simplified_traj]

Java代码(GPT转译):

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
import java.util.ArrayList;
import java.util.List;

class Point {
    private double x;
    private double y;

    public Point(double x, double y) {
        this.x = x;
        this.y = y;
    }

    public double getX() {
        return x;
    }

    public double getY() {
        return y;
    }
}

public class DouglasPeuckerAlgorithm {
    public static double pointToLineDistance(Point point, Point start, Point end) {
        double x = point.getX();
        double y = point.getY();
        double x1 = start.getX();
        double y1 = start.getY();
        double x2 = end.getX();
        double y2 = end.getY();

        double numerator = Math.abs((y2 - y1) * x - (x2 - x1) * y + x2 * y1 - y2 * x1);
        double denominator = Math.sqrt(Math.pow((y2 - y1), 2) + Math.pow((x2 - x1), 2));

        double distance;
        if (denominator == 0) {
            distance = 0;
        } else {
            distance = numerator / denominator;
        }
        return distance;
    }

    public static List<List<Point>> douglasPeucker(List<Point> traj, double epsilon) {
        List<List<Point>> segmentedTrajectories = new ArrayList<>();
        List<List<Point>> simplifiedTrajectories = new ArrayList<>();

        if (traj.size() < 3) {
            segmentedTrajectories.add(traj);
            simplifiedTrajectories.add(traj);
            return segmentedTrajectories;
        }

        double dmax = 0;
        int index = 0;
        int end = traj.size() - 1;

        for (int i = 1; i < end; i++) {
            double d = pointToLineDistance(traj.get(i), traj.get(0), traj.get(end));
            if (d > dmax) {
                index = i;
                dmax = d;
            }
        }

        if (dmax > epsilon) {
            List<Point> part1 = douglasPeucker(traj.subList(0, index + 1), epsilon).get(0);
            List<Point> simplifiedPart1 = douglasPeucker(traj.subList(0, index + 1), epsilon).get(1);
            List<Point> part2 = douglasPeucker(traj.subList(index, traj.size()), epsilon).get(0);
            List<Point> simplifiedPart2 = douglasPeucker(traj.subList(index, traj.size()), epsilon).get(1);
            segmentedTrajectories.addAll(part1);
            segmentedTrajectories.addAll(part2);
            simplifiedTrajectories.addAll(simplifiedPart1);
            simplifiedTrajectories.addAll(simplifiedPart2);
            return segmentedTrajectories;
        } else {
            List<Point> simplifiedTraj = new ArrayList<>();
            simplifiedTraj.add(traj.get(0));
            simplifiedTraj.add(traj.get(end));
            segmentedTrajectories.add(traj);
            simplifiedTrajectories.add(simplifiedTraj);
            return simplifiedTrajectories;
        }
    }
}