Ближайшая точка от определенной двумерной точки до списка двумерных точек Python

Question

У меня есть список из примерно 40 2D-точек (x и y). Я хочу, чтобы сценарий начинался с первой точки из списка (скажем, 180,0) и находил ближайшую точку от списка до первой точки (180, 0). Как только эта ближайшая точка будет найдена, она должна повторить то же самое (так что ближайшая точка станет первой точкой), не используя уже использованные точки (180, 0). И делайте это до тех пор, пока не будет использована каждая точка. Таким образом, мой случайный список должен быть упорядочен в список точек, которые становятся плавным линейным путем. Мой код до сих пор выглядит следующим образом:

def arrange_points(points): 
    # arranges all 2D points in a fluent and consistent linepath order 
    size = len(points) #number of elements in list 
    di = [] #list containing all distances from start point 
    start_point = points[0] 

    for i in range (size): 
     next_points = points[i] 

     dist = math.sqrt((next_points[0] - start_point[0])**2 + (next_points[1] - start_point[1])**2) #distance of start point to all other points 
     di.append(dist) 

     ln = min(filter(None, di)) # smallest distance from start point, except 0 
     f = di.index(ln) # finds place of ln in list di 
     next_point = points[f] # retrieves corresponding point from points, that corresponds to ln 
    return di 
    return next_point 

di = arrange_points(points) 

# 0 and previous points cannot be taken 

Это то, что мой linepath выглядит сейчас:

И это то, что он должен выглядеть следующим образом:

Описанные точки выглядят следующим образом: (неправильный порядок) Итак, в основном, если я начинаю с 180,0 и продолжаю следовать ближайшей точке (без lett чтобы вернуть код), он должен работать, чтобы в итоге получить список в правильном порядке.

Кто-нибудь может помочь мне с моим кодом?

Answer 1

IIUC, вы могли бы сделать что-то вроде:

def get_nearest(points, coord): 
    """Return closest point to coord from points""" 
    dists = [(pow(point[0] - coord[0], 2) + pow(point[1] - coord[1], 2), point) 
       for point in points]    # list of (dist, point) tuples 
    nearest = min(dists) 
    return nearest[1] # return point only 

next_point = points.pop(0) # get first point 
line_path = [] 
line_path.append(next_point) 

while len(points) > 1: 
    next_point = get_nearest(points, next_point) 
    line_path.append(next_point) 
    points.remove(next_point) 

line_path.extend(points) # add last point