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

Question

我有一个包含约 200,000 个点的二维数组，并希望“抖动”这些点，使任何点与其最近邻点之间的距离 >= 某个最小值。

在从头开始编写这个算法之前，我想问:是否有任何规范的方法或常用的算法来实现这个行为？我认为在着手解决这个问题之前先回顾一下这些算法是有意义的。

如果其他人可以就此问题提出任何建议，我们将不胜感激。

Answer 1

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

1. 构建点的 Voronoi 图
2. 将每个点放在其 Voronoi 单元中
3. 重复直到点足够分开

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 中构造约束 Lloyd 迭代的一些讨论和代码，我写了一点 blog post .