29

我想生成一个从 0 到 2500 的一堆 (x, y) 坐标，它不包括彼此相距 200 以内的点而无需递归。

现在，我让它检查所有先前值的列表，看看是否有任何值与所有其他值相距甚远。这确实效率低下，如果我需要生成大量点，则需要很长时间。

那么我该怎么做呢？

4

5 回答 5

13

这是 Hank Ditton 建议的变体，在时间和记忆方面应该更有效，特别是如果您从所有可能的点中选择相对较少的点。这个想法是，每当生成一个新点时，它的 200 个单位内的所有内容都会添加到一组要排除的点中，并根据这些点检查所有新生成的点。

import random

radius = 200
rangeX = (0, 2500)
rangeY = (0, 2500)
qty = 100  # or however many points you want

# Generate a set of all points within 200 of the origin, to be used as offsets later
# There's probably a more efficient way to do this.
deltas = set()
for x in range(-radius, radius+1):
    for y in range(-radius, radius+1):
        if x*x + y*y <= radius*radius:
            deltas.add((x,y))

randPoints = []
excluded = set()
i = 0
while i<qty:
    x = random.randrange(*rangeX)
    y = random.randrange(*rangeY)
    if (x,y) in excluded: continue
    randPoints.append((x,y))
    i += 1
    excluded.update((x+dx, y+dy) for (dx,dy) in deltas)
print randPoints
于 2013-10-29T20:44:28.607 回答
7

我会过度生成点，target_N < input_N并使用KDTree过滤它们。例如：

import numpy as np
from scipy.spatial import KDTree
N   = 20
pts = 2500*np.random.random((N,2))

tree = KDTree(pts)
print tree.sparse_distance_matrix(tree, 200)

会给我彼此“接近”的积分。从这里应用任何过滤器应该很简单：

  (11, 0)   60.843426339
  (0, 11)   60.843426339
  (1, 3)    177.853472309
  (3, 1)    177.853472309
于 2013-10-29T20:41:56.140 回答
3

一些选项：

  • 使用您的算法，但使用可以加快最近邻居查找速度的kd-tree来实现它
  • 在 [0, 2500]^2 正方形上构建规则网格，并以网格中每个交点为中心的二维正态分布随机“摇动”所有点
  • 绘制大量随机点，然后应用k-means算法并仅保留质心。它们将彼此相距很远，并且该算法虽然是迭代的，但可以比您的算法更快地收敛。
于 2013-10-29T20:45:41.090 回答
3

这已经得到了回答，但它与我的工作非常相干，所以我尝试了一下。我实现了这篇笔记中描述的算法，我发现它链接自这篇博文。不幸的是，它并不比其他提议的方法快，但我确信需要进行优化。

import numpy as np
import matplotlib.pyplot as plt

def lonely(p,X,r):
    m = X.shape[1]
    x0,y0 = p
    x = y = np.arange(-r,r)
    x = x + x0
    y = y + y0

    u,v = np.meshgrid(x,y)

    u[u < 0] = 0
    u[u >= m] = m-1
    v[v < 0] = 0
    v[v >= m] = m-1

    return not np.any(X[u[:],v[:]] > 0)

def generate_samples(m=2500,r=200,k=30):
    # m = extent of sample domain
    # r = minimum distance between points
    # k = samples before rejection
    active_list = []

    # step 0 - initialize n-d background grid
    X = np.ones((m,m))*-1

    # step 1 - select initial sample
    x0,y0 = np.random.randint(0,m), np.random.randint(0,m)
    active_list.append((x0,y0))
    X[active_list[0]] = 1

    # step 2 - iterate over active list
    while active_list:
        i = np.random.randint(0,len(active_list))
        rad = np.random.rand(k)*r+r
        theta = np.random.rand(k)*2*np.pi

        # get a list of random candidates within [r,2r] from the active point
        candidates = np.round((rad*np.cos(theta)+active_list[i][0], rad*np.sin(theta)+active_list[i][1])).astype(np.int32).T

        # trim the list based on boundaries of the array
        candidates = [(x,y) for x,y in candidates if x >= 0 and y >= 0 and x < m and y < m]

        for p in candidates:
            if X[p] < 0 and lonely(p,X,r):
                X[p] = 1
                active_list.append(p)
                break
        else:
            del active_list[i]

    return X

X = generate_samples(2500, 200, 10)
s = np.where(X>0)
plt.plot(s[0],s[1],'.')

结果：

生成的样本模式

于 2013-10-31T15:19:29.617 回答
0

根据链接，来自 aganders3 的方法称为泊松圆盘采样。您可能能够找到使用本地网格搜索来查找“重叠”的更有效的实现。例如泊松圆盘采样。因为你在约束系统，所以它不可能是完全随机的。平面中具有均匀半径的圆的最大堆积约为 90%，并且当圆排列成完美的六边形阵列时实现。随着您请求的点数接近理论限制，生成的排列将变得更加六边形。以我的经验，使用这种方法很难达到 60% 以上的均匀圆圈填充。

于 2019-06-11T16:53:32.077 回答