Distance Transform for Path Planning

MediumPython

Problem

Bear Robotics' Servi navigation stack can use a distance transform to prefer paths that maintain clearance from obstacles. Given a binary occupancy grid, compute the distance from every free cell to its nearest obstacle using four-directional movement.

A cell containing 1 is an obstacle and has distance 0. A cell containing 0 is free, and its distance is the minimum number of up, down, left, or right moves needed to reach any obstacle. Return a new grid of integer distances without modifying the input.

Formal Specification

Implement distance_transform(grid).

Input: grid, a non-empty rectangular list of lists containing only 0 and 1.
Output: A rectangular list of lists where each position contains its distance to the nearest obstacle.
The input contains at least one obstacle.
Diagonal movement does not count toward distance.

Constraints

1 <= rows, cols <= 500
grid is rectangular
grid[r][c] is either 0 or 1
At least one cell contains 1

Function Signature

def distance_transform(grid):

Formal Specification

Implement distance_transform(grid).

Input: grid, a non-empty rectangular list of lists containing only 0 and 1.
Output: A rectangular list of lists where each position contains its distance to the nearest obstacle.
The input contains at least one obstacle.
Diagonal movement does not count toward distance.