以最小间距随机均匀分布点

debugcn 发表于 Dev

Compizfox

我正在尝试在二维空间中生成一组点的坐标，这些点随机均匀地间隔开，但彼此之间的距离不太近。

我开始使用np.random.uniform，生成nx 2个值（x和y坐标），然后在所有坐标上使用两个嵌套的for循环筛选坐标列表，以删除太近的点并将它们随机放置在其他位置：

# Generate xy coordinates for the grafting points
rng = np.random.RandomState(seed=self.rng_seed)
    coordinates = rng.uniform(high=(self.box_size[0], self.box_size[1]), size=(n_chains, 2))

for count in range(0, self.max_overlap_iter):
    moved_bead = False
    # Search for overlapping beads by looping over the list doubly
    for id_i, coord_i in enumerate(coordinates):
        for id_j, coord_j in enumerate(coordinates):
            if not id_i == id_j and np.sqrt(sum((coord_i - coord_j)**2)) < self.bead_size:
                # Move the second point
                coordinates[id_j] = rng.uniform(high=(self.box_size[0], self.box_size[1]), size=2)
                moved_bead = True
    if not moved_bead:
        break

将点移到新的随机位置后，它必须再次通过外循环，因为它可能仍然重叠。

问题在于，当点的密度足够高时，这实际上变得很慢，因为某些点“重叠”的飞速上升的可能性。因此，我必须建立最大数量的迭代，但这显然不能解决我的问题。

有没有更快，更有效的方法来做到这一点？

Compizfox

我最终写了一个Poisson磁盘点集生成器算法，该算法可以使用从其他算法中得到的一些想法生成非最大点集并在线性时间内运行。

当然，感谢@Kamil给我提供了Google的“泊松磁盘点集”一词；）

可以在这里找到：https : //github.com/Compizfox/MDBrushGenerators/blob/master/PoissonDiskGenerator.py

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。