A recursive algorithm that simplifies a polyline by removing points that lie within a tolerance distance of the line connecting their neighbours.
Given a polyline of N points and a tolerance ε (epsilon), RDP finds the minimum subset of points that approximates the original path within ε pixels everywhere.
The algorithm is divide-and-conquer. Draw a straight line from the first point to the last. Find the point with the greatest perpendicular distance from that line. If it's less than ε, the whole interior can be discarded — the straight line is a good-enough approximation. If it exceeds ε, that point must be kept and the segment is split there, recursing on both halves.
Perpendicular distance from point P to the line through A and B is computed as the area of the triangle ABP divided by the base length |AB|.
Drag the epsilon slider to see simplification in real time. Gray dots are the original 60 sampled points; blue dots are the kept points; the white line is the simplified path.
Each step is one recursive call. The amber segment is the current start→end line being tested. The thin perpendicular lines show the distance from each interior point to that line. The red point has the maximum distance — it determines whether this segment splits or collapses. Epsilon is fixed at ε = 12.