# Edge Case Handling for Horizontal and Vertical Line Simplification in pybind11-rdp

> Learn how pybind11-rdp simplifies horizontal and vertical lines by handling edge cases effectively. Get accurate results for colinear points.

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

---

**When simplifying perfectly horizontal, vertical, or colinear lines using pybind11-rdp, the algorithm correctly reduces the input to only the start and end points by detecting zero perpendicular distance across all intermediate points.**

The `cubao/pybind11-rdp` package provides high-performance Python bindings for the Ramer-Douglas-Peucker (RDP) line simplification algorithm. When processing **horizontal and vertical line simplification** edge cases—or any perfectly straight polyline—the implementation must reliably identify that no intermediate points contribute meaningful geometric detail.

## How the RDP Algorithm Handles Colinear Points

The core logic resides in [`src/main.cpp`](https://github.com/cubao/pybind11-rdp/blob/main/src/main.cpp), where the C++ implementation wraps the geometric primitives and recursion logic exposed to Python. For colinear inputs, three specific mechanisms ensure correct behavior.

### Distance Calculation in `LineSegment::distance2`

The perpendicular distance test occurs in `LineSegment::distance2` (lines 28–38). For a candidate segment defined by points **A** and **B**, the method computes the squared distance from any intermediate point **P**:

```cpp
double dot = (P - A).dot(AB);
if (dot <= 0) {
    return (P - A).squaredNorm();          // before A
} else if (dot >= len2) {
    return (P - B).squaredNorm();          // after B
}
return (A + (dot * inv_len2 * AB) - P).squaredNorm(); // on segment

```

For points lying exactly on the line segment, the final return value is `0`. When all intermediate points return `0`, the algorithm interprets this as zero deviation.

### Early Exit Logic in Recursive Simplification

The recursive simplifier `douglas_simplify` (lines 54–65) scans the interval `[i, j]` to find the point with maximum squared distance `max_dist2`. If this value is less than or equal to `epsilon * epsilon`, the function returns immediately:

```cpp
if (max_dist2 <= epsilon * epsilon) {
    return;                         // keep only endpoints i and j
}
douglas_simplify(coords, to_keep, i, max_index, epsilon);
douglas_simplify(coords, to_keep, max_index, j, epsilon);

```

With the default `epsilon = 0.0`, a perfectly straight line (where `max_dist2 == 0`) triggers this early exit, preserving only the first and last indices.

### Tie-Breaking for Degenerate Inputs

When multiple points share the same maximum distance—including the case where all distances are zero—the tie-breaking logic (lines 66–77) selects the point closest to the center of the interval:

```cpp
} else if (dist2 == max_dist2) {
    // prefer the point closest to the centre to limit recursion depth
    int pos_to_mid = std::fabs(k - mid);
    if (pos_to_mid < min_pos_to_mid) {
        min_pos_to_mid = pos_to_mid;
        max_index = k;
    }
}

```

This prevents pathological recursion depth on degenerate inputs while still ensuring only the endpoints survive the final mask.

## Practical Examples of Horizontal and Vertical Line Simplification

The Python bindings expose `rdp()` and `rdp_mask()` functions that demonstrate the edge-case behavior without requiring C++ interaction.

### Simplifying a Horizontal Line

A perfectly horizontal line with 100 points collapses to its endpoints:

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

# 100 points on y = 0

xs = np.linspace(0, 99, 100)
horizontal = np.column_stack((xs, np.zeros_like(xs)))

result = rdp(horizontal)  # epsilon defaults to 0.0

print(result)

# Output: [[ 0.  0.]

#          [99.  0.]]

```

### Simplifying a Vertical Line

The same logic applies to vertical orientations:

```python
pts = [[0, 0], [0, 1], [0, 2], [0, 3], [0, 4]]
print(rdp(pts))

# Output: [[0, 0], [0, 4]]

```

### Using Epsilon to Preserve Minor Deviations

If the line contains small perturbations, increasing `epsilon` treats them as noise:

```python
pts = [[0, 0], [1, 0.01], [2, -0.02], [3, 0], [4, 0]]

# With epsilon=0.05, the wiggle is ignored

print(rdp(pts, epsilon=0.05))

# Output: [[0, 0], [4, 0]]

```

## Recursive vs Iterative Modes for Large Colinear Inputs

For massive datasets, the default recursive implementation may hit Python's recursion limit. The package provides an iterative fallback controlled by the `recursive` parameter.

```python
from pybind11_rdp import rdp

# 10,000 colinear points

pts = [[i, 0] for i in range(10000)]

# Recursive mode (default) may raise RecursionError on huge N

# rdp(pts)  # Risky for very large inputs

# Iterative mode safely handles the edge case

result = rdp(pts, recursive=False)
print(result.shape)  # (2, 2) - only endpoints remain

```

The iterative implementation `douglas_simplify_iter` (lines 89–104 in [`src/main.cpp`](https://github.com/cubao/pybind11-rdp/blob/main/src/main.cpp)) uses a queue-based approach that performs the same `max_dist2 <= epsilon²` check without call-stack overhead.

## Key Source Files

| File | Role | Location |
|------|------|----------|
| [`src/main.cpp`](https://github.com/cubao/pybind11-rdp/blob/main/src/main.cpp) | Core C++ implementation containing `LineSegment::distance2`, recursive and iterative simplifiers, and pybind11 bindings. | <https://github.com/cubao/pybind11-rdp/blob/master/src/main.cpp> |
| [`src/pybind11_rdp/__init__.py`](https://github.com/cubao/pybind11-rdp/blob/main/src/pybind11_rdp/__init__.py) | Python package entry point exposing the compiled `_core` module. | <https://github.com/cubao/pybind11-rdp/blob/master/src/pybind11_rdp/__init__.py> |
| [`tests/test_basic.py`](https://github.com/cubao/pybind11-rdp/blob/main/tests/test_basic.py) | Unit tests verifying basic functionality including straight-line inputs. | <https://github.com/cubao/pybind11-rdp/blob/master/tests/test_basic.py> |
| [`tests/test_rdp.py`](https://github.com/cubao/pybind11-rdp/blob/main/tests/test_rdp.py) | Extended tests covering mask generation and algorithm variants. | <https://github.com/cubao/pybind11-rdp/blob/master/tests/test_rdp.py> |

## Summary

- **Zero-distance detection**: The `LineSegment::distance2` method in [`src/main.cpp`](https://github.com/cubao/pybind11-rdp/blob/main/src/main.cpp) returns `0` for points colinear with the candidate segment, signaling no simplification error.
- **Early termination**: Both recursive (`douglas_simplify`) and iterative (`douglas_simplify_iter`) implementations check `max_dist2 <= epsilon * epsilon` to return only endpoints for straight lines.
- **Default behavior**: With `epsilon=0.0`, horizontal, vertical, or any perfectly straight polylines automatically reduce to their first and last points.
- **Scalability**: Use `recursive=False` for massive colinear datasets to avoid Python recursion limits while maintaining identical geometric results.

## Frequently Asked Questions

### How does pybind11-rdp handle perfectly straight horizontal or vertical lines?

When all input points lie on a straight line, the `LineSegment::distance2` function calculates a perpendicular distance of exactly `0` for every intermediate point. Because the maximum squared distance (`max_dist2`) remains `0`, the algorithm compares it against `epsilon * epsilon` (default `0.0`) and immediately returns only the first and last points without further recursion.

### What is the default epsilon value and how does it affect colinear points?

The default `epsilon` parameter is `0.0` as defined in the Python bindings within [`src/main.cpp`](https://github.com/cubao/pybind11-rdp/blob/main/src/main.cpp). This strict tolerance means any non-zero deviation is considered significant. For perfectly colinear points, the deviation is exactly `0`, so the algorithm correctly identifies the line as already simplified and preserves only the endpoints.

### Can the algorithm hit recursion limits when simplifying long straight lines?

Yes, the default recursive implementation (`douglas_simplify`) processes segments via function calls that consume stack depth proportional to the number of splits. For extremely long colinear series (e.g., 10,000 points), Python may raise a `RecursionError`. To avoid this, pass `recursive=False` to use the iterative queue-based implementation (`douglas_simplify_iter`), which handles arbitrarily large inputs with constant memory overhead.

### Why does the code include tie-breaking logic for points with equal distance?

The tie-breaking logic in lines 66–77 of [`src/main.cpp`](https://github.com/cubao/pybind11-rdp/blob/main/src/main.cpp) resolves cases where multiple points share the same maximum distance to the candidate segment. When all distances are zero (colinear case), the algorithm selects the point closest to the center of the interval. This heuristic minimizes recursion depth by splitting the problem into balanced sub-segments rather than creating highly unbalanced splits that could degrade performance.