Python：在（x，y）平面上一堆点之间的平均距离

Question

计算平面中两点之间的距离的公式是众所周知且简单明了的。

然而，对于一个包含n个点的问题，你想要计算平均距离，最好的方法是什么？

例如：

import matplotlib.pyplot as plt
x=[89.86, 23.0, 9.29, 55.47, 4.5, 59.0, 1.65, 56.2, 18.53, 40.0]
y=[78.65, 28.0, 63.43, 66.47, 68.0, 69.5, 86.26, 84.2, 88.0, 111.0]
plt.scatter(x, y,color='k')
plt.show()

The distance is simply rendered as:

import math
dist=math.sqrt((x2-x1)**2+(y2-y1)**2)

但是这是一个组合问题，不允许重复。该如何解决？

- FaCoffee

---

循环上一个。 - Ma0

如果您循环上一个操作，最终会重复计算：10选2，这将得出45种组合。 - FaCoffee

时间复杂度将会很有趣。 - Ari Gold

@AriGold 这是 O(n^2) > t > O(n)。 - Ma0

@CF84 一个“智能循环”也是一个“循环”。 - Ma0

Answer 1

itertools.combinations提供了不重复的组合：

>>> for combo in itertools.combinations([(1,1), (2,2), (3,3), (4,4)], 2):
...     print(combo)
...
((1, 1), (2, 2))
((1, 1), (3, 3))
((1, 1), (4, 4))
((2, 2), (3, 3))
((2, 2), (4, 4))
((3, 3), (4, 4))

您问题的代码：

import math
from itertools import combinations

def dist(p1, p2):
    (x1, y1), (x2, y2) = p1, p2
    return math.sqrt((x2 - x1)**2 + (y2 - y1)**2)

x = [89.86, 23.0, 9.29, 55.47, 4.5, 59.0, 1.65, 56.2, 18.53, 40.0]
y = [78.65, 28.0, 63.43, 66.47, 68.0, 69.5, 86.26, 84.2, 88.0, 111.0]

points = list(zip(x,y))
distances = [dist(p1, p2) for p1, p2 in combinations(points, 2)]
avg_distance = sum(distances) / len(distances)

- Steven Rumbalski

Answer 2

你可以使用Scipy库中的函数pdist来解决这个问题（可能更有效率）。这个函数计算n维空间中观测值之间的成对距离。

要解决这个问题，可以使用以下函数：

from scipy.spatial.distance import pdist
import numpy as np

def compute_average_distance(X):
    """
    Computes the average distance among a set of n points in the d-dimensional space.

    Arguments:
        X {numpy array} - the query points in an array of shape (n,d), 
                          where n is the number of points and d is the dimension.
    Returns:
        {float} - the average distance among the points
    """
    return np.mean(pdist(X))

- kpatron

Answer 3

在这种情况下，您需要遍历点的序列：

：

from math import sqrt

def avg_distance(x,y):
    n = len(x)
    dist = 0
    for i in range(n):
        xi = x[i]
        yi = y[i]
        for j in range(i+1,n):
            dx = x[j]-xi
            dy = y[j]-yi
            dist += sqrt(dx*dx+dy*dy)
    return 2.0*dist/(n*(n-1))

在最后一步，我们将总距离除以n×(n-1)/2，这是以下计算的结果：

n-1
---
\       n (n-1)
/   i = -------
---        2
i=1

这是我们计算的距离总数。

在这里，我们不测量点与其自身之间的距离（这当然始终为0）。请注意，这当然会影响平均值，因为您也不将它们计入其中。

假设有n个点，则此算法的运行时间为O(n²)。

- Willem Van Onsem