在2D网格上寻找最近物体的算法

Question

在2D网格上寻找最近物体的算法

algorithm2dmultidimensional-arraycoordinate-systems

26

假设你有一个二维网格，网格上的每个位置都有x个物体（其中x> = 0）。我在考虑一种简洁的算法，使得当用户指定一个坐标时，该算法能够找到最接近的带有物体的坐标（包括指定的坐标）。

为了简单起见，我们假设如果两个坐标的距离相同，则返回第一个（或者如果您的算法不按此方式工作，则返回最后一个，没有关系）。

编辑：距离为1的坐标必须是向上、下、左或右移动一步。斜着移动的坐标距离为2。

另外，有哪些优秀的免费在线算法参考资料？

- random

5

附注：您所描述的距离测量通常被称为“曼哈顿距离”，或更数学化地称为L1距离。 - Thomas

5个回答

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)

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

如果您只有一个二维数组

然而，如果问题描述假设一个二维数组，其中对象的位置不能列出而不首先搜索所有对象，则必须进行螺旋循环。

搜索“Spiral Search Method”会出现一些有趣的链接。这里是一些执行数组螺旋循环的代码，但这不能从任意点开始并向外螺旋，但应该为您提供如何实现所需内容的一些好主意。

这里有一个类似的问题，关于在二维数组中以螺旋顺序填充值。

无论如何，这是我解决问题的方法：

给定点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个对象，则循环列表将始终优于执行螺旋。

分布技术：如果存在分布模式（即对象倾向于聚集在一起），则螺旋可能会更快。

对象数量：如果有一百万个对象，则螺旋可能会更快，因为列表技术要求您检查并计算每个距离。

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

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

- Tom Gullen

我确实有所有对象的位置，但这有什么帮助呢？ - random

因为你可以遍历整个对象列表，计算该对象与起点之间的距离，并找到最短的距离。经过更深思考，如果速度很重要，这可能并不总是最快的解决方案，这取决于您的搜索空间有多大。但它比外部螺旋算法简单得多。 - Tom Gullen

是的，那就是我一开始所做的。现在我有了一个通过网格表示的表达方式，我认为利用它的方法可能会更快。（速度很重要） - random

我已经为您添加了关于速度的简短段落。 - Tom Gullen

@random：如果查询性能很重要，请考虑我的解决方案。是否可以按照我建议的修改网格数据结构？ - Eyal Schneider

这是一个很棒的回答，但我不得不查看Martin的回答，因为他写出了我正在寻找的算法。然而，这让我意识到，我可能最好同时使用螺旋和列表搜索，根据情况选择其中之一。谢谢！ - random

5

如果您的对象是密集的，那么从中心开始向外螺旋搜索附近的点可能是找到最近对象的最佳方法。如果您的对象是稀疏的，则四叉树或相关数据结构（R树等）可能更好。这里有一个写作带有例子。

我不知道有什么好的在线算法参考资料，但我可以说，如果您要编写超过偶尔的一行代码，则节省购买CLRS将是值得的。基于该书的讲座已经被Peteris Krumins注释了，但它们只涵盖了该书的一部分。这是您需要拥有的少数几本书之一。

- deinst

3

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

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

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

- Eyal Schneider

这是一个非常酷的解决方案，它在添加对象时进行搜索，而不是在尝试获取最近对象时进行搜索。然而，添加对象比尝试获取最近对象更常见，并且添加对象的性能同样重要，甚至更重要（取决于与问题无关的其他因素）。 - random

-1

一个简单的BFS从起始坐标开始，沿着4个方向寻找最接近对象的网格点就足够了。

- Surya Singh

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Martin Ingvar Kofoed Jensen · Accepted Answer

更新

根据最新的信息：

假设两个坐标之间的对角线距离为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);
        }
    }
}