initialize_2D_travelling_salesman

initialize_2D_travelling_salesman#

mrinufft.trajectories.inits.travelling_salesman.initialize_2D_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 2D 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 in O(n²). 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 (np.ndarray) – A 2-dimensional density array from which points are sampled.

  • first_cluster_by (str, optional) – The coordinate used to cluster points initially, by default None.

  • second_cluster_by (str, optional) – A secondary coordinate used for clustering within primary clusters, by default None.

  • sort_by (str, 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 2D array representing the TSP-ordered trajectory.

Return type:

np.ndarray

Raises:

ValueError – If density is not a 2-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.