Ближайший сосед для списка массивов

Это похоже на задачу_путешественника_продавца. Вычислите попарное расстояние между всеми узлами, определите собственное расстояние NaN/Inf, затем получите кратчайший путь:

from numpy import array
import networkx as nx

coordinates= [array([[ 300, 2300],
                     [ 670, 2360],
                     [ 400, 2300]]),
              array([[1500, 1960],
                     [1620, 2200],
                     [1505, 1975]]),
              array([[ 980, 1965],
                     [1060, 2240],
                     [1100, 2250],
                     [ 980, 1975]]),
              array([[ 565, 1940],
                     [ 680, 2180],
                     [ 570, 1945]])]

# extract starts and ends
starts = np.vstack([a[0]  for a in coordinates])
ends   = np.vstack([a[-1] for a in coordinates])

# compute pairwise distances, except self
dist = np.sqrt(((starts[:, None] - ends)**2).sum(-1))
np.fill_diagonal(dist, np.nan)

# build the graph
G = nx.from_numpy_array(np.round(dist, 1), create_using=nx.DiGraph)
G.remove_edges_from(nx.selfloop_edges(G))

# find shortest path (NB. cycle could be False)
path = nx.approximation.traveling_salesman_problem(G, cycle=True)
# [1, 0, 3, 2, 1]

out = [coordinates[i] for i in path[1:]]

Если вам не обязательно нужен цикл, используйте cycle=False и out = [coordinates[i] for i in path].

Выход:

[array([[ 300, 2300],
        [ 670, 2360],
        [ 400, 2300]]),
 array([[ 565, 1940],
        [ 680, 2180],
        [ 570, 1945]]),
 array([[ 980, 1965],
        [1060, 2240],
        [1100, 2250],
        [ 980, 1975]]),
 array([[1500, 1960],
        [1620, 2200],
        [1505, 1975]])]

Промежуточный dist:

array([[          nan, 1248.05849222,  753.67433285,  446.01008957],
       [1151.34703717,           nan,  520.21630117,  930.12095988],
       [ 669.79474468,  525.09522946,           nan,  410.48751504],
       [ 396.01136347,  940.65137006,  416.47328846,           nan]])

График (с расстояниями в виде меток ребер и кратчайшим путем, выделенным красным):

Используйте BallTree: из sklearn.neighbours импортируйте BallTree.

BallTree отлично справляется с поиском ближайших соседей в многомерных данных. особенно в сочетании с такой техникой, как rest_mask, сосредоточиться на соответствующих сегментах. Он использует древовидную структуру, которая обеспечивает более быстрый поиск.

import numpy as np
from sklearn.neighbors import BallTree

coordinates = [
    np.array([[300, 2300],
              [670, 2360],
              [400, 2300]]),
    np.array([[1500, 1960],
              [1620, 2200],
              [1505, 1975]]),
    np.array([[980, 1965],
              [1060, 2240],
              [1100, 2250],
              [980, 1975]]),
    np.array([[565, 1940],
              [680, 2180],
              [570, 1945]])
]

# Extract first and last coordinates
first_coords = np.array([arr[0] for arr in coordinates])
last_coords = np.array([arr[-1] for arr in coordinates])

#print("First coordinates:\n", first_coords)
'''
First coordinates:
 [[ 300 2300]
 [1500 1960]
 [ 980 1965]
 [ 565 1940]]
'''
#print("Last coordinates:\n", last_coords)

'''
Last coordinates:
 [[ 400 2300]
 [1505 1975]
 [ 980 1975]
 [ 570 1945]]
'''
# Build a BallTree for first coordinates
tree = BallTree(first_coords)

# Initialize the sorted list with the first coordinate set
sorted_indices = [0]
'''
np.ones fills the mask with all elements set to True.
This signifies that initially, all segments are considered "unused" 
and eligible to be chosen as the next closest neighbor in the loop.
the remaining_mask acts as a dynamic flag that tracks the used segments. 
Setting elements to False prevents the algorithm from revisiting previously 
chosen segments as potential neighbors.
'''
remaining_mask = np.ones(len(coordinates), dtype=bool)
'''
This indicates that the first segment has already been chosen as the starting point 
and is no longer considered "available"
for further comparisons in subsequent iterations of the loop.
'''

remaining_mask[0] = False  # Mark the first segment as used
current_index = 0 

# Find closest neighbors and filter with mask in one step
while remaining_mask.any():
    # Query BallTree for k=len(coordinates) to get all distances
    distances, indices = tree.query(last_coords[current_index].reshape(1, -1), k=len(coordinates))
    #print(f"Querying BallTree for last_coords[{current_index}]:", last_coords[current_index])
    
    # Combine mask and indices for efficient filtering
    flat_indices = indices.ravel()

    filtered_mask = remaining_mask[flat_indices]

    filtered_indices = flat_indices[filtered_mask]

    closest_index = filtered_indices[0]

    # Update sorted indices, current index, and mask
    sorted_indices.append(closest_index)
    current_index = closest_index
    remaining_mask[closest_index] = False

# Use the sorted indices to arrange the coordinates
sorted_coordinates = [coordinates[i] for i in sorted_indices]

print("Sorted coordinates:\n", sorted_coordinates)
'''
Sorted coordinates:
[array([[ 300, 2300],
       [ 670, 2360],
       [ 400, 2300]]), 
array([[ 565, 1940],
       [ 680, 2180],
       [ 570, 1945]]), 
array([[ 980, 1965],
       [1060, 2240],
       [1100, 2250],
       [ 980, 1975]]), 
array([[1500, 1960],
       [1620, 2200],
       [1505, 1975]])]

'''