Python create list of closest points for drone path

April 21, 2022

I’m trying to create a function that takes a list of points and returns a new list of points,
beginning with the first point and then at each stage, moving to the closest point that has not yet been visited.

Input list: [(2.8, 9.8), (0.3, 8.3), (4.4, 8.8), (6.8, 7.4), (4.1, 0.3), (4.5, 0.0), (7.6, 1.1), (5.0, 8.2), (7.7, 1.8), (3.4, 6.9), (4.8, 3.2), (0.7, 7.9)]

Essentially I want the function to put the start point in the input list (2.8, 9.8) as the first point in the output list. Then since the closest point to the start point (2.8, 9.8) is (4.4, 8.8), (4.4, 8.8) should appear second in the list, the closest remaining point to (4.4, 8.8) is (5.0, 8.2), so (5.0, 8.2) should appear third in the list and so on.

This should output the list: [(2.8, 9.8), (4.4, 8.8), (5.0, 8.2), (6.8, 7.4), (3.4, 6.9), (0.7, 7.9), (0.3, 8.3), (4.8, 3.2), (4.1, 0.3), (4.5, 0.0), (7.6, 1.1), (7.7, 1.8)].

Really stumped on where I’m going wrong in my code, this is what I have so far:

def best_path(points) :
    path = []
    closest_distance = math.sqrt((points[0][0] - points[1][0])**2 + (points[0][1] - points[1][1])**2)
    previous_point = points[0]
    x = 0
    while x < len(points) :
        for i in points :
            distance = math.sqrt((previous_point[0] - i[0])**2 + (previous_point[1] - i[1])**2)
            x+=1
            if closest_distance > distance :
                closest_point = i
                previous_point = i
                path.append(closest_point)
    return path

This returns: [(2.8, 9.8), (4.4, 8.8), (6.8, 7.4), (5.0, 8.2), (3.4, 6.9), (0.7, 7.9)]

Should return: [(2.8, 9.8), (4.4, 8.8), (5.0, 8.2), (6.8, 7.4), (3.4, 6.9), (0.7, 7.9), (0.3, 8.3), (4.8, 3.2), (4.1, 0.3), (4.5, 0.0), (7.6, 1.1), (7.7, 1.8)].

>Solution :

I suggest you to use numpy.argmin to get the index of the point withminimum distance once you have computed them all. You also have to remove each point from points once you have visited it, like this:

def best_path(points) :
    path = []
    prev_p = points[0]
    dist = [(prev_p[0] - p[0])**2 + (prev_p[1] - p[1])**2 for p in points]
    
    while points:
        dist = [(prev_p[0] - p[0])**2 + (prev_p[1] - p[1])**2 for p in points]
        i = np.argmin(dist)
        closest_p = points.pop(i)
        prev_p = closest_p
        path.append(closest_p)
    
    return path

or without using argmin: