python之点间距最小的随机均匀分布

我正在尝试生成 2d 空间中一组点的坐标，这些点随机均匀分布，但彼此不太接近。

我从 np.random.uniform 开始，生成 n x 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 

在一个点被移动到一个新的随机位置后，它必须再次经过外循环，因为它可能仍然重叠。

问题在于，当点的密度足够高时，这会变得非常慢，因为某些点“重叠”的概率会飙升。因此，我必须构建最大迭代次数，但这显然不是我的问题的解决方案。

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

请您参考如下方法:

您是否尝试过使用泊松盘采样算法？

我想这可能是您要找的。

Python implementation

Jason Davies Poisson-Disc Sampling

Mike Bostock implementation in Javascript

下面是删除时的代码

<!DOCTYPE html> 
<meta charset="utf-8"> 
<body> 
<script src="//d3js.org/d3.v3.min.js"></script> 
<script> 
 
var width = 960, 
    height = 500; 
 
var sample = poissonDiscSampler(width, height, 10); 
 
var svg = d3.select("body").append("svg") 
    .attr("width", width) 
    .attr("height", height); 
 
d3.timer(function() { 
  for (var i = 0; i < 10; ++i) { 
    var s = sample(); 
    if (!s) return true; 
    svg.append("circle") 
        .attr("cx", s[0]) 
        .attr("cy", s[1]) 
        .attr("r", 0) 
      .transition() 
        .attr("r", 2); 
  } 
}); 
 
// Based on https://www.jasondavies.com/poisson-disc/ 
function poissonDiscSampler(width, height, radius) { 
  var k = 30, // maximum number of samples before rejection 
      radius2 = radius * radius, 
      R = 3 * radius2, 
      cellSize = radius * Math.SQRT1_2, 
      gridWidth = Math.ceil(width / cellSize), 
      gridHeight = Math.ceil(height / cellSize), 
      grid = new Array(gridWidth * gridHeight), 
      queue = [], 
      queueSize = 0, 
      sampleSize = 0; 
 
  return function() { 
    if (!sampleSize) return sample(Math.random() * width, Math.random() * height); 
 
    // Pick a random existing sample and remove it from the queue. 
    while (queueSize) { 
      var i = Math.random() * queueSize | 0, 
          s = queue[i]; 
 
      // Make a new candidate between [radius, 2 * radius] from the existing sample. 
      for (var j = 0; j < k; ++j) { 
        var a = 2 * Math.PI * Math.random(), 
            r = Math.sqrt(Math.random() * R + radius2), 
            x = s[0] + r * Math.cos(a), 
            y = s[1] + r * Math.sin(a); 
 
        // Reject candidates that are outside the allowed extent, 
        // or closer than 2 * radius to any existing sample. 
        if (0 <= x && x < width && 0 <= y && y < height && far(x, y)) return sample(x, y); 
      } 
 
      queue[i] = queue[--queueSize]; 
      queue.length = queueSize; 
    } 
  }; 
 
  function far(x, y) { 
    var i = x / cellSize | 0, 
        j = y / cellSize | 0, 
        i0 = Math.max(i - 2, 0), 
        j0 = Math.max(j - 2, 0), 
        i1 = Math.min(i + 3, gridWidth), 
        j1 = Math.min(j + 3, gridHeight); 
 
    for (j = j0; j < j1; ++j) { 
      var o = j * gridWidth; 
      for (i = i0; i < i1; ++i) { 
        if (s = grid[o + i]) { 
          var s, 
              dx = s[0] - x, 
              dy = s[1] - y; 
          if (dx * dx + dy * dy < radius2) return false; 
        } 
      } 
    } 
 
    return true; 
  } 
 
  function sample(x, y) { 
    var s = [x, y]; 
    queue.push(s); 
    grid[gridWidth * (y / cellSize | 0) + (x / cellSize | 0)] = s; 
    ++sampleSize; 
    ++queueSize; 
    return s; 
  } 
} 
 
</script>