将点分布在边界内的表面上

我对一种在 4 面（如正方形）上分布预定义数量的点的方法（算法）感兴趣。

主要问题是每个点必须具有彼此之间的最小和最大接近度（两个预定义值之间的随机值）。基本上，任何两点的距离不应小于 2，也不应大于 3。

我的代码将用 ruby​​ 实现（点是位置，表面是地图），但任何想法或片段绝对受到欢迎，因为我的所有想法都包含相当多的蛮力。

Try 这张纸 http://diwww.epfl.ch/w3lsp/publications/colour/prhsfcabp_93.html。它有一个很好、直观的算法，可以满足您的需要。

在我们的建模中，我们采用了另一种模型：我们认为每个中心都通过排斥弦与其所有邻居相关。

在模拟开始时，中心是随机分布的，并且各中心的强度也是随机分布的 字符串。我们随机选择移动一个中心；然后我们计算所有引起的合力 给定中心的邻居，我们计算成比例且定向的位移 就合力而言。

经过一定次数的迭代（这取决于迭代次数） 中心和初始随机性程度）系统变得稳定。

如果从图中看不清楚，这种方法会生成均匀分布的点。您可以使用在边界内为零的力（例如，在 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