blocks|key|658221|text|查看用于简化多边形的Douglas+Peucker+Algorithm。我已经成功地使用了这一点，以减少gps航点的数量时，传输到客户的显示目的。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|658222|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Ramer%25E2%2580%2593Douglas%25E2%2580%2593Peucker_algorithm^0|A|P|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

check out the <a href="http://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm" rel="noreferrer">Douglas Peucker Algorithm</a> which is used to simplify a polygon. i´ve used this successfully to reduce the amount of gps waypoints when trasmitted to clients for displaying purposes.

blocks|key|2193167|text|有一篇关于Compressing+GPS+Data+on+Mobile+Devices的研究论文。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|2193168|此外，您还可以在Writing+GPS+Applications上查看这篇CodeProject文章。我认为你遇到的问题不是笔直的点，而是弯道。这完全取决于你希望你的路径有多精确。|2193169|entityMap|0|LINK|mutability|MUTABLE|url|http://www.springerlink.com/content/e3540p208g266733/|1|http://www.codeproject.com/KB/mobile/WritingGPSApplications2.aspx^0|5|12|0|0|8|O|1|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@$A|Q|B|R|1|S]]|C|$]]|$1|D|3|E|5|6|7|T|8|@]|9|@$A|U|B|V|1|W]]|C|$]]|$1|F|3|-4|5|6|7|X|8|@]|9|@]|C|$]]]|G|$H|$5|I|J|K|C|$L|M]]|N|$5|I|J|K|C|$L|O]]]]

There is a research paper on <a href="http://www.springerlink.com/content/e3540p208g266733/" rel="nofollow noreferrer">Compressing GPS Data on Mobile Devices</a>. 

Additionally, you can look at this CodeProject article on <a href="http://www.codeproject.com/KB/mobile/WritingGPSApplications2.aspx" rel="nofollow noreferrer">Writing GPS Applications</a>. I think the problem you will have is not for straight points, but curved roads. It all depends on how precise you want your path to be.

blocks|key|1958939|text|你可能想用多项式近似来近似你的路径x(t)，y(t)。你在找这样的东西吗：http://www.youtube.com/watch?v=YtcZXlKbDJY？|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1958940|entityMap|0|LINK|mutability|MUTABLE|url|http://www.youtube.com/watch?v=YtcZXlKbDJY^0|11|16|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

You probably want to approximate your path x(t), y(t) with a polynomial approximation of it. Are you looking for something like this: <a href="http://www.youtube.com/watch?v=YtcZXlKbDJY" rel="nofollow noreferrer">http://www.youtube.com/watch?v=YtcZXlKbDJY</a> ???

blocks|key|658247|text|可以通过基于后续点之间的坡度计算执行非常基本的简化来删除冗余点。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|658248|下面是一小段但不完整的C%2B%2B代码，介绍了可能的算法：|658249|struct+Point
{
+++double+x;
+++double+y;
};

double+calculate_slope(Point+const&+p1,+Point+const&+p2)
{
++++//++++++dy+++++y2+-+y1
++++//+m+=+----+=+---------
++++//++++++dx+++++x2+-+x1
++++return+((p2.y+-+p1.y)+/+(p2.x+-+p1.x));
}

//+1.+Read+first+two+points+from+GPS+stream+source
Point+p0+=+...+;
Point+p1+=+...+;

//+2.+Accept+p0+as+it's+first+point

//+3.+Calculate+slope
double+m0+=+calculate_slope(p0,+p1);

//+4.+next+point+is+now+previous
p0+=+p1;

//+5.+Read+another+point
p1+=+...+;
double+m1+=+calculate_slope(p0,+p1);

//+6.+Eliminate+Compare+slopes
double+const+tolerance+=+0.1;+//+choose+your+tolerance
double+const+diff+=+m0+-+m1;
bool+if+(!((diff+<=+tolerance)+&&+(diff+>=+-tolerance)))
{
++++//+7.+Accept+p0+and+eliminate+p1

++++m0+=+m1;
}

//+Repeat+steps+from+4+to+7+for+the+rest+of+points.|code-block|syntax|javascript|658250|我希望它能帮上忙。|658251|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|N|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|O|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|P|8|@]|9|@]|A|$]]|$1|K|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|L|$]]

You can remove redundant points by performing a very basic simplification based on calculation of slope between subsequent points.

Here is a bit of but not complete C++ code presenting possible algorithm:

<pre><code>struct Point
{
 double x;
 double y;
};

double calculate_slope(Point const&amp; p1, Point const&amp; p2)
{
 // dy y2 - y1
 // m = ---- = ---------
 // dx x2 - x1
 return ((p2.y - p1.y) / (p2.x - p1.x));
}

// 1. Read first two points from GPS stream source
Point p0 = ... ;
Point p1 = ... ;

// 2. Accept p0 as it's first point

// 3. Calculate slope
double m0 = calculate_slope(p0, p1);

// 4. next point is now previous
p0 = p1;

// 5. Read another point
p1 = ... ;
double m1 = calculate_slope(p0, p1);

// 6. Eliminate Compare slopes
double const tolerance = 0.1; // choose your tolerance
double const diff = m0 - m1;
bool if (!((diff &lt;= tolerance) &amp;&amp; (diff &gt;= -tolerance)))
{
 // 7. Accept p0 and eliminate p1

 m0 = m1;
}

// Repeat steps from 4 to 7 for the rest of points.
</code></pre>

I hope it helps.

blocks|key|2193402|text|上面给出的代码有几个问题，可能会使它不合适：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2193403|2193404|“同一坡度”容差衡量的是坡度而不是角度的差异，因此NNE到NNW的差异被认为比NE到SE的差异要大得多(假设y轴是从北到南的)。|unordered-list-item|2193405|2193406|解决这个问题的一种方法是使用公差来测量两个线段的点积与其长度的乘积的比较。(记住两个向量的点积是它们的长度和它们之间夹角的余弦的乘积，这可能有助于理解。)但是，请参见next+point.|2193407|Considers+only+slope+error而不是position，因此长ENE段后跟长ESE段被压缩为单个段的可能性与在ENE和ESE之间交替的一串短段相同。|2193408|2193409|我正在考虑的方法是查看矢量图形应用程序如何将光标坐标列表转换为一系列曲线。例如，参见lib2geom的bezier-utils.cpp。请注意，(i)它几乎完全基于位置，而不是基于方向；(ii)它将三次贝塞尔曲线作为输出，而不是折线，尽管您可以使用相同的方法来提供折线输出(在这种情况下，牛顿-拉夫森步长本质上只是一个简单的点积)。|2193410|entityMap^0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]|$1|C|3|D|5|E|7|R|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|S|8|@]|9|@]|A|$]]|$1|G|3|H|5|6|7|T|8|@]|9|@]|A|$]]|$1|I|3|J|5|E|7|U|8|@]|9|@]|A|$]]|$1|K|3|-4|5|6|7|V|8|@]|9|@]|A|$]]|$1|L|3|M|5|6|7|W|8|@]|9|@]|A|$]]|$1|N|3|-4|5|6|7|X|8|@]|9|@]|A|$]]]|O|$]]

The code given above has a couple of issues that might make it unsuitable:

<ul>
<li>"same slope" tolerance measures difference in gradient rather than angle, so NNE to NNW is considered a much bigger difference than NE to SE (assuming y axis runs North-South).

One way of addressing this would be for the tolerance to measure how the dot product of two segments compares with the product of their lengths. (It might help understanding to remember that dot product of two vectors is the product of their lengths and the cosine of the angle between them.) However, see next point.</li>
<li>Considers only slope error rather than position error, so a long ENE segment followed by long ESE segment is just as likely to be compressed to a single segment as a string of short segments alternating between ENE and ESE.</li>
</ul>

The approach that I was thinking of would be to look at what vector graphics applications do to convert a list of cursor coordinates into a sequence of curves. E.g. see lib2geom's bezier-utils.cpp. Note that (i) it's almost entirely position-based rather than direction-based; and (ii) it gives cubic bézier curves as output rather than a polyline, though you could use the same approach to give polyline output if that's preferred (in which case the Newton-Raphson step becomes essentially just a simple dot product).

I have a device that records GPS data. A reading is taken every 2-10 seconds. For an activity taking 2 hours there are a lot of GPS points.

Does anyone know of an algorithm for compressing the dataset by removing redundant data points. i.e. If a series of data points are all in a straight line then only the start and end point are required.

Compressing GPS Points

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

我有一个可以记录GPS数据的设备。每2-10秒读取一次读数。对于一个需要2个小时的活动，有很多GPS点。有没有人知道通过删除冗余数据点来压缩数据集的算法。即，如果一系列数据点都在一条直线上，则只需要起点和终点。

问压缩GPS点
EN

回答 5

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问压缩GPS点EN

回答 5

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问压缩GPS点
EN