# 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

```text
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:

```text
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)

| ε value | Result                               |
| ------- | ------------------------------------ |
| Small   | High fidelity, little simplification |
| Medium  | Balanced                             |
| Large   | Aggressive simplification            |

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 👍