问Python:确保每个成对距离都是>=某个最小距离

EN

我最终使用了一种名为"Lloyd iteration"的技术来解决这个问题。该算法背后的思想非常简单；要在一组点上运行Lloyd迭代，我们：

1. 构建点
2. 中心的Voronoi图其Voronoi像元中的每个点
3. Repeat直到点充分分隔

This gist有一些示例代码(带有可视化)：

from lloyd import Field
from scipy.spatial import voronoi_plot_2d
import matplotlib.pyplot as plt
import numpy as np
import umap, os

def plot(vor, name, e=0.3):
  '''Plot the Voronoi map of 2D numpy array X'''
  plot = voronoi_plot_2d(vor, show_vertices=False, line_colors='y', line_alpha=0.5, point_size=5)
  plot.set_figheight(14)
  plot.set_figwidth(20)
  plt.axis([field.bb[0]-e, field.bb[1]+e, field.bb[2]-e, field.bb[3]+e])
  if not os.path.exists('plots'): os.makedirs('plots')
  if len(str(name)) < 2: name = '0' + str(name)
  plot.savefig( 'plots/' + str(name) + '.png' )

# get 1000 observations in two dimensions and plot their Voronoi map
np.random.seed(1144392507)
X = np.random.rand(1000, 4)
X = umap.UMAP().fit_transform(X)

# run 20 iterations of Lloyd's algorithm
field = Field(X)
for i in range(20):
  print(' * running iteration', i)
  plot(field.voronoi, i)
  field.relax()

结果是，点的移动就像它们在以下gif中所做的那样：

​

​

注意:上面的gif显示了无约束的Lloyd迭代，其中输出域可能非常大。对于使用Python语言构建约束劳埃德迭代的一些讨论和代码，我编写了一些blog post。

您的问题非常类似于气泡图构造(examples)：在图表中放置指定半径的N个球体，使得：

总图表是一个尽可能小的图表

我在这个领域的知识不是很多，所以我不能为这个问题列出一个详尽的算法列表。我将在这篇文章中介绍我所知道的唯一一个，以及如何使其适应您的问题。

javascript图表库使用的一种常见方法似乎是基于物理的(例如：d3.js force clusters)。简而言之(根据我的理解)，他们：

重力随机(或使用启发式)为球体提供初始位置。通过应用下列力，将球体视为对象，

1. 运行一个小型物理模拟：
2. to
   • attracts every friction to separate overlapping spheres.
   • "Fluid“friction:减慢每个具有速度的对象。这可确保模拟在某一点停止(防止oscillations).

​

这可以用来解决您的问题:将每个点视为直径为D的球体的中心(D是您希望每个点之间的最小距离)。所有球体都具有相同的质量(您可以简单地忽略质量，直接使用加速度而不是力)。

data.

• Physics：

1. 球体的初始位置是你的输入，只是丢弃了重力，因为你不想/不需要“打包”这些点。

正如我所说的，我对气泡图不是很熟悉。在这个主题上寻找替代算法可能很有趣，看看它们是否适合您的情况。

1. 计算所有点之间的成对距离- sklearn.metrics.pairwise.euclidean_distances
2. 计算所有成对距离的最小值
3. 如果最小距离足够小，请退出
4. 计算每两点之间的成对向量，以便它们彼此远离

H19除以成对距离，以便它们是每个点的单位向量H111，计算与其他点的距离之和:成对向量/成对距离平方*某个常数(力常数应设置为当点处于最小距离时，力较小，但不是通过以6计算的量来infinitesimal)

1. nudge所有点。还应将微移限制在最小/10，因此如果两个点结束在同一点，则它们不会被轻推无限距离间隔
2. 重复，直到最小值足够小

在所有情况下都应该收敛，但会在必要时扩展画布。此外，对于200,000个点，它也是内存和计算密集型的，但忽略大向量/小作用力的稀疏矩阵使其更容易处理。