algorithm - 一种随机放置圆圈至少相隔 D 距离的算法

Question

我正在尝试编写一种算法，以在任意尺寸的二维矩形中随机放置半径为 R 的圆，这样每个放置的圆与矩形中的其他圆之间的距离至少为 D，

矩形不需要填充，更具体地说，旧的圆圈可能会被破坏，所以我需要能够放置一个新的圆圈，它尊重我已经放置的最后 N 个圆圈的位置(比如5 for eg), 如果不能满足这些条件我可以单独处理。

任何人都可以帮助我如何推导出这样的算法，或者指出一些可能涵盖此的研究吗？

Answer 1

1 Place circle at random location
2 Loop over previous circles
3     if too close
4        delete new circle
5        goto 1
6 if need more circles
7     goto 1

判断是否有空间

Choose resolution required, say delta = D/100
for( x = 0; x < rectangle_size x += delta )
   for( y = 0; y < rectangle_size y += delta )
      unset failed
      loop over circles
           if x,y less than 2D from circle
              set failed
              break from circle loop
       if not failed
            return 'yes there is room'
return 'no, there is no room'

如果你希望有这么多的圈子，以至于只剩下几个洞来容纳新的圈子，那么你可以这样做

clear candidates
Choose resolution required, say delta = D/100
for( x = 0; x < rectangle_size x += delta )
   for( y = 0; y < rectangle_size y += delta )
      unset failed
      loop over circles
           if x,y less than 2D from circle
              set failed
              break from circle loop
       if not failed
            add x,y to candidates
if no candidates
    return 'there is no room'
randomly choose location for new circle from candidates