在边界内的表面上分布点
我对在四边形表面（如正方形）上分布预定义数量的点的方法（算法）感兴趣。
主要问题是每个点必须具有彼此的最小和最大接近度（在两个预定义值之间随机）。 基本上任何两点的距离都不应该比说2更接近，而不是3。
我的代码将在ruby中实现（点是位置，表面是地图），但任何想法或片段都是受欢迎的，因为我的所有想法都包括相当多的蛮力。
试试这篇论文 。 它有一个很好的，直观的算法，可以满足您的需求。
在我们的模型化中，我们采用了另一种模型：我们认为每个中心都通过排斥字符串与其所有邻居相关。
在模拟开始时，中心是随机分布的，以及弦的强度。 我们随机选择移动一个中心; 然后我们计算由给定中心的所有邻居引起的合力，并且我们计算在所产生的力的意义上成比例和定向的位移。
经过一定次数的迭代（取决于中心的数量和初始随机性的程度），系统变得稳定。
如果从图中不清楚，该方法产生均匀分布的点。 你可以使用一个在你的界限内为零的力（例如在2和3之间），否则为非零（如果点太接近则令人厌恶，如果太远则有吸引力）。
这是我的Python实现（抱歉，我不知道ruby）。 只需导入它并调用uniform（）来获取点列表。
import numpy as np from numpy.linalg import norm import pylab as pl # find the nearest neighbors (brute force) def neighbors(x, X, n=10): dX = X - x d = dX[:,0]**2 + dX[:,1]**2 idx = np.argsort(d) return X[idx[1:11]] # repulsion force, normalized to 1 when d == rmin def repulsion(neib, x, d, rmin): if d == 0: return np.array([1,-1]) return 2*(x - neib)*rmin/(d*(d + rmin)) def attraction(neib, x, d, rmax): return rmax*(neib - x)/(d**2) def uniform(n=25, rmin=0.1, rmax=0.15): # Generate randomly distributed points X = np.random.random_sample( (n, 2) ) # Constants # step is how much each point is allowed to move # set to a lower value when you have more points step = 1./50. # maxk is the maximum number of iterations # if step is too low, then maxk will need to increase maxk = 100 k = 0 # Force applied to the points F = np.zeros(X.shape) # Repeat for maxk iterations or until all forces are zero maxf = 1. while maxf > 0 and k < maxk: maxf = 0 for i in xrange(n): # Force calculation for the i-th point x = X[i] f = np.zeros(x.shape) # Interact with at most 10 neighbors Neib = neighbors(x, X, 10) # dmin is the distance to the nearest neighbor dmin = norm(Neib[0] - x) for neib in Neib: d = norm(neib - x) if d < rmin: # feel repulsion from points that are too near f += repulsion(neib, x, d, rmin) elif dmin > rmax: # feel attraction if there are no neighbors closer than rmax f += attraction(neib, x, d, rmax) # save all forces and the maximum force to normalize later F[i] = f if norm(f) <> 0: maxf = max(maxf, norm(f)) # update all positions using the forces if maxf > 0: X += (F/maxf)*step k += 1 if k == maxk: print "warning: iteration limit reached" return X 我认为你的一个暴力想法包括随意重复生成点并检查约束是否恰好满足。
另一种方法是采用满足约束的配置，并反复扰乱其中的一小部分，随机选择 – 例如移动单个点 – 移动到随机选择的附近配置。 如果你经常这样做，你应该转移到几乎独立于起点的随机配置。 这可以在http://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_algorithm或http://en.wikipedia.org/wiki/Gibbs_sampling下certificate是合理的。
我可能会尝试随意做，然后通过并删除接近其他点的点。 您可以比较距离的平方以节省一些数学时间。
或者创建带边框的单元格并在每个单元格中放置一个点。 随机性较小，取决于这是否“只是为了看起来的东西”。 但它可能非常快。
我做了一个妥协，最后使用Poisson Disk Sampling方法。
结果非常接近我所需要的，特别是尝试次数较少（这也大大降低了成本）。