# Edge Case: L-Shaped Path Handling in RDP (Ramer-Douglas-Peucker)

> Discover how pybind11-rdp handles L-shaped paths by retaining corners and discarding collinear points using a middle-pivot strategy.

- Repository: [cubao/pybind11-rdp](https://github.com/cubao/pybind11-rdp)
- Tags: deep-dive
- Published: 2026-02-28

---

**The pybind11-rdp library uses a middle-pivot preference strategy in its C++ core to guarantee that corner points in L-shaped polylines are always retained while collinear intermediate points are discarded during simplification.**

The **cubao/pybind11-rdp** package implements the classic Ramer-Douglas-Peucker algorithm with high-performance C++ bindings exposed to Python via pybind11. When processing point sequences that form an "L" shape—two orthogonal line segments meeting at a corner—the algorithm must correctly identify and preserve that critical corner point while removing redundant collinear points from each leg.

## How L-Shaped Paths Challenge Standard RDP

Standard RDP implementations recursively split line segments at the point with the maximum perpendicular distance. In a perfectly orthogonal L-shape, the corner point and many intermediate points can exhibit similar distance characteristics, creating a degenerate case where the algorithm might select a suboptimal pivot. If the wrong pivot is chosen, the algorithm could fail to preserve the true geometric corner or create unnecessary recursion depth.

The library addresses this specifically in [`src/main.cpp`](https://github.com/cubao/pybind11-rdp/blob/main/src/main.cpp) through a targeted safeguard that ensures robust handling of these geometric edge cases.

## The Middle-Pivot Safeguard in [`src/main.cpp`](https://github.com/cubao/pybind11-rdp/blob/main/src/main.cpp)

The core simplification logic resides in [`src/main.cpp`](https://github.com/cubao/pybind11-rdp/blob/main/src/main.cpp), where both recursive (`douglas_simplify`) and iterative (`douglas_simplify_iter`) variants share the same robust distance-checking logic.

### Maximum-Distance Detection with Tie-Breaking

When processing a segment `[i, j]`, the algorithm creates a `LineSegment` between endpoints and scans all intermediate points `k` (`i < k < j`) to find the maximum perpendicular distance (`max_dist2`). 

When multiple points share the same maximal distance—as occurs in orthogonal L-shapes where the corner and adjacent points project similarly—the code implements a specific tie-breaking rule at lines 68-76:

```cpp
// workaround to ensure we choose a pivot close to the middle of the list,
// reducing recursion depth, for certain degenerate inputs...

```

This logic prefers the point **closest to the middle of the interval** when distances are equal. By selecting a central pivot rather than the first or last maximal-distance point, the algorithm reduces recursion depth and guarantees that the true corner point serves as the split point for subsequent simplification passes.

### Recursion and Sub-Segment Processing

Once the pivot (`max_index`) is identified, the algorithm processes two sub-segments: `[i, max_index]` and `[max_index, j]`. Because the corner point possesses the largest perpendicular distance to the hypotenuse connecting the L-shape's endpoints, it is always retained as a critical point. Collinear points on each leg—having zero or minimal distance to their respective sub-segment lines—are subsequently discarded when their distance falls below the epsilon threshold.

## Python API and Usage Examples

The Python wrapper in [`src/pybind11_rdp/__init__.py`](https://github.com/cubao/pybind11-rdp/blob/main/src/pybind11_rdp/__init__.py) exposes a convenient interface that forwards requests to the compiled core while preserving this edge-case handling:

```python
def rdp(points, epsilon: float = 0.0, algo="iter", return_mask=False):
    """Main interface for the Ramer-Douglas-Peucker algorithm."""
    recursive = "iter" != algo
    if return_mask:
        return rdp_mask(points, epsilon=epsilon, recursive=recursive)
    return _rdp(points, epsilon=epsilon, recursive=recursive)

```

By default, `algo="iter"` uses the iterative implementation, but both recursive and iterative pathways inherit the same corner-preserving logic from the underlying C++ implementation.

### Example 1: Simplify an L-Shaped Polyline

```python
import numpy as np
from pybind11_rdp import rdp

# L-shaped polyline: horizontal leg → vertical leg

points = np.array([
    [5, 0],
    [4, 0],
    [3, 0],
    [3, 1],
    [3, 2],
])

simplified = rdp(points)          # epsilon defaults to 0.0

print(simplified)

# [[5. 0.]

#  [3. 0.]

#  [3. 2.]]

```

### Example 2: Collapse with Larger Epsilon

```python
simplified_eps = rdp(points, epsilon=1.5)
print(simplified_eps)

# [[5. 0.]

#  [3. 2.]]

```

### Example 3: Boolean Mask Output

```python
mask = rdp(points, return_mask=True)
print(mask)          # [1, 0, 1, 0, 1] – keep first, corner, last

```

### Example 4: Recursive Algorithm Verification

```python
simplified_rec = rdp(points, algo="rec")
print(np.allclose(simplified, simplified_rec))  # True

```

## Verifying Correctness with Unit Tests

The repository includes explicit validation for L-shaped path handling in [`tests/test_rdp.py`](https://github.com/cubao/pybind11-rdp/blob/main/tests/test_rdp.py). The `test_L0` function confirms that the algorithm correctly retains the corner point `(3, 0)` while removing intermediate collinear points:

```python
def test_L0():
    """Point sequence which has the form of an L."""
    assertAE(
        rdp(np.array([5, 0, 4, 0, 3, 0, 3, 1, 3, 2]).reshape(5, 2)),
        np.array([5, 0, 3, 0, 3, 2]).reshape(3, 2),
    )

```

This test validates that the output `[[5, 0], [3, 0], [3, 2]]` preserves the geometric integrity of the original L-shape, confirming that the middle-pivot safeguard functions correctly across both algorithm variants.

## Summary

- **Degenerate case handling**: The C++ implementation in [`src/main.cpp`](https://github.com/cubao/pybind11-rdp/blob/main/src/main.cpp) (lines 68-76) specifically addresses L-shaped paths by preferring middle-interval pivots when multiple points share the same maximal distance.
- **Corner preservation**: The algorithm guarantees retention of orthogonal corner points while discarding collinear intermediate points based on the epsilon threshold.
- **Implementation parity**: Both `douglas_simplify` (recursive) and `douglas_simplify_iter` (iterative) use identical pivot-selection logic, ensuring consistent behavior regardless of the `algo` parameter.
- **Python accessibility**: The `rdp()` function in [`src/pybind11_rdp/__init__.py`](https://github.com/cubao/pybind11-rdp/blob/main/src/pybind11_rdp/__init__.py) exposes these robust simplification routines with optional mask generation and algorithm selection.

## Frequently Asked Questions

### Why does RDP need special handling for L-shaped paths?

L-shaped paths create a degenerate case where the corner point and adjacent points may exhibit identical perpendicular distances to the line connecting the endpoints. Without the middle-pivot preference implemented in [`src/main.cpp`](https://github.com/cubao/pybind11-rdp/blob/main/src/main.cpp), the algorithm might select a suboptimal pivot point, potentially dropping the true corner or creating excessive recursion depth by selecting endpoints of collinear runs.

### How does the middle-pivot safeguard affect performance?

Preferring middle-interval pivots reduces recursion depth for degenerate inputs like L-shapes or grids. By splitting segments closer to their geometric centers rather than at extremities, the algorithm processes fewer recursive levels while maintaining $O(n \log n)$ average-case complexity for well-behaved inputs.

### Can I use the recursive algorithm instead of the default iterative one?

Yes. Pass `algo="rec"` to the `rdp()` function to use the recursive implementation. Both variants in [`src/main.cpp`](https://github.com/cubao/pybind11-rdp/blob/main/src/main.cpp) share the same `LineSegment` distance calculations and middle-pivot logic, producing identical geometric results. The iterative default (`algo="iter"`) is recommended for very large inputs to avoid potential stack overflow.

### Does this handle N-dimensional L-shapes or only 2D?

The pybind11-rdp implementation supports arbitrary dimensions. The perpendicular distance calculations in `douglas_simplify` work in N-dimensional space, meaning L-shaped paths (or hyper-corner geometries) in 3D or higher dimensions receive the same middle-pivot protection and corner-point preservation as 2D polylines.