2

so i have a list of points

["9.5 7.5", "10.2 19.1", "9.7 10.2", "2.5 3.6", "5.5 6.5", "7.8 9.8"]

with a starting point of

["2.2 4.6"]

now what i am trying to do it is get the closest point to my starting point, then the closest point to that point and so on.

So i get to calculate distance

def dist(p1,p2):
    return math.sqrt((p2[0] - p1[0]) ** 2 + (p2[1] - p1[1]) ** 2)

but again, i'm trying to get the closest to my starting point, then the closest point to that one and so on.

ok, because you are complaing i didn't show enough code?

fList = ["2.5 3.6", "9.5 7.5", "10.2 19.1", "9.7 10.2",  "5.5 6.5", "7.8 9.8"]
def distance(points):
    p0, p1 = points
    return math.sqrt((p0[0] - p1[0])**2 + (p0[1] - p1[1])**2)

min_pair = min(itertools.combinations(fList, 2), key=distance)
min_distance = distance(min_pair)

print min_pair
print min_distance

so i get passing my starting point I get

([2.2, 4.6], [2.5, 3.6])

So now i need to use 2.5, 3.6 as my starting point and find the next closest and so on

Has anyone done anything similar?

2
  • Welcome to StackOverflow. Please read and follow the posting guidelines in the help documentation, as suggested when you created this account. On topic and how to ask apply here. StackOverflow is not a design, coding, research, or tutorial service.
    – Prune
    Commented May 3, 2018 at 16:21
  • Nice edit, you are thinking too hard about it. You can easily solve this by using sort() on the list of floatpoints if you give sort() as key= your distance function. no need for itertools. Commented May 3, 2018 at 16:34

3 Answers 3

3

A possibility is to use a breadth-first search to scan all elements, and find the closest point for each element popped off the queue:

import re, collections
import math

s = ["9.5 7.5", "10.2 19.1", "9.7 10.2", "2.5 3.6", "5.5 6.5", "7.8 9.8"]
def cast_data(f):
   def wrapper(*args, **kwargs):
     data, [start] = args
     return list(map(lambda x:' '.join(map(str, x)), f(list(map(lambda x:list(map(float, re.findall('[\d\.]+', x))), data)), list(map(float, re.findall('[\d\.]+', start))))))
   return wrapper

@cast_data
def bfs(data, start, results=[]):
   queue = collections.deque([start])
   while queue and data:
     result = queue.popleft()
     possible = min(data, key=lambda x:math.hypot(*[c-d for c, d in zip(result, x)]))
     if possible not in results:
       results.append(possible)
       queue.append(possible)
       data = list(filter(lambda x:x != possible, data))
   return results

print(bfs(s, ["2.2 4.6"]))

Output:

['2.5 3.6', '5.5 6.5', '7.8 9.8', '9.7 10.2', '9.5 7.5', '10.2 19.1']

The result is the listing of closest points, as determined by using math.hypot.

2
  • you are evil :) - I got [(1.0440306508910546, [2.5, 3.6]), (3.8078865529319543, [5.5, 6.5]), (7.64198926981712, [7.8, 9.8]), (7.854934754662192, [9.5, 7.5]), (9.360021367496977, [9.7, 10.2]), (16.560495161679196, [10.2, 19.1])] - but If I post my 6 liner that would be a copy&paste& understand solution Commented May 3, 2018 at 16:28
  • @PatrickArtner Ah, you included the differences along with each point.
    – Ajax1234
    Commented May 3, 2018 at 16:34
1

You can try the following code. Much simpler and short. Uses a comparator to sort the list depending on the distance from the starting point (2.2,4.6)

import math
data = ["9.5 7.5", "10.2 19.1", "9.7 10.2", "2.5 3.6", "5.5 6.5", "7.8 9.8"]
data.sort(key=lambda x: math.sqrt((float(x.split(" ")[0]) - 2.2)**2 +
                                  (float(x.split(" ")[1]) -4.6)**2))
print(data)

# output ['2.5 3.6', '5.5 6.5', '7.8 9.8', '9.5 7.5', '9.7 10.2', '10.2 19.1']
0

You can simply sort a list by a key you define as you wish - f.e. by your distance function:

import math

def splitFloat(x):
    """Split each element of x on space and convert into float-sublists"""
    return list(map(float,x.split()))

def dist(p1, p2):
    # you could remove the sqrt for computation benefits, its a symetric func
    # that does not change the relative ordering of distances
    return math.sqrt((p2[0] - p1[0]) ** 2 + (p2[1] - p1[1]) ** 2)

p = ["9.5 7.5", "10.2 19.1", "9.7 10.2", "2.5 3.6", "5.5 6.5", "7.8 9.8"]

s = splitFloat("2.2 4.6")       # your start point
p = [splitFloat(x) for x in p]  # your list of points

# sort by distance between each individual x and s
p.sort(key = lambda x:dist(x,s))

d = [ (dist(x,s),x) for x in p]  # create tuples with distance for funsies
print(p)
print(d)

Output:

 [[2.5, 3.6], [5.5, 6.5], [7.8, 9.8], [9.5, 7.5], [9.7, 10.2], [10.2, 19.1]]

[(1.0440306508910546, [2.5, 3.6]), (3.8078865529319543, [5.5, 6.5]),
 (7.64198926981712, [7.8, 9.8]), (7.854934754662192, [9.5, 7.5]), 
 (9.360021367496977, [9.7, 10.2]), (16.560495161679196, [10.2, 19.1])]

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.