Handling 3D Coordinate Arrays (Nx3 vs Nx2) in pybind11-rdp

The pybind11-rdp library automatically handles both Nx3 and Nx2 coordinate arrays by internally padding 2D inputs with a zero z-coordinate, processing them as 3D data, and stripping the extra dimension from the output to preserve the original input shape.

The cubao/pybind11-rdp repository provides Python bindings for the Ramer-Douglas-Peucker (RDP) algorithm, enabling efficient polyline simplification on NumPy arrays. A key architectural feature of this library is its seamless support for both two-dimensional (Nx2) and three-dimensional (Nx3) coordinate arrays without requiring users to manually reshape their data.

How pybind11-rdp Handles Nx3 and Nx2 Arrays

The library’s C++ core operates exclusively on three-dimensional data using Eigen matrices. When you pass a two-dimensional array, the binding layer performs a transparent conversion that adds a zero-filled z-axis, executes the RDP algorithm, and removes the temporary dimension before returning results.

Core Type Definitions

In src/main.cpp, the library defines distinct Eigen types for 2D and 3D data:

// 3D matrix type (Nx3)
using RowVectors = Eigen::Matrix<double, Eigen::Dynamic, 3, Eigen::RowMajor>;

// 2D matrix type (Nx2)  
using RowVectorsNx2 = Eigen::Matrix<double, Eigen::Dynamic, 2, Eigen::RowMajor>;

These definitions appear at lines 46 and 48 of src/main.cpp, establishing the memory layout expectations for incoming NumPy arrays.

The Nx2-to-Nx3 Conversion Pipeline

When you invoke rdp() with an Nx2 array, the binding executes a four-step conversion process defined in src/main.cpp at lines 24-31:

1. Allocate a temporary Nx3 matrix initialized with zeros
2. Copy the two input columns into the leftmost positions of the 3D matrix
3. Process the data through the standard douglas_simplify algorithm
4. Return only the first two columns, discarding the zero z-coordinate

This approach ensures that the Euclidean distance calculations in the RDP algorithm remain consistent while avoiding code duplication for 2D and 3D variants.

Implementation Details

Direct Nx3 Processing

For three-dimensional inputs, the library provides a direct passthrough overload at src/main.cpp lines 16-22. This path forwards the Eigen matrix immediately to the core douglas_simplify function without any dimensionality conversion, offering maximum performance for 3D point clouds.

Automatic Padding for Nx2 Inputs

The Nx2 overload (lines 24-31) handles the transparent conversion described earlier. The implementation uses Eigen’s block operations to efficiently copy data between the 2D input and 3D working buffer:

// Simplified representation of the conversion logic
RowVectors tmp = RowVectors::Zero(coords.rows(), 3);
tmp.leftCols<2>() = coords;  // coords is Nx2
auto result = douglas_simplify(tmp, epsilon);
return result.leftCols<2>();

This conversion incurs minimal overhead—typically a single memory allocation and memcpy operation—making it suitable for real-time polyline simplification tasks.

Mask Generation with rdp_mask

The library applies the same dimensionality handling to the rdp_mask function (lines 48-55 of src/main.cpp). This variant returns an Eigen::VectorXi mask indicating which points are retained after simplification. Whether you pass Nx2 or Nx3 data, the mask length always matches the input row count, allowing you to filter auxiliary data arrays consistently.

Python API and Type Hints

The Python interface exposes these C++ overloads through pybind11 with complete type annotations in src/pybind11_rdp/__init__.pyi (lines 62-98). The stub file defines separate signatures for 2D and 3D inputs, enabling IDE autocompletion and static type checking:

@overload
def rdp(coords: NDArray[np.float64], epsilon: float = ...) -> NDArray[np.float64]: ...
@overload
def rdp(coords: LineSegment, epsilon: float = ...) -> LineSegment: ...

This design ensures that Python developers receive the correct return type dimensions—Nx2 input yields Nx2 output, Nx3 yields Nx3—without manual reshaping.

Practical Examples

The following examples demonstrate handling both 2D and 3D coordinate arrays with the rdp and rdp_mask functions, plus the LineSegment utility class:

import numpy as np
from pybind11_rdp import rdp, rdp_mask, LineSegment

# 1️⃣ Nx3 input (x, y, z)

coords_3d = np.array([[0, 0, 0],
                      [1, 1, 0],
                      [2, 2, 0],
                      [3, 3, 0],
                      [4, 4, 0]], dtype=np.float64)

simplified_3d = rdp(coords_3d, epsilon=0.5)
print("Nx3 result shape:", simplified_3d.shape)   # (2, 3)

# 2️⃣ Nx2 input (x, y) – the library adds a zero z internally

coords_2d = np.array([[0, 0],
                      [1, 1],
                      [2, 2],
                      [3, 3],
                      [4, 4]], dtype=np.float64)

simplified_2d = rdp(coords_2d, epsilon=0.5)
print("Nx2 result shape:", simplified_2d.shape)   # (2, 2)

# Mask version works the same way

mask_2d = rdp_mask(coords_2d, epsilon=0.5)
print("Mask:", mask_2d)                          # [1 0 0 0 1]

# Using the LineSegment class (always 3‑D)

seg = LineSegment([0, 0, 0], [10, 0, 0])
print("Distance to point (5, 4, 0):", seg.distance([5, 4, 0]))

Notice that the Nx2 input returns an Nx2 array automatically—the zero z-coordinate never appears in the Python output.

Summary

• pybind11-rdp simplifies polylines for both 2D (Nx2) and 3D (Nx3) NumPy arrays using a unified C++ backend.
• The core algorithm operates exclusively on 3D data defined as RowVectors in src/main.cpp, ensuring consistent Euclidean distance calculations.
• When receiving Nx2 inputs, the binding layer automatically pads the array with a zero z-coordinate, processes it, and strips the extra dimension before returning results.
• This design avoids code duplication while maintaining type safety through pybind11 overloads and Python type stubs in src/pybind11_rdp/__init__.pyi.

Frequently Asked Questions

Does pybind11-rdp support 2D coordinates?

Yes, the library fully supports two-dimensional coordinate arrays. When you pass an Nx2 NumPy array, the binding layer transparently converts it to Nx3 by adding a zero-filled z-coordinate column, processes the data using the standard 3D RDP algorithm, and returns the result with the original Nx2 shape.

How does the library convert Nx2 arrays to Nx3 internally?

The conversion occurs in src/main.cpp at lines 24-31. The implementation allocates a temporary Nx3 Eigen matrix initialized with zeros, copies the two input columns into the leftmost positions using block operations, executes the douglas_simplify function on the 3D data, and finally returns only the first two columns of the result.

Is there a performance penalty when using 2D coordinates?

The overhead is negligible for most applications. The conversion requires only a single memory allocation for the temporary Nx3 buffer and a memcpy operation to copy the 2D data into the 3D structure. Since the core RDP algorithm runs in O(n log n) time, the linear-time conversion step does not significantly impact overall performance.

Can I use rdp_mask with 3D point clouds?

Yes, the rdp_mask function works with both Nx3 and Nx2 inputs. Located at lines 48-55 of src/main.cpp, this function applies the same dimensionality handling as the standard rdp function but returns an integer mask vector indicating which points are retained after simplification. The mask length always matches the input row count regardless of whether you use 2D or 3D coordinates.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}