Douglas-Peucker-Algorithm

Question

I have a set of GPS-Position in my Database. Because i want to draw them on a map i stumbled over the "Douglas-Peucker-Algorithm" which will delete Points on a line which are not "necassary"...

But the everywhere i look for, i only discover the algorithm for pixel X/Y - Coordinates, and not for Latitude and Longitude...

Therefore i want to transform Lat / Long into a 2-Dimensional "X/Y" View ? Is that possible, or am i thinking "too complicated" ? :)

http://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm

Were you ever able to find a solution? – M. Smith Feb 19 '16 at 19:07 — M. Smith, Feb 19 '16 at 19:07

score 2 · Answer 1 · answered Jul 06 '11 at 19:45

If you can safely assume the GPS hasn't been moving thousands of kilometers, and you're not too close to the north/south pole, you can approximate X/Y coordinates in kilometres by multiplying latitude and longitude by a constant. Latitude is always the same amount of km per degree (about 10000 km is 90 degrees going from equator to one of the poles). For longitude, multiply by the same amount times cos(latitude).

It is not a lot harder however to compute 3D positions from longitude/latitude: See this wikipedia article on spherical coordinates how to do this. azimuth/elevation are longitude/latitude.

This is still an approximation as you take the straight line distance, rather than following the earth's surface, but for your application I can't imagine this is a problem.

Oh, and thanks for the link to the Douglas Peucker algo... I am going to try it out in a different problem domain.

score 1 · Answer 2 · answered Jul 06 '11 at 19:48

That depends on what you want a "straight line" to be. If you want a straight line on a map, then you must convert your lat/long coordinates using the correct projection (likely the Mercator projection, but there's a full list on Wikipedia). However, if you're looking for the straightest line on the surface (i.e. one that coincides with a great circle), you shouldn't have to apply any transformation to your lat/long values.

score 0 · Answer 3 · answered Jan 28 '14 at 08:29

0

Here is a great walkthrough in PHP: http://www.phpriot.com/articles/reducing-map-path-douglas-peucker-algorithm

answered Jan 28 '14 at 08:29

wivku

2,457
2
33
42

score 0 · Answer 4 · edited May 23 '17 at 10:32

0

I have asked this question some time ago, and the answer I got allowed me to write an implementation in java for this project. It's in EarthGeometry.java

edited May 23 '17 at 10:32

Community

1
1

answered Aug 19 '11 at 22:10

Maurice Perry

32,610
9
70
97

Douglas-Peucker-Algorithm

4 Answers4