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

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

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

其他人可以就这个问题提供的任何建议将不胜感激。

最佳答案

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

构建点的 Voronoi 图

将其 Voronoi 单元中的每个点居中

重复直到点被充分分离

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 。