在2D网格上查找最近对象的算法

Question

假设您有一个2D网格,网格上的每个点都有x个对象(x> = 0).我无法考虑干净的算法,因此当用户指定坐标时,算法会找到最近的坐标(包括指定的坐标)与其上的对象.

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

编辑:1的坐标必须是1向上,向下,向左或向右.对角线的坐标是2.

作为旁注,什么是算法的优秀,免费的在线参考？

Answer 1

更新

有了新的信息:

假设对角线的坐标是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);
        }
    }
}

Answer 2

如果你有一个对象列表

如果您拥有列表中所有对象的所有位置,这将更容易,因为您不需要搜索所有空方块并可以执行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)

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

如果你只有一个2D数组

然而,如果所描述的问题假设一个2D数组,其中在没有首先搜索所有对象的情况下无法列出对象的位置,那么您将不得不进行螺旋循环.

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

这是一个关于在2D数组中以螺旋顺序填充值的类似问题.

无论如何,这是我将如何解决这个问题:

给定点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次,您只需要循环外边界值,您不需要重新检查内部值.

哪种方法更快？

这完全取决于:

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

阵列密度

如果你有一个包含2个对象的500x500阵列,那么循环列表将始终优于螺旋

分配技术

如果存在分布模式(IE将对象倾向于彼此聚集),则螺旋可以执行得更快.

对象数量

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

通过计算填充空间的概率,您应该能够计算出最快的解决方案,而列表解决方案每次都必须检查每个对象.

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

Answer 3

如果您的物体很密集，那么搜索附近的点可能是找到距离中心最近的物体的最佳方法。如果对象稀疏，则四叉树或相关的数据结构（R树等）可能更好。这里是一个书面记录举例。

我不知道有什么好的在线算法参考，但是我可以说，如果您编写的代码比偶尔编写的代码多，节省您的钱来购买CLRS将是物有所值的。网上有一些基于本书的讲座，彼得斯·克鲁姆斯（Peteris Krumins）曾为这些讲座作过艰苦的注释，但它们仅涵盖了本书的一部分。这是您需要拥有的几本书籍之一。