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

问题描述

假设有一个2D网格每个点上的对象的网格的x号（其中x> = 0）。我无法想了的清洁的算法，这样，当用户指定一个坐标，算法查找最接近的坐标（包括指定的那一个）与在其上的对象。

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?

推荐答案

UDATE

使用新的信息：

假设一个坐标斜   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 + d - i;
        int y2 = ys - 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屋！