Python, how to find a next nearest available points in 2D space?

0
votes

Given starting array [[0,0], [1, 0], [0, 1]]. How to find a next nearest available points (by distance to (0,0)) in 2D space in python? In the pic1 find the next available (by distance to (0,0)) in red-point? After append array, in pic2 find next available (by distance to (0,0)) in red-point again and keep growing?

**pic1**

pic2

2
pythonalgorithmmatrixartificial-intelligencenearest-neighbor
What about (0.000001, 0.000001)? It's even closer! -> Be more precise on what you try to achieve and under which conditions? – s.k
No decimal points for the coordinate. If points is same distance, smallest X is priority, ex (0,1) & (1,0) same distance, (0,1) amend first. – Jay

2 Answers

0
votes

Pesudo Code:

generate all possible ENTRIES;
Sort ENTRIES by Min(delta_x, delta_y);
best_distance2 = DOUBLE.MAX;

as long as next_item in ENTRIES is below `best_distance`:
    get next_item
    //get squared distance 
    d2 = delta_x^2  + delta_x^2;
    if best_distance2 > d2 
      best_distance2 = d2
      best_item = next_item
    end if
0
votes

Generate a list of (distance, Point) pairs & sort this list using the first element as key. Iterating over the sorted list would give you the next nearest point in each iteration.

points = [(2, 2), (0,0), (0,1)]

def distance(p):
    return p[0] ** 2 + p[1] ** 2

distances = [(distance(p), p) for p in points]
sorted_distances = sorted(distances, key=lambda x: x[0])
print(sorted_distances)