我有一个大约200,000个点的2D数组,并希望“抖动”这些点,以便任何点和它最近的邻居之间的距离是>=某个最小值。
在从头开始编写此算法之前,我想问一问:是否有任何规范的方法或常用算法来实现此行为?我认为在开始之前先回顾一下这些算法是有意义的。
其他人在这个问题上可以提供的任何建议都将非常感谢。
发布于 2018-10-08 21:13:04
我最终使用了一种名为"Lloyd iteration"的技术来解决这个问题。该算法背后的思想非常简单;要在一组点上运行Lloyd迭代,我们:
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。
发布于 2018-07-08 05:14:21
您的问题非常类似于气泡图构造(examples):在图表中放置指定半径的N个球体,使得:
总图表是一个尽可能小的图表
我在这个领域的知识不是很多,所以我不能为这个问题列出一个详尽的算法列表。我将在这篇文章中介绍我所知道的唯一一个,以及如何使其适应您的问题。
javascript图表库使用的一种常见方法似乎是基于物理的(例如:d3.js force clusters)。简而言之(根据我的理解),他们:
重力随机(或使用启发式)为球体提供初始位置。通过应用下列力,将球体视为对象,
这可以用来解决您的问题:将每个点视为直径为D
的球体的中心(D
是您希望每个点之间的最小距离)。所有球体都具有相同的质量(您可以简单地忽略质量,直接使用加速度而不是力)。
data.
正如我所说的,我对气泡图不是很熟悉。在这个主题上寻找替代算法可能很有趣,看看它们是否适合您的情况。
发布于 2019-01-05 09:03:59
H19除以成对距离,以便它们是每个点的单位向量H111,计算与其他点的距离之和:成对向量/成对距离平方*某个常数(力常数应设置为当点处于最小距离时,力较小,但不是通过以6计算的量来infinitesimal)
在所有情况下都应该收敛,但会在必要时扩展画布。此外,对于200,000个点,它也是内存和计算密集型的,但忽略大向量/小作用力的稀疏矩阵使其更容易处理。
https://stackoverflow.com/questions/51214496
复制相似问题