在二维网格上寻找最近​​对象的算法 [英] Algorithm for finding nearest object on 2D grid

问题描述

假设您有一个 2D 网格，网格上的每个点都有 x 个对象(x >=0).我在考虑 clean 算法时遇到了麻烦，因此当用户指定坐标时，该算法会找到最近的坐标(包括指定的坐标)，上面有一个对象.

Say you have a 2D grid with each spot on the grid having x number of objects (with x >=0). I am having trouble thinking of a clean algorithm so that when a user specifies a coordinate, the algorithm finds the closest coordinate (including the one specified) with an object on it.

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

For simplicity's sake, we'll assume that if 2 coordinates are the same distance away the first one will be returned (or if your algorithm doesn't work this way then the last one, doesn't matter).

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

A coordinate that is 1 away must be either 1 up, down, left or right. Coordinates that are away diagonally are 2.

顺便提一下，什么是很棒的免费在线算法参考?

As a side note, what is a great, free, online reference for algorithms?

推荐答案

更新

有新信息:

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

Assuming that a coordinate diagonally is 2 away

这个算法会起作用.该算法以螺旋式向外搜索，有点像从内部开始测试每个环"中的每个点.

This algorithm would work. The algorithm searches outwards in a spiral kinda way testing each point in each 'ring' started from the inside.

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

Note that it does not handle out of bounds situations. So you should change this to fit your needs.

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) 相同.这个算法会起作用.该算法以螺旋式向外搜索，有点像从内部开始测试每个环"中的每个点.

Assuming that in your 2D grid the distance between (0, 0) and (1, 0) is the same as (0, 0) and (1, 1). This algorithm would work. The algorithm searches outwards in a spiral kinda way testing each point in each 'ring' started from the inside.

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

Note that it does not handle out of bounds situations. So you should change this to fit your needs.

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);
        }
    }
}

这篇关于在二维网格上寻找最近​​对象的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！