CODEWITHSUNDEEP
gps
LatinChriz
LatinChriz

Reputation: 81

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 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

Upvotes: 7

Views: 3479

Answers (4)

wivku
wivku

Reputation: 2653

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

Upvotes: 0

Maurice Perry
Maurice Perry

Reputation: 32831

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

Upvotes: 0

You
You

Reputation: 23774

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.

Upvotes: 1

user180326
user180326

Reputation:

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.

Upvotes: 2

Related Questions