轨迹数据压缩算法

TANKING 发布于2019-07-31 11:13 / 2702人阅读

摘要：数据问题解压缩结果计算高主要运行结果列表容差计算通过的内容算法点列表第一个点最后一个点容差轨迹结果原始图压缩图

数据

P0,107.605,137.329
P1,122.274,169.126
P2,132.559,179.311
P3,153.324,184.276
P4,171.884,174.654
P5,186.408,168.634
P6,196.566,145.204
P7,200.549,127.877
P8,211.391,118.179
P9,216.318,116.547
P10,225.197,122.796
P11,231.064,135.459
P12,240.835,143.398
P13,254.630,144.933
P14,265.055,158.761
P15,271.004,159.660
P16,274.474,173.979

问题

解

import math

# 压缩结果
Compressed = list()


class Point(object):
    def __init__(self, id, x, y):
        self.id = id
        self.x = x
        self.y = y


def read_m(path):
    m = []
    with open(path, "r") as f:
        for i in f.readlines():
            aa = i.replace("
", "").split(",")
            p = Point(aa[0], eval(aa[1]), eval(aa[2]))
            m.append(p)

    return m


def calc_height(point1, point2, point):
    """
    计算高
    :param point1: Point
    :param point2: Point
    :param point: Point
    :return:
    """
    area = abs(0.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))

    bottom = math.sqrt(
        math.pow(point1.x - point2.x, 2) + math.pow(point1.y - point2.y, 2)
    )

    height = area / bottom * 2
    return height


def DPmain(pointList, tolerance):
    """
    主要运行结果
    :param pointList: Point 列表
    :param tolerance: 容差
    :return:
    """
    if pointList == None or pointList.__len__() < 3:
        return pointList

    firspoint = 0
    lastPoint = len(pointList) - 1

    Compressed.append(pointList[firspoint])
    Compressed.append(pointList[lastPoint])

    while (pointList[firspoint] == pointList[lastPoint]):
        lastPoint -= 1
    DouglasPeucker(pointList, firspoint, lastPoint, tolerance)



def DouglasPeucker(pointList, firsPoint, lastPoint, tolerance):
    """
    计算通过的内容
    DP算法
    :param pointList: 点列表
    :param firsPoint: 第一个点
    :param lastPoint: 最后一个点
    :param tolerance: 容差
    :return:
    """
    maxDistance = 0.0
    indexFarthest = 0
    for i in range(firsPoint, lastPoint):
        distance = calc_height(pointList[firsPoint], pointList[lastPoint], pointList[i])
        if (distance > maxDistance):
            maxDistance = distance
            indexFarthest = i

    if maxDistance > tolerance and indexFarthest != 0:
        Compressed.append(pointList[indexFarthest])
        DouglasPeucker(pointList, firsPoint, indexFarthest, tolerance)
        DouglasPeucker(pointList, indexFarthest, lastPoint, tolerance)


if __name__ == "__main__":
    a = read_m("轨迹.txt")
    print(a.__len__())
    # for item in a:
    #     print(item.id, item.x, item.y)
    DPmain(a, 8)
    for i in Compressed:
        print("{},{},{}".format(i.id, i.x, i.y))

结果

P0,107.605,137.329
P16,274.474,173.979
P9,216.318,116.547
P3,153.324,184.276
P1,122.274,169.126
P5,186.408,168.634
P7,200.549,127.877

原始图

压缩图

海外云主机服务器托管轨迹产生算法字典压缩算法最快压缩算法最强压缩算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/44818.html

地图匹配算法实践

摘要：在实际应用中，采样信号的质量会严重影响地图匹配结果采样频率的降低定位误差的加大信号的丢失，都会使匹配的不准确性增加。年首次设立的竞赛，其内容就是地图匹配。地图匹配算法综述以使用到的信息来划分现有的算法可被分成四类几何拓扑概率高级。 1 背景如下图所示，1、2、3 这三个点是汽车的GPS定位结果，尽管汽车是在道路上，但定位结果与道路存在偏差。地图匹配（Map Matching）是指将行...

nihao 2019-08-22 16:22 评论0 收藏0
地图匹配算法实践

摘要：在实际应用中，采样信号的质量会严重影响地图匹配结果采样频率的降低定位误差的加大信号的丢失，都会使匹配的不准确性增加。年首次设立的竞赛，其内容就是地图匹配。地图匹配算法综述以使用到的信息来划分现有的算法可被分成四类几何拓扑概率高级。 1 背景如下图所示，1、2、3 这三个点是汽车的GPS定位结果，尽管汽车是在道路上，但定位结果与道路存在偏差。地图匹配（Map Matching）是指将行...

bluesky 2019-08-02 10:13 评论0 收藏0
算法学习 >> 快速理解算法运行轨迹

摘要：算法的学习是枯燥无味的，如何快速理解和提高学习的乐趣理解复杂数据结构的最佳方法是看到它们的实际运行。废话不多说了，直接上网址了主页算法算法列表希望对爱好算法的你有帮助谢谢。算法的学习是枯燥无味的，如何快速理解和提高学习的乐趣？理解复杂数据结构的最佳方法是看到它们的实际运行。今天给大家推荐一个网址、它已经为各种数据结构和算法开发了交互式动画，这样有助于我们更直观的去理解和学习各种数据...

MonoLog 2019-08-19 11:45 评论0 收藏0
「不良视频」如何消灭？她手把手教你走出第一步

摘要：严肃的开场白故事要从深度学习说起。本文从视频分类的角度，对深度学习在该方向上的算法进行总结。数据集熟悉深度学习的朋友们应该清楚，深度学习是一门数据驱动的技术，因此数据集对于算法的研究起着非常重要的作用。是一个比较成功的传统方法与深度学习算 showImg(https://segmentfault.com/img/bV7hQP?w=900&h=330); 不严肃的开场白视频社交已经成为...

Invoker 2019-06-21 16:17 评论0 收藏0