Help with understanding this algorithm

Question

I would like to implement the Ramer–Douglas–Peucker_algorithm in C++.

The pseudo code looks like this:

function DouglasPeucker(PointList[], epsilon)
 //Find the point with the maximum distance
 dmax = 0
 index = 0
 for i = 2 to (length(PointList) - 1)
  d = OrthogonalDistance(PointList[i], Line(PointList[1], PointList[end])) 
  if d > dmax
   index = i
   dmax = d
  end
 end

 //If max distance is greater than epsilon, recursively simplify
 if dmax >= epsilon
  //Recursive call
  recResults1[] = DouglasPeucker(PointList[1...index], epsilon)
  recResults2[] = DouglasPeucker(PointList[index...end], epsilon)

  // Build the result list
  ResultList[] = {recResults1[1...end-1] recResults2[1...end]}
 else
  ResultList[] = {PointList[1], PointList[end]}
 end

 //Return the result
 return ResultList[]
end

Here is my understanding so far. It is a recursive function taking in an array of points and a distance threshold.

Then it iterates through the current points to find the point with the maximum distance.

I got a bit lost with the Orthographical Distance function. How do I compute this? I've never seen a distance function take a line segment as a parameter.

I think aside from this I should be alright, I will just use std::vectors for the arrays. I think I will use std::copy and then push or pop according to what the algorithm says.

Thanks

Answer 1

The orthogonal distance from a point P to a line L is defined by the distance between point P and point P2, where P2 is the orthogonal projection of P on line L.

How you compute this value depends on the dimension of the space you work on, but if it's 2D, you should be able to figure that out by drawing an example on a piece of paper !

Answer 2

Look at the topcoder tutorial and the

double linePointDist(point A, point B, point C, bool isSegment);

method it it what your looking for.

Answer 3

The OrthogonalDistance is shown in this picture:

So it's the distance from your point and the point on the line which is the projection of that point on the line.

The distance from a point to a line is usally something like this:

where x0 and y0 are the coordinates of the external point and a, b, c are the coefficient of the equation of your line.

That's what I remember from school, long time ago.

Answer 4

A brief description of the math required can be found here. Just realize that you can swap the word "Orthogonal" for "Perpendicular" when dealing with 2D. The site linked has instructions for lines defined by two points as well as lines defined by slope-intercept form.

The short version is reproduced here: If the line is represented in slope intercept from: ax + by + c = 0, and the point is represented by x0, y0, then the function that will give the Orthogonal distance is:

abs(a*x0 + b*y0 + c)/sqrt(a*a + b*b) 

Answer 5

It's not clear to me whether you want the distance of the point to the (infinite) line through the two points, or the distance to the line segment defined by the points, but I suspect its the latter.

Consider the somewhat contrived example of the points (0,0) (1,0) and (10, t) where t is small. The distance of (10,t) from the line through the first two points (ie the x axis) is t, while the distance (10,t) from the line segment with end points (0,0) and (1,0) is hypot(9,t) ~ 9. So if you were using distance to the line, there is a danger that the algorithm above would not split at (10,t).

The method mentioned by jethro above handles both lines and line segments.