Алгоритм нахождения ближайшего объекта на 2D сетке

Question

Скажем, у вас есть двумерная сетка, в которой каждая точка на сетке имеет х количество объектов (с х> = 0). У меня возникают проблемы при мыслите алгоритм clean , чтобы, когда пользователь указывает координату, алгоритм находил ближайшую координату (включая указанную) с объектом на ней.

Для простоты будем считать, что если 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)
    }
}

Старая версия

Предполагая, что в вашей двумерной сетке расстояние между (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)

Затем просто выберите тот, у которого кратчайшее расстояние.

Если у вас есть только двумерный массив

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

Поиск ' Спиральный метод поиска ' дает несколько интересных ссылок. Вот некоторый код, который делает спиральный цикл вокруг массива, однако он не работает от произвольной точки и спирали наружу, но должен дать вам хорошие идеи о том, как достичь того, чего вы хотите.

Вот аналогичный вопрос о заполнении значений в спиральном порядке в двумерном массиве.

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

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

Техника распространения

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

Количество объектов

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

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

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

Answer 3

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

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

Answer 4

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

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

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