algorithm - 热衷于寻找网格上最近的自由点

Question

想象一个简单的 2D 网格；网格上的对象可以占据多个单元格(但点总是连接的)。考虑以下示例，其中我使用字母 A 和 B 只是为了区分对象(这很有用，因为对象可能彼此靠近放置):

0 1 2 3 4 5 6 7 8 9 10
1 . . . . . . . . . .
2 . . . . . . . . . .
3 . . . A . . . . . .
4 . . A A A . . B B .
5 . . . A . . . B B .
6 . . . . . . . . . .

我需要一种插入新对象的算法，将它们定位在网格上并确保它们不重叠。因此，如果我想嵌入一个新对象(用 C 表示)并且其任何单元格的坐标已被占用，则算法应该找到最近的空闲区域(即点列表) )来分配新对象。让我们尝试将对象 C 插入到坐标 (4, 3) 处，该坐标已被 A 中的单元格占据:

0 1 2 3 4 5 6 7 8 9 10
1 . . . . . . . . . .
2 . C C . . . . . . .
3 . C C A . . . . . .
4 . . A A A . . B B .
5 . . . A . . . B B .
6 . . . . . . . . . .

如您所见，对象已移动到靠近对象 A 的位置。我假设搜索应该围绕被占用的单元格开始，顺序如下(按方向给出):N、E、S、W，然后在中间方向:NE、SE 等。

您建议如何实现该算法？

更新:对象位置是左上角。 最近点是根据初始请求位置与周围自由点之间的距离计算得出的。

Answer 1

您想要按照距离增加的顺序迭代可能的位移(即移位)。由于所有位移都是整数，因此位移的平方需要为 sums of two squares 。以下 python 代码跟踪每个 x 位移的下一个可能的 y 位移。它生成对列表。每对表示位移坐标。单个列表中的所有元素距原点的距离相同，而后面列表中的元素将具有更大的距离。因此，以什么顺序遍历内部列表并不重要，至少在距离方面是这样。您甚至可能想要随机化它们。

def iter_distance(maxr = 10):
    r = 0
    d = [0]
    while r <= maxr:
        m = maxr*maxr + 1
        for x, y in enumerate(d):
            sq = x*x + y*y
            if sq < m:
                m = sq
                b = []
            if sq == m:
                b.append((x, y))
        for x, y in b:
            d[x] = y + 1
        if b[-1][0] == r:
            r += 1
            d.append(0)
        yield (b +
               [(x, -y) for x, y in b if y] +
               [(-x, y) for x, y in b if x] +
               [(-x, -y) for x, y in b if x*y])

for lst in iter_distance():
    marker = '*'
    for x, y in lst:
        print("{:5} {:5} {:10} {}".format(x, y, x*x + y*y, marker))
        marker = ' '

第一行输出如下所示:

    0     0          0 *
    0     1          1 *
    1     0          1  
    0    -1          1  
   -1     0          1  
    1     1          2 *
    1    -1          2  
   -1     1          2  
   -1    -1          2  
    0     2          4 *
    2     0          4  
    0    -2          4  
   -2     0          4  
    1     2          5 *
    2     1          5  
    1    -2          5  
    2    -1          5  
   -1     2          5  
   -2     1          5  
   -1    -2          5  
   -2    -1          5  
    2     2          8 *
    2    -2          8  
   -2     2          8  
   -2    -2          8  
    0     3          9 *
    3     0          9  
    0    -3          9  
   -3     0          9  

对于最大 400 的距离(即传递 400 作为 maxr 参数)，您将获得 37,556 个不同距离的 502,625 行，因此您希望动态生成这些，而不是硬编码将它们添加到应用程序中。不过，您可以使用这些数字来检查您的实现情况，以防我们中的一个人犯了错误。

如果关心性能，可以使用优先级队列代替数组，这样写:

#include <queue>
#include <utility>
#include <cmath>
#include <iostream>
#include <iomanip>

class displacement {
private:
  int _d;
  int _x;
  int _y;
public:
  displacement() : _d(0), _x(0), _y(0) {}
  displacement(int x, int y) : _d(x*x + y*y), _x(x), _y(y) {}
  int x() const { return _x; }
  int y() const { return _y; }
  int sqd() const { return _d; }
  bool operator<(const displacement& d) const { return sqd() > d.sqd(); }
};

static void print2(int x, int y, int sqd) {
  std::cout << std::setw(10) << x << ' '
            << std::setw(10) << y << ' '
            << std::setw(20) << sqd << ' '
            << std::endl;
}

static void print1(int x, int y, int sqd) {
  print2(x, y, sqd);
  if (y)
    print2(x, -y, sqd);
  if (x) {
    print2(-x, y, sqd);
    if (y)
      print2(-x, -y, sqd);
  }
}

int main(int argc, char** argv) {
  int maxr = 400;
  int maxrsq = maxr*maxr;
  std::priority_queue<displacement> q;
  q.push(displacement(0, 0));
  while (q.top().sqd() <= maxrsq) {
    const displacement& d = q.top();
    int x = d.x();
    int y = d.y();
    int sqd = d.sqd();
    print1(x, y, sqd);
    q.pop();
    q.push(displacement(x, y + 1));
    if (x == y) {
      q.push(displacement(x + 1, y + 1));
    }
    else {
      print1(y, x, sqd);
    }
  }
}

在这种情况下，队列包含单独的位移，结果将以任意(可能是实现定义的)顺序打印相同距离的单独位移，而不将它们收集到列表中。仅立即打印给定位移的镜像。这里的代码采用了完全的8重对称，因此任何时候队列中存储的元素数量甚至小于到目前为止生成的最大距离，除了最开始的时候。