Closest point from certain 2D point to list of 2D points Python

Question

I have a list of about 40 2D points (x and y). I want a script that starts at the first point from the list (say, 180,0) and finds the closest point from the list to that first point (180, 0). Once that closest point is found, it should do the same thing again (so closest point becomes first point), without using the points that already have been used (180, 0). And do this untill every point has been used. In this way, my random list should become ordered into a list of points that become a fluent linepath. My code so far looks like this:

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

This is what my linepath looks like now:

And this is what it should look like:

Points plotted look like this: (wrong order) So basically if I start at 180,0 and keep following the closest point (without letting the code to go back) it should work to end up with a list in correct order.

Anybody that can help me with my code?

Answer 1

IIUC, you could do something like:

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