一颗牛肉丸
0%

抽稀算法

发表于 更新于 分类于 Disqus：

在小程序的论坛中看到有人说地图上加载太多点会有 bug, 心想他不能把这些点抽稀后再显示吗. 遂谷歌了一下, 发现了这个 Ramer-Douglas-Peucker 算法.

参考链接

Ramer-Douglas-Peucker algorithm wiki

曲线点抽稀算法-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
import math
points = [
    [10,10],
    [20,30],
    [30,12],
    [35,5],
    [40,22],
    [50,12],
    [80,40],
]
newPoints = []

def pointDistance(point_a, point_b, point_c):
    k = (point_a[1]-point_c[1])/(point_a[0]-point_c[0])
    b = (point_a[1] - k*point_a[0])
    distance = abs(k*point_b[0]-point_b[1]+b)/(math.sqrt(math.pow(k, 2)+1))
    return distance
def getFarthest(threshold):
    check_index = 1
    while check_index < len(points) - 1:
        distance = pointDistance(
            points[check_index-1], 
            points[check_index], 
            points[check_index+1])
        if distance < threshold:
            check_index += 1
        else:
            newPoints.append(points[check_index])
            check_index += 1
    return newPoints

threshold = 15
newPoints.append(points[0])
getFarthest(threshold)
newPoints.append(points[len(points)-1])
print(newPoints) # [[10, 10], [20, 30], [80, 40]]

Ramer-Douglas-Peucker 算法

思路

代码

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
import math
points = [
    [10,10],
    [20,30],
    [30,12],
    [35,5],
    [40,22],
    [50,12],
    [80,40],
]
newPoints = []

# 计算点到前后两点所连成直线的距离.
def pointDistance(point_a, point_b, point_c):
    k = (point_a[1]-point_c[1])/(point_a[0]-point_c[0])
    b = (point_a[1] - k*point_a[0])
    distance = abs(k*point_b[0]-point_b[1]+b)/(math.sqrt(math.pow(k, 2)+1))
    return distance

def vacuate(checkPoints,threshold):
    if len(checkPoints) == 2:
        return checkPoints
    maxDistance = 0
    index = 1
    maxIndex = 1
    # 获取距离首尾两点所连线段距离最远的点的位置.
    while index < len(checkPoints) - 1:
        distance = pointDistance(
            checkPoints[0], 
            checkPoints[index], 
            checkPoints[len(checkPoints)-1]
        )
        if distance > maxDistance:
            maxDistance = distance
            maxIndex = index
            index += 1
        else:
            index += 1
    # 最远点距离大于阈值.
    if maxDistance >= threshold:
        # 从最远点切分线段, 分别进行计算.
        result1 = vacuate(checkPoints[0:maxIndex+1], threshold)
        result2 = vacuate(checkPoints[maxIndex:len(checkPoints)], threshold)
        result = result1 + result2[1:]
    else:
        result = [checkPoints[0], checkPoints[len(checkPoints)-1]]
    return result
    
threshold = 13
result = vacuate(points,threshold)
print(result)

问题

容易发现点的排序对最后结果有很大的影响, 现实应用中一般用在导航路线的抽稀, 而导航路线可以根据时间来排序, 所以不会有什么问题. 但如果是在面上抽稀点呢? 如统计一个区域内的某种生物的种群数量.