pyorps.utils.traversal

PYORPS: An Open-Source Tool for Automated Power Line Routing

Reference: [1] Hofmann, M., Stetz, T., Kammer, F., Repo, S.: ‘PYORPS: An Open-Source Tool for

Automated Power Line Routing’, CIRED 2025 - 28th Conference and Exhibition on Electricity Distribution, 16 - 19 June 2025, Geneva, Switzerland

Functions

calculate_path_metrics_numba(raster, ...)

Calculate comprehensive metrics for a power line path.

calculate_region_bounds(dr, dc, rows, cols)

Calculate valid region bounds for source and target areas in graph construction.

calculate_segment_length(abs_dr, abs_dc)

Calculate the geometric length of a path segment between grid cells.

check_max_values(raster_data, indices_2d, ...)

Check which positions have the maximum value.

construct_edges(raster, steps[, ignore_max])

Construct graph edges from rasterized geodata using specified neighborhood steps.

euclidean_distances_numba(raster, target_point)

Calculate Euclidean distances from all points to a target point.

find_nearest_valid_positions_numba(...)

Find nearest valid positions for all invalid positions using Numba.

find_valid_nodes(dr, dc, s_rows_start, ...)

Find all valid node transitions for a given step direction within bounds.

get_cost_factor_numba(dr, dc, ...)

Calculate the cost factor for an edge based on its geometric length.

get_max_number_of_edges(n, m, steps)

Calculate the maximum number of edges for a given raster shape and neighborhood.

get_outgoing_edges(node_idx, raster, steps, ...)

Get outgoing edges from a specific node for dynamic graph traversal.

intermediate_steps_numba(dr, dc)

Calculate intermediate steps for line traversal using Bresenham-like algorithm.

is_valid_node(sr, sc, tr, tc, exclude_mask, ...)

Check if a node transition is valid and calculate its traversal cost.

ravel_index(row, col, cols)

Convert 2D grid coordinates to 1D linear index.
pyorps.utils.traversal.find_nearest_valid_positions_numba(raster_data, invalid_positions, max_value)[source]

Find nearest valid positions for all invalid positions using Numba.

Parameters:

  • raster_data (ndarray) – 2D array of raster values

  • invalid_positions (ndarray) – Array of shape (n, 2) with row, col indices

  • max_value (int) – The maximum value to avoid

Returns:

Array of corrected positions with shape (n, 2)

Return type:

ndarray

pyorps.utils.traversal.check_max_values(raster_data, indices_2d, max_value)[source]

Check which positions have the maximum value.

Returns:

Tuple of (has_max_values, invalid_mask, invalid_indices)

Parameters:
Return type:

tuple

pyorps.utils.traversal.intermediate_steps_numba(dr, dc)[source]

Calculate intermediate steps for line traversal using Bresenham-like algorithm.

This function determines all intermediate grid cells that a line segment passes through when moving from one grid cell to another. It’s essential for calculating edge weights in the graph representation of rasterized geodata.

Parameters:

  • dr (int) – Row difference (delta row) between source and target

  • dc (int) – Column difference (delta column) between source and target

Returns:

Array of intermediate step coordinates as (row, col) pairs

Return type:

np.ndarray

References

[1]

pyorps.utils.traversal.get_cost_factor_numba(dr, dc, intermediates_count)[source]

Calculate the cost factor for an edge based on its geometric length.

The cost factor normalizes edge weights by distributing the Euclidean distance over all cells involved in the traversal (source, target, and intermediates).

Parameters:

  • dr (int) – Row difference between source and target

  • dc (int) – Column difference between source and target

  • intermediates_count (int) – Number of intermediate cells traversed

Returns:

Cost factor for edge weight calculation

Return type:

float

References

[1]

pyorps.utils.traversal.ravel_index(row, col, cols)[source]

Convert 2D grid coordinates to 1D linear index.

This is a high-performance replacement for np.ravel_multi_index optimized for regular grid indexing operations in graph construction.

Parameters:

  • row (int) – Row coordinate in the grid

  • col (int) – Column coordinate in the grid

  • cols (int) – Total number of columns in the grid

Returns:

Linear index corresponding to the 2D coordinates

Return type:

int

pyorps.utils.traversal.calculate_region_bounds(dr, dc, rows, cols)[source]

Calculate valid region bounds for source and target areas in graph construction.

This function determines the valid coordinate ranges for source and target nodes when creating edges with the given step direction, ensuring all coordinates remain within grid boundaries.

Parameters:

  • dr (int) – Row step direction

  • dc (int) – Column step direction

  • rows (int) – Total number of rows in the grid

  • cols (int) – Total number of columns in the grid

Returns:

Array containing bounds for source and target regions

Return type:

np.ndarray

References

[1]

pyorps.utils.traversal.is_valid_node(sr, sc, tr, tc, exclude_mask, intermediates, raster, rows, cols, out_cost)[source]

Check if a node transition is valid and calculate its traversal cost.

This function validates that a path from source to target coordinates is feasible by checking boundary conditions, exclusion masks, and intermediate cell validity. It also calculates the total cost for traversing this path.

Parameters:

  • sr (int) – Source row coordinate

  • sc (int) – Source column coordinate

  • tr (int) – Target row coordinate

  • tc (int) – Target column coordinate

  • exclude_mask (np.ndarray) – Binary mask indicating forbidden areas

  • intermediates (np.ndarray) – Array of intermediate step coordinates

  • raster (np.ndarray) – Cost raster with terrain/construction costs

  • rows (int) – Total number of rows in the grid

  • cols (int) – Total number of columns in the grid

  • out_cost (np.ndarray) – Output array to store calculated cost

Returns:

True if the node transition is valid, False otherwise

Return type:

bool

References

[1]

pyorps.utils.traversal.find_valid_nodes(dr, dc, s_rows_start, s_rows_end, s_cols_start, s_cols_end, exclude_mask, raster, intermediates, rows, cols, cost_factor, max_nodes)[source]

Find all valid node transitions for a given step direction within bounds.

This function systematically searches through a defined region to identify all valid edges (node transitions) for a specific step direction, calculating their costs and storing them for graph construction.

Parameters:

  • dr (int) – Row step direction

  • dc (int) – Column step direction

  • s_rows_start (int) – Starting row for source region search

  • s_rows_end (int) – Ending row for source region search

  • s_cols_start (int) – Starting column for source region search

  • s_cols_end (int) – Ending column for source region search

  • exclude_mask (np.ndarray) – Binary mask indicating forbidden areas

  • raster (np.ndarray) – Cost raster with terrain/construction costs

  • intermediates (np.ndarray) – Array of intermediate step coordinates

  • rows (int) – Total number of rows in the grid

  • cols (int) – Total number of columns in the grid

  • cost_factor (float) – Cost normalization factor for this step direction

  • max_nodes (int) – Maximum number of valid nodes to find

Returns:

Edge data and count

Return type:

Tuple[np.ndarray, np.ndarray, np.ndarray, int]

References

[1]

pyorps.utils.traversal.get_max_number_of_edges(n, m, steps)[source]

Calculate the maximum number of edges for a given raster shape and neighborhood.

This function estimates the upper bound on the number of edges that will be created when converting a raster into a graph using the specified neighborhood steps. This is used for memory pre-allocation optimization.

Parameters:

  • n (int) – Number of rows in the raster

  • m (int) – Number of columns in the raster

  • steps (np.ndarray) – Array of neighborhood step directions

Returns:

Maximum possible number of edges

Return type:

int

References

[1]

pyorps.utils.traversal.construct_edges(raster, steps, ignore_max=True)[source]

Construct graph edges from rasterized geodata using specified neighborhood steps.

This is the main function for converting rasterized cost data into a weighted graph representation suitable for least-cost path analysis. It processes each step direction in the neighborhood to create edges between valid grid cells.

Parameters:

  • raster (np.ndarray) – 2D cost raster representing terrain/construction costs

  • steps (np.ndarray) – Array of neighborhood step directions (Rk neighborhood)

  • ignore_max (bool) – If True, treats maximum cost values as forbidden areas

Returns:

Complete edge list for graph

Return type:

Tuple[np.ndarray, np.ndarray, np.ndarray]

References

[1]

pyorps.utils.traversal.calculate_segment_length(abs_dr, abs_dc)[source]

Calculate the geometric length of a path segment between grid cells.

This function provides optimized calculations for common step patterns and falls back to the Pythagorean theorem for arbitrary steps.

Parameters:

  • abs_dr (int) – Absolute row difference

  • abs_dc (int) – Absolute column difference

Returns:

Euclidean length of the segment

Return type:

float

pyorps.utils.traversal.calculate_path_metrics_numba(raster, path_indices)[source]

Calculate comprehensive metrics for a power line path.

This function analyzes an optimal path found by the routing algorithm to provide detailed statistics about path length, terrain traversed, and cost distribution. This information is essential for power line planning and cost estimation.

Parameters:

  • raster (np.ndarray) – 2D cost raster representing terrain/construction costs

  • path_indices (np.ndarray) – Array of linear indices representing the path

Returns:

Total length, categories, lengths

Return type:

Tuple[float, np.ndarray, np.ndarray]

References

[1]

pyorps.utils.traversal.euclidean_distances_numba(raster, target_point)[source]

Calculate Euclidean distances from all points to a target point.

This function is optimized for spatial analysis and can be used for various distance-based calculations in power line routing applications.

Parameters:

  • raster (np.ndarray) – Array of coordinate points

  • target_point (np.ndarray) – Target point coordinates

Returns:

Array of distances from each point to the target

Return type:

np.ndarray

pyorps.utils.traversal.get_outgoing_edges(node_idx, raster, steps, rows, cols, exclude_mask=None)[source]

Get outgoing edges from a specific node for dynamic graph traversal.

This function calculates outgoing edges on-demand rather than pre-computing the entire graph, which can be memory-efficient for large rasters or specialized pathfinding algorithms.

Parameters:

  • node_idx (int) – Linear index of the source node

  • raster (np.ndarray) – 2D cost raster

  • steps (np.ndarray) – Array of neighborhood step directions

  • rows (int) – Number of rows in the raster

  • cols (int) – Number of columns in the raster

  • exclude_mask (Union[np.ndarray, None]) – Optional exclusion mask

Returns:

Target nodes and edge costs

Return type:

Tuple[np.ndarray, np.ndarray]

References

[1]