nav2_costmap_2d::DistanceTransform Class Reference

Efficient Euclidean distance transform using the Felzenszwalb-Huttenlocher algorithm. More...

#include <nav2_costmap_2d/include/nav2_costmap_2d/distance_transform.hpp>

Static Public Member Functions
static void	distanceTransform1D (const float *f, float *d, int n, int *v, float *z)
	Perform 1D distance transform using lower envelope of parabolas. More...
static void	distanceTransform2D (MatrixXfRM &img, int height, int width)
	Perform 2D Euclidean distance transform using separable passes. More...

Static Public Attributes
static constexpr float	DT_INF = std::numeric_limits<float>::max()
	Infinity constant for distance transform.

Detailed Description

Efficient Euclidean distance transform using the Felzenszwalb-Huttenlocher algorithm.

This class provides a standalone implementation of the linear-time (O(n)) distance transform algorithm based on the lower envelope of parabolas method. It can be used for various applications including costmap inflation, obstacle detection, and path planning.

The algorithm computes exact squared Euclidean distances in two separable 1D passes (rows and columns), making it highly efficient for large images/grids.

Reference: Distance Transforms of Sampled Functions P. Felzenszwalb and D. Huttenlocher Theory of Computing, Vol. 8, No. 19, September 2012

Definition at line 47 of file distance_transform.hpp.

Member Function Documentation

distanceTransform1D()

static void nav2_costmap_2d::DistanceTransform::distanceTransform1D ( const float *  f, float *  d, int  n, int *  v, float *  z  )

inlinestatic

Perform 1D distance transform using lower envelope of parabolas.

This is the core Felzenszwalb-Huttenlocher algorithm for computing squared Euclidean distances in 1D. It uses a lower envelope of parabolas to achieve linear time complexity.

Parameters

f	Input array of squared distances (typically 0 for obstacles, INF for free space)
d	Output array for transformed squared distances (same size as f)
n	Length of the arrays
v	Buffer for parabola indices (size n)
z	Buffer for parabola boundaries (size n+1)

Definition at line 66 of file distance_transform.hpp.

References DT_INF.

Referenced by distanceTransform2D().

Here is the caller graph for this function:

distanceTransform2D()

static void nav2_costmap_2d::DistanceTransform::distanceTransform2D ( MatrixXfRM &  img, int  height, int  width  )

inlinestatic

Perform 2D Euclidean distance transform using separable passes.

This method applies the 1D distance transform separately along columns and rows, exploiting the separability property of the Euclidean metric. The result is an exact Euclidean distance map computed in O(width × height) time.

The algorithm is parallelized using OpenMP when available for improved performance on multi-core systems.

Parameters

img	Input/output matrix (modified in place). Input values should be 0 for obstacles and DT_INF for free space. Output will contain Euclidean distances.
height	Number of rows in the matrix
width	Number of columns in the matrix

Definition at line 120 of file distance_transform.hpp.

References distanceTransform1D().

Referenced by nav2_costmap_2d::InflationLayer::updateCosts().

Here is the call graph for this function:

Here is the caller graph for this function:

---

The documentation for this class was generated from the following file:

• nav2_costmap_2d/include/nav2_costmap_2d/distance_transform.hpp