26

假设您有一个 2D 网格，网格上的每个点都有 x 个对象（x >=0）。我在想一个干净的算法时遇到了麻烦，这样当用户指定一个坐标时，算法会找到最接近的坐标（包括指定的坐标），上面有一个对象。

为简单起见，我们假设如果 2 个坐标距离相同，则将返回第一个坐标（或者如果您的算法不能以这种方式工作，那么最后一个坐标无关紧要）。

编辑：距离为 1 的坐标必须是上、下、左或右 1。对角线远离的坐标是 2。

附带说明一下，什么是出色的免费在线算法参考？

4

5 回答 5

18

更新

有了新信息：

假设一个坐标对角线距离为 2

该算法将起作用。该算法以一种螺旋方式向外搜索，测试从内部开始的每个“环”中的每个点。

请注意，它不处理越界情况。所以你应该改变它以满足你的需要。

int xs, ys; // Start coordinates

// Check point (xs, ys)

for (int d = 1; d<maxDistance; d++)
{
    for (int i = 0; i < d + 1; i++)
    {
        int x1 = xs - d + i;
        int y1 = ys - i;

        // Check point (x1, y1)

        int x2 = xs + d - i;
        int y2 = ys + i;

        // Check point (x2, y2)
    }


    for (int i = 1; i < d; i++)
    {
        int x1 = xs - i;
        int y1 = ys + d - i;

        // Check point (x1, y1)

        int x2 = xs + i;
        int y2 = ys - d + i;

        // Check point (x2, y2)
    }
}

旧版

假设在您的 2D 网格中，(0, 0) 和 (1, 0) 之间的距离与 (0, 0) 和 (1, 1) 之间的距离相同。该算法将起作用。该算法以一种螺旋方式向外搜索，测试从内部开始的每个“环”中的每个点。

请注意，它不处理越界情况。所以你应该改变它以满足你的需要。

int xs, ys; // Start coordinates

if (CheckPoint(xs, ys) == true)
{
    return (xs, ys);
}

for (int d = 0; d<maxDistance; d++)
{
    for (int x = xs-d; x < xs+d+1; x++)
    {
        // Point to check: (x, ys - d) and (x, ys + d) 
        if (CheckPoint(x, ys - d) == true)
        {
            return (x, ys - d);
        }

        if (CheckPoint(x, ys + d) == true)
        {
            return (x, ys - d);
        }
    }

    for (int y = ys-d+1; y < ys+d; y++)
    {
        // Point to check = (xs - d, y) and (xs + d, y) 
        if (CheckPoint(x, ys - d) == true)
        {
            return (xs - d, y);
        }

        if (CheckPoint(x, ys + d) == true)
        {
            return (xs - d, y);
        }
    }
}
于 2010-07-25T17:36:14.500 回答
13

如果你有一个对象列表

如果你有一个列表中所有对象的所有位置，这会容易得多，因为你不需要搜索所有的空方块，并且可以执行2D 距离计算来确定离你最近的那个。遍历您的对象列表并计算距离，如下所示：

Define your two points. Point 1 at (x1, y1) and Point 2 at (x2, y2).

    xd = x2-x1
    yd = y2-y1
    Distance = SquareRoot(xd*xd + yd*yd)

然后只需选择距离最短的那个。

如果你只有一个二维数组

但是，如果所描述的问题假设一个二维数组，其中如果不首先搜索所有对象就无法列出对象的位置，那么您将不得不进行螺旋循环。

搜索“螺旋搜索法”会出现一些有趣的链接。 这是一些围绕数组进行螺旋循环的代码，但这不能从任意点向外螺旋，但应该给你一些关于如何实现你想要的好主意。

这是关于在二维数组中以螺旋顺序填充值的类似问题。

无论如何，这是我将如何解决这个问题：

给定点P，创建一个向量对，指定周围的区域P。

所以如果P = 4,4 那么你的向量对将是3,3|5,5

在这些范围内循环每个值。

for x = 3 to 5
    for y = 3 to 5
        check(x,y)
    next
next

如果找到值，则退出。如果不是，请再次将界限增加一倍。所以在这种情况下，我们会去 2,2|6,6

在循环检查值时，确保我们没有进入任何负索引，并确保我们没有超过数组的大小。

此外，如果将边界扩展 n 次，则只需循环外部边界值，无需重新检查内部值。

哪种方法更快？

这一切都取决于：

  • 阵列的密度
  • 分配技术
  • 对象数

阵列密度

如果你有一个 500x500 的数组，里面有 2 个对象，那么循环列表总是会优于做螺旋

分配技术

如果存在分布模式（即对象倾向于彼此聚集），那么螺旋可能会执行得更快。

对象数

如果有一百万个对象，螺旋可能会执行得更快，因为列表技术要求您检查和计算每个距离。

与列表解决方案每次都必须检查每个对象的事实相比，您应该能够通过计算空间被填充的概率来计算最快的解决方案。

但是，使用列表技术，您也许可以进行一些智能排序以提高性能。这可能值得研究。

于 2010-07-25T17:21:56.197 回答
5

如果您的对象很密集，那么仅搜索附近的点可能是找到最近的对象的最佳方法，从中心向外盘旋。如果您的对象是稀疏的，那么四叉树或相关数据结构（R-tree 等）可能会更好。这是带有示例的文章。

我不知道有什么好的在线算法参考，但我可以说，如果你要写的不仅仅是偶尔的一行代码，那么省下你买CLRS的钱是值得的。网上有基于这本书的讲座，由Peteris Krumins精心注释，但它们只涵盖了本书的一部分。这是您需要拥有的少数几本书之一。

于 2010-07-25T17:27:38.153 回答
3

以下简单的解决方案假设您可以负担每个网格单元存储额外信息的费用，并且允许将新对象添加到网格的时间成本相对较高。

这个想法是每个单元格都保存对最近占用单元格的引用，从而允许 O(1) 查询时间。每当将对象添加到位置 (i,j) 时，对周围的单元格进行扫描，覆盖大小增加的环。对于正在扫描的每个单元格，评估其当前最近占用的单元格引用，并在必要时替换它。当被扫描的最后一个环完全没有被修改时，该过程结束。在最坏的情况下，该过程会扫描所有网格单元，但最终当网格变得足够密集时会变得更好。

此解决方案易于实现，可能有很大的空间开销（取决于您的网格在内存中的组织方式），但提供了最佳查询时间。

于 2010-07-25T17:54:34.367 回答
-1

从 4 个方向的起始坐标开始的简单 BFS 足以找到网格上与对象最近的点。

于 2021-08-22T02:04:34.227 回答