Ramer–Douglas–Peucker (RDP) algorithm

The Ramer–Douglas–Peucker (RDP) algorithm (also called Douglas–Peucker) is a classic path / polyline simplification algorithm. It reduces the number of points in a curve while preserving its overall shape within a specified error tolerance.

It is widely used in:

• GIS & map rendering (road simplification)
• Computer graphics
• Gesture recognition
• Physics/path optimization in games (including 2D engines)
• Data compression for trajectories

1. Problem It Solves

Given:

• A polyline defined by ordered points [ P = {p_1, p_2, …, p_n} ]
• A tolerance ( \varepsilon )

Goal:

Remove “unnecessary” intermediate points while ensuring the simplified path never deviates more than ( \varepsilon ) from the original.

2. Core Idea (Intuition)

Imagine stretching a rubber band from the first point to the last point:

• If all intermediate points lie close to the band → keep only endpoints
• If any point deviates too far → keep the most deviant point and recurse

The algorithm keeps points only when they are needed to preserve shape.

3. Distance Metric

For each intermediate point ( p_i ), compute its perpendicular distance to the line segment ( \overline{p_1 p_n} ).

Perpendicular distance formula (2D)

For point ( P ) and line ( AB ):

[ d = \frac{|(B-A) \times (A-P)|}{|B-A|} ]

Expanded:

[ d = \frac{|(x_2-x_1)(y_1-y_0) - (x_1-x_0)(y_2-y_1)|}{\sqrt{(x_2-x_1)^2 + (y_2-y_1)^2}} ]

4. Algorithm Steps (Recursive)

Input

• List of points: points
• Tolerance: ε

Step-by-step

1. Start with first and last point

   • Keep points[0] and points[n-1]

2. Find max deviation

   • For each intermediate point:

     • Compute distance to line segment (start → end)

   • Find the point with maximum distance d_max

3. Decision

   • If d_max > ε:

     • Keep that point

     • Recursively apply RDP to:

     • Left segment

     • Right segment

   • Else:

     • Remove all intermediate points

4. Combine results

   • Merge results from recursive calls

5. Visual Example

Original path:

A ---- x ---- y ---- z ---- B

If:

• x, y, z are close to line AB → simplify to A ---- B
• y deviates too much → split: A ---- y ---- B

Then recurse on A → y and y → B.

6. Pseudocode

RDP(points, ε):
    if points.length < 3:
        return points

    start = points[0]
    end = points[last]

    maxDist = 0
    index = 0

    for i in 1 to n-2:
        d = perpendicularDistance(points[i], start, end)
        if d > maxDist:
            maxDist = d
            index = i

    if maxDist > ε:
        left = RDP(points[0..index], ε)
        right = RDP(points[index..end], ε)
        return left + right[1:]
    else:
        return [start, end]

7. Iterative (Stack-Based) Version

Used to avoid deep recursion:

stack.push((0, n-1))
keep[0] = keep[n-1] = true

while stack not empty:
    (start, end) = stack.pop()

    maxDist = 0
    index = -1

    for i in start+1 to end-1:
        d = distance(points[i], points[start], points[end])
        if d > maxDist:
            maxDist = d
            index = i

    if maxDist > ε:
        keep[index] = true
        stack.push((start, index))
        stack.push((index, end))

8. Time & Space Complexity

Worst case

• Time: ( O(n^2) )
• Space: ( O(n) ) (recursion stack)

Typical case

• Close to O(n log n) for smooth curves

9. Choosing ε (Tolerance)

Rule of thumb:

• Screen-space simplification → pixels
• World-space → meters / units
• Games → collision precision vs performance tradeoff

10. Strengths & Weaknesses

✅ Strengths

• Simple
• Shape-preserving
• Deterministic
• Works well for polylines

❌ Weaknesses

• Not topology-aware
• Can remove important points if ε is too large
• Worst-case quadratic
• Sensitive to noisy data

11. Common Variations

• Modified RDP (segment distance instead of infinite line)
• Weighted RDP
• Visvalingam–Whyatt (area-based alternative)
• Multi-scale RDP (LOD systems)

12. Practical Uses (Including Games)

• Simplify touch gestures
• Optimize collision paths
• Reduce draw calls
• Path smoothing before AI navigation
• Level geometry simplification

13. Key Takeaway

RDP keeps only the points that matter.

By recursively removing points that do not significantly alter shape, it achieves high compression with controlled error, making it one of the most important algorithms in geometric processing.

If you want:

• A step-by-step numeric example
• Code in Dart / Flutter / Flame
• Comparison with Visvalingam–Whyatt
• Optimization tricks for real-time games

Just tell me 👍