path

4.3. path#

Path optimization utilities for LMD cutting path generation.

This module provides algorithms for solving the Traveling Salesman Problem (TSP) to optimize the order of cutting shapes, minimizing total travel distance for laser microdissection operations.

lmd.path.assign_vertices(hilbert_points: ndarray, data_rounded: ndarray) → ndarray#

Order data points according to their position along a Hilbert curve.

For each point on the Hilbert curve, the matching data point is located and its index appended to the output, yielding an ordering of the data points that follows the curve.

Parameters:

  • hilbert_points – Array of shape (M, 2) with the integer coordinates of the Hilbert curve points, in curve order.

  • data_rounded – Array of shape (N, 2) with the data coordinates rounded to the Hilbert curve grid.

Returns:

Array of shape (N,) with the indices of data_rounded ordered along the Hilbert curve.

lmd.path.calc_len(data: ndarray) → float#

Calculate the length of a path based on a list of coordinates

Parameters:

data – Array of shape (N, 2) containing a list of coordinates

Returns:

The total length of the path.

lmd.path.tsp_greedy_solve(node_list: ndarray, k: int = 100, return_sorted: bool = False) → ndarray | list[int]#

Find an approximation of the shortest path through a list of coordinates

Parameters:

  • node_list – Array of shape (N, 2) containing a list of coordinates

  • k – Number of Nearest Neighbours calculated for each Node.

  • return_sorted – If set to False a list of indices is returned. If set to True the sorted coordinates are returned.

Returns:

An array

  • return_sorted=True: Array of sorted nodes.

  • return_sorted=False: Ordered indices of nodes

lmd.path.tsp_hilbert_solve(data: ndarray, p: int = 3) → ndarray#

Approximate a short traversal path between centroids with a Hilbert Curve

A Hilbert curve provides a space-filling mapping from 2D coordinates to a one-dimensional order that tends to preserve spatial locality. Here, this property is used as a heuristic to obtain an ordering of point centroids that typically yields a shorter traversal path than a random ordering, but does not guarantee an optimal Traveling Salesperson solution.

Parameters:

  • data – 2D Array of shape (N, 2) containing a list of coordinates

  • p – Iterations to use in constructing the Hilbert curve.

Returns:

Ordered indices of data of the shape (N,) according to their position along the Hilbert curve.