initialize_3D_travelling_salesman

initialize_3D_travelling_salesman#

mrinufft.trajectories.inits.travelling_salesman.initialize_3D_travelling_salesman(Nc, Ns, density, first_cluster_by=None, second_cluster_by=None, sort_by=None, tsp_tol=1e-08, *, verbose=False, **sampling_kwargs)[source]#

Initialize a 3D trajectory using a Travelling Salesman Problem (TSP)-based path.

This is a reproduction of the work from [Cha+14]. The TSP solution is obtained using the 2-opt method with a complexity in O(n²) in time and memory.

An additional option is provided to cluster shots before solving the TSP and thus reduce drastically the computation time. The initial sampling method can also be customized.

Parameters:

  • Nc (int) – The number of clusters (or shots) to divide the trajectory into.

  • Ns (int) – The number of points per cluster.

  • density (NDArray) – A 3-dimensional density array from which points are sampled.

  • first_cluster_by ({"x", "y", "z", "r", "phi", "theta"}, optional) – The coordinate used to cluster points initially, by default None.

  • second_cluster_by ({"x", "y", "z", "r", "phi", "theta"}, optional) – A secondary coordinate used for clustering within primary clusters, by default None.

  • sort_by ({"x", "y", "z", "r", "phi", "theta"}, optional) – The coordinate by which to order points within each cluster, by default None.

  • tsp_tol (float, optional) – Convergence tolerance for the TSP solution, by default 1e-8.

  • verbose (bool, optional) – If True, displays a progress bar, by default False.

  • **sampling_kwargs (dict, optional) – Additional arguments to pass to mrinufft.trajectories.sampling.sample_from_density.

Returns:

A 3D array representing the TSP-ordered trajectory.

Return type:

NDArray

Raises:

ValueError – If density is not a 3-dimensional array.

References

[Cha+14]

Chauffert, Nicolas, Philippe Ciuciu, Jonas Kahn, and Pierre Weiss. “Variable density sampling with continuous trajectories.” SIAM Journal on Imaging Sciences 7, no. 4 (2014): 1962-1992.