Douglas-Peucker-Algorithm

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 whi开发者_运维技巧ch 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

---

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.

---

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.

---

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

---

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