routing.core.voxel_utils

Utility functions for voxel and multi-scale grid operations.

This module contains helper functions for: - Matrix decomposition and submatrix extraction - Multi-scale voxelization operations - Grid alignment and voxel manipulation

class routing.core.voxel_utils.VoxelizationCache

Bases: object

A class representing a cache for expensive voxelization operations.

This cache stores computed border voxels (both indices and centers) to avoid redundant calculations when the same voxelization is accessed multiple times.

Parameters:

_border_data – Internal dictionary mapping voxelization IDs to cached (border_indices, border_centers) tuples. Initialized as empty dict.

clear() → None

Clear all cached data.

get_border_centers(voxelization: MatrixBasedVoxelization) → ndarray

Get border voxel centers with caching.

Parameters:

voxelization – The voxelization to get border centers from

Returns:

Array of border voxel centers

get_border_indices(voxelization: MatrixBasedVoxelization) → ndarray

Get border voxel indices with caching.

Parameters:

voxelization – The voxelization to get border indices from

Returns:

Array of border voxel indices

get_border_voxels(voxelization: MatrixBasedVoxelization) → tuple[ndarray, ndarray]

Get border voxel indices and centers with caching.

This method computes both indices and centers together to avoid double computation of indices.

Parameters:

voxelization – The voxelization to get border voxels from

Returns:

Tuple of (border_indices, border_centers)

routing.core.voxel_utils.are_voxelizations_adjacent(voxelization_1: MatrixBasedVoxelization, voxelization_2: MatrixBasedVoxelization, cache: VoxelizationCache | None = None) → bool

Check if two voxelizations are adjacent using border voxels and spatial indexing.

This function uses border voxels only and KDTree with early exit for optimal performance.

Parameters:

• voxelization_1 – The first voxelization

• voxelization_2 – The second voxelization to check adjacency with

• cache – Optional cache for border voxel computation

Returns:

True if voxelizations are adjacent (distance < tolerance)

routing.core.voxel_utils.build_component_indices_from_voxelizations(voxelizations: list[MatrixBasedVoxelization], global_shape: tuple[int, int, int], global_min_grid_center: tuple[float, float, float], voxel_size: float) → ndarray

Build a component_indices matrix from a list of connected voxelizations.

Maps each voxel to its connected component index.

Parameters:

• voxelizations – List of connected MatrixBasedVoxelization objects

• global_shape – Shape of the global matrix

• global_min_grid_center – Min grid center of the global matrix

• voxel_size – Voxel size

Returns:

Integer array with component indices (-1 for empty voxels)

routing.core.voxel_utils.calculate_bounds_from_grid_spec(grid_origin: tuple[float, float, float], grid_shape: tuple[int, int, int], grid_voxel_size: float, world_origin: tuple[float, float, float], world_voxel_size: float) → dict[str, tuple[int, int]]

Calculate bounds in world coordinates from grid specifications.

Parameters:

• grid_origin – Origin of the grid in physical coordinates

• grid_shape – Shape of the grid (width, height, depth)

• grid_voxel_size – Voxel size of the local grid.

• world_origin – Origin of the world coordinate system

• world_voxel_size – Voxel size of the world.

Returns:

Bounds dictionary within world (in world voxel size) with ‘x’, ‘y’, ‘z’ keys

routing.core.voxel_utils.calculate_bounds_volume(bounds: dict[str, tuple[int, int]]) → int

Calculate the volume of a bounds dictionary.

routing.core.voxel_utils.compute_grid_alignment(fine_voxelization: MatrixBasedVoxelization, coarse_voxelization: MatrixBasedVoxelization) → tuple[int, ndarray]

Compute grid alignment parameters for multi-scale voxel operations.

Parameters:

• fine_voxelization – The fine resolution voxelization.

• coarse_voxelization – The coarse resolution voxelization.

Returns:

A tuple containing (ratio_int, fine_grid_start_offset).

Raises:

ValueError – If voxelizations are not properly aligned or ratio is not an integer.

routing.core.voxel_utils.compute_voxel_border_indices(voxelization: MatrixBasedVoxelization) → ndarray

Compute the voxel indices of the border voxels.

Parameters:

voxelization – The voxelization to compute border indices from

Returns:

Array of border voxel indices (N x 3)

routing.core.voxel_utils.compute_voxel_positions(indices: ndarray, voxelization: MatrixBasedVoxelization) → ndarray

Compute world positions from voxel indices.

Parameters:

• indices – Array of voxel indices (N x 3)

• voxelization – The voxelization containing grid parameters

Returns:

Array of world positions (N x 3)

routing.core.voxel_utils.expand_bounds_along_axis(matrix: ndarray, bounds: dict[str, tuple[int, int]], axis: int, fixed_slices: tuple[slice, slice]) → tuple[int, int]

Expand bounds along a specific axis while keeping other dimensions fixed.

routing.core.voxel_utils.extract_maximal_submatrices(matrix: ndarray, try_all_orders: bool = True, allow_overlap: bool = False) → list[dict[str, tuple[int, int]]]

Extract maximal submatrices of True values from a boolean matrix.

Parameters:

• matrix – Boolean 3D numpy array

• try_all_orders – If True, try all 6 expansion orders and pick best volume. If False, use first order only (faster)

• allow_overlap – If True, test expansion on original matrix (allows overlap). If False, test on visited matrix

Returns:

List of bounds dictionaries with ‘x’, ‘y’, ‘z’ keys

routing.core.voxel_utils.extract_sub_matrix(matrix: ndarray | None, sub_matrix_bounds: dict[str, tuple[int, int]]) → ndarray | None

Extract a sub-matrix from a 3D numpy array based on the provided bounds.

Parameters:

• matrix – The original 3D numpy array

• sub_matrix_bounds – Dictionary with ‘x’, ‘y’, ‘z’ keys containing (start, end) indices

routing.core.voxel_utils.extract_sub_matrix_based_voxelization(matrix_based_voxelization: MatrixBasedVoxelization, sub_matrix_bounds: dict[str, tuple[int, int]]) → MatrixBasedVoxelization

Extract a sub-voxelization from a MatrixBasedVoxelization based on bounds.

Parameters:

• matrix_based_voxelization – The original voxelization

• sub_matrix_bounds – Dictionary with ‘x’, ‘y’, ‘z’ keys containing (start, end) indices

Returns:

A new MatrixBasedVoxelization for the sub-region

routing.core.voxel_utils.fill_bounds_with_new_voxel_size(bounds: dict[str, tuple[int, int]], initial_voxelization: MatrixBasedVoxelization, factor: int) → MatrixBasedVoxelization

Fill bounds with a new voxel size scaled by factor.

Parameters:

• bounds – Bounds to fill in the initial voxelization coordinate system

• initial_voxelization – The initial voxelization

• factor – Scale factor for voxel size reduction

Returns:

A new voxelization with finer voxel size filling the bounds

routing.core.voxel_utils.filter_adjacent_components(components: list[MatrixBasedVoxelization], initial_voxelization: MatrixBasedVoxelization, cache: VoxelizationCache | None = None) → list[MatrixBasedVoxelization]

Filter components to keep only those adjacent to initial voxelization.

Parameters:

• components – List of voxelization components to filter

• initial_voxelization – Reference voxelization for adjacency check

• cache – Optional cache for border voxel computation

Returns:

Filtered list of adjacent components

routing.core.voxel_utils.filter_positions_by_proximity(positions_1: ndarray, positions_2: ndarray, distance_threshold: float) → tuple[ndarray, ndarray]

Filter positions using expanded bounding boxes to reduce search space.

Parameters:

• positions_1 – First array of positions (N x 3)

• positions_2 – Second array of positions (M x 3)

• distance_threshold – Distance threshold for proximity filtering

Returns:

Tuple of filtered position arrays

routing.core.voxel_utils.filter_voxelization_by_bbox(voxelization: MatrixBasedVoxelization, bounding_box: BoundingBox) → MatrixBasedVoxelization | None

Filter voxelization to keep only voxels within the bounding box.

Parameters:

• voxelization – Voxelization to filter

• bounding_box – Bounding box to filter by

Returns:

Filtered voxelization or None if empty

routing.core.voxel_utils.find_submatrix_from_point(matrix: ndarray, start_x: int, start_y: int, start_z: int, order: tuple[str, str, str]) → dict[str, tuple[int, int]]

Find the maximal submatrix starting from a given cell in a specific axis order.

routing.core.voxel_utils.mark_bounds_as_visited(matrix: ndarray, bounds: dict[str, tuple[int, int]]) → None

Mark the elements within the bounds as visited (False).

routing.core.voxel_utils.merge_voxelizations(voxelizations: list[MatrixBasedVoxelization]) → MatrixBasedVoxelization | None

Merge multiple voxelizations into a single one efficiently by combining all voxel indices at once.

Parameters:

voxelizations – List of voxelizations to merge

Returns:

Merged voxelization or None if input is empty

routing.core.voxel_utils.remove_voxels(fine_voxelization: MatrixBasedVoxelization, coarse_voxelization: MatrixBasedVoxelization) → MatrixBasedVoxelization

Remove voxels from fine voxelization that are covered by coarse voxelization.

This method performs a multi-scale boolean difference operation, where each True voxel in the coarse voxelization covers a block of voxels in the fine voxelization that should be removed.

Parameters:

• fine_voxelization – The fine resolution voxelization from which to remove voxels.

• coarse_voxelization – The coarse resolution voxelization that defines which regions to remove.

Returns:

The resulting fine voxelization after removal.

routing.core.voxel_utils.voxelize_region(region_bbox: BoundingBox, voxel_size: float, full_mesh: Mesh3D) → MatrixBasedVoxelization | None

Voxelize a region with the given voxel size, removing ruled volumes.

Parameters:

• region_bbox – Bounding box of the region to voxelize

• voxel_size – Voxel size for the voxelization

• full_mesh – Full mesh to crop and voxelize

Returns:

Voxelization of the region or None if empty