algorithm - 在半径增加的二维网格中查找相邻单元格

Question

假设有一个二维网格，其中 X 是要检查的单元格，T 是满足给定单元格 X 的检查标准的单元格。

+---+---+---+---+---+
| T |   |   |   |   |
+---+---+---+---+---+
|   |   |   |   |   |
+---+---+---+---+---+
|   |   | X |   |   |
+---+---+---+---+---+
|   |   |   |   |   |
+---+---+---+---+---+
|   |   |   |   |   |
+---+---+---+---+---+

现在我想通过以下方式搜索来找到最接近 X 且满足条件(本例中为 T)的单元格，其中数字表示要检查的单元格按升序排列:

+---+---+---+---+---+
| 11|   |   |   |   |
+---+---+---+---+---+
| 10| 1 | 2 | 3 |   |
+---+---+---+---+---+
| 9 | 0 | X | 4 |   |
+---+---+---+---+---+
| 8 | 7 | 6 | 5 |   |
+---+---+---+---+---+
|   |   |   |   |   |
+---+---+---+---+---+

硬编码 X-Cell 偏移量的简单方法行不通，因为 T 和 X 之间的距离是任意的。那么，如果没有前一种方法，我该如何实现呢？

Answer 1

还没有指定半径的测试，上面的循环没有标记任何东西，它只是填充一个正方形。 “半径”一词仅适用于圆形区域。

如果您想枚举位于圆内或附近的点，您可以使用欧氏距离:

• 在 float 域中:currentRadius * currentRadius 作为条件并相应地乘以 X * X + Y * Y

• 在整数域中:Bresenham 圆，引用 https://www.geeksforgeeks.org/bresenhams-circle-drawing-algorithm/连接水平填充

第二个选项是最快的——我在过去的好日子里用过它——你会更快地找到点..但它给你留下了象限和边界问题，如果你存储点，运行时从整数中获得 yield 比较将是无关紧要的。

现在，我会使用第一个选项。对于相对较小的网格，使用循环，添加 R * R > V 的测试，其中 V 是 X 和 T 之间的欧几里得距离的平方，即 V = (T.X-X) * (T.X-X) + (T.Y-Y ) * (T.Y-Y) 对于每个点。