时间戳

首页 > 解决方案 > python计算距离最近xy点

python - python计算距离最近xy点

问题描述

所以我有一个点列表

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

起点为

["2.2 4.6"]

现在我想做的是得到离我的起点最近的点，然后是离那个点最近的点，依此类推。

所以我要计算距离

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

但同样，我试图让最接近我的起点，然后是最接近那个起点的点，依此类推。

好的，因为你在抱怨我没有显示足够的代码？

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

所以我通过了我的起点

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

所以现在我需要使用 2.5、3.6 作为我的起点并找到下一个最接近的等等

有没有人做过类似的事情？

标签： python

解决方案

一种可能性是使用广度优先搜索来扫描所有元素，并找到从队列中弹出的每个元素的最近点：

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"]))

输出：

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

结果是最近点的列表，由使用 确定math.hypot。

推荐阅读