Алгоритм поиска ближайшего объекта в 2D сетке

Ответ 1

Udate

С новой информацией:

Предполагая, что координата по диагонали находится на расстоянии 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 + d - i;
        int y2 = ys - 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);
        }
    }
}

Ответ 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-массиве.

В любом случае, вот как я мог бы решить проблему:

С учетом точки 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 с двумя объектами в нем, то цикл списка всегда будет превосходить выполнение спирали

Технология распределения

Если существуют шаблоны распределения (IE объекты стремятся группироваться друг вокруг друга), то спираль может работать быстрее.

Число объектов

Спираль, вероятно, будет работать быстрее, если будет миллион объектов, так как техника списка требует, чтобы вы проверяли и вычисляли каждое расстояние.

Вы должны уметь вычислять самое быстрое решение, вычисляя вероятность заполнения пространства, по сравнению с тем, что решение списка должно проверять каждый объект каждый раз.

Однако, используя технику списка, вы можете выполнить некоторую интеллектуальную сортировку для повышения производительности. Возможно, стоит посмотреть.

Ответ 3

Если ваши объекты плотны, то просто поиск ближайших точек, вероятно, будет лучшим способом найти ближайший объект, вырвавшийся из центра. Если ваши объекты разрежены, то quadtree или соответствующая структура данных (R-дерево и т.д.), Вероятно, лучше. Ниже приведен пример writeup с примерами.

Я не знаю хорошей ссылки на онлайн-алгоритм, но могу сказать, что если вы собираетесь писать больше, чем случайную строку кода, сохраняя свои копейки, чтобы купить CLRS будет стоить денег. Есть лекции, основанные на этой книге в Интернете, которые кропотливо аннотируются "Петерис Крумины" , но они охватывают только часть книги. Это одна из немногих книг, которые вам нужно иметь.

Ответ 4

Следующее простое решение предполагает, что вы можете позволить себе хранить дополнительную информацию в ячейке ячейки и что временная стоимость добавления новых объектов в сетку допускается относительно высокой.

Идея состоит в том, что каждая ячейка содержит ссылку на ближайшую занятую ячейку, что позволяет O (1) время запроса. Всякий раз, когда объект добавляется в позицию (i, j), выполняйте сканирование окружающих ячеек, покрывая кольца увеличивающегося размера. Для каждой проверяемой ячейки оценивайте текущую ближайшую ссылку на занятую ячейку и при необходимости замените ее. Процесс заканчивается, когда последнее проверяемое кольцо не изменяется вообще. В худшем случае процесс сканирует все ячейки сетки, но в конечном итоге становится лучше, когда сетка становится достаточно плотной.

Это решение прост в реализации, может иметь значительные накладные расходы (в зависимости от того, как организована ваша сетка в памяти), но обеспечивает оптимальное время запроса.