python - 给定列表中人员的二维坐标，我如何找到彼此之间的距离低于阈值的人？

Question

我有三元组列表：

• 姓名
• 坐标 x
• 坐标 y

混蛋是与列表中任何其他人的距离小于 2 的人。

我认为我的代码可以工作，但是由于嵌套循环，它的复杂性是 O(N²)。有没有可能让它更有效率？

people=[
  ('Mickey', 4.6, 3.2),
  ('Donald', 6.1, 3.2),
  ('Bambi',  6.2, 5.2),
  ('Goofy',  6.4, 2.0),
  ('Eeyore', 7.0, 6.4)]

min_distance_sq=2.**2

jerks=set()
for p1 in people:
    if p1 in jerks:
        continue
    for p2 in people:
        if p1[1]==p2[1]:
            continue
        distance_sq=(p1[2]-p2[2])**2+(p1[3]-p2[3])**2
        if distance_sq < min_distance_sq:
            jerks.add(p1)
            jerks.add(p2)
            break

for jerk in jerks:
    print(jerk[0],'from',jerk[1],'is jerk')

标签： pythonalgorithmoptimization

Answer 1

您可以构建某种二进制空间分区 (BSP) 数据结构。

例如，构建时间为 O(nlogn) 的kd 树，并对每个项目进行“最近邻”查询