Алгоритм для нахождения ближайшего объекта на 2D сетке
Я предпочитаю избегать re, если это возможно:
myString="ThisStringIsCamelCase"
''.join(['_'+i.lower() if i.isupper() else i for i in myString]).lstrip('_')
'this_string_is_camel_case'
4 ответа
Обновление
С новой информацией:
Предполагая, что координата по диагонали находится на расстоянии 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);
}
}
}
Если ваши объекты плотные, то поиск ближайших точек, вероятно, будет лучшим способом найти ближайший объект, выходящий из центра. Если ваши объекты редки, то лучше использовать квадродерево или связанную структуру данных (R-дерево и т. Д.). Вот рецензия с примерами.
Я не знаю хороших ссылок на онлайн-алгоритмы, но могу сказать, что если вы собираетесь писать больше, чем случайную строку кода, экономия ваших копеек на покупку CLRS будет стоить денег , Существуют лекции, основанные на этой книге в Интернете, которые были тщательно аннотированы Петерисом Круминьсом , но они охватывают только часть книги. Это одна из немногих книг, которая вам нужна.
Следующее простое решение предполагает, что вы можете позволить себе хранить дополнительную информацию для каждой ячейки сетки, и что временные затраты на добавление новых объектов в сетку могут быть относительно высокими.
Идея состоит в том, что каждая ячейка содержит ссылку на ближайшую занятую ячейку, что позволяет запросить время O (1). Каждый раз, когда объект добавляется в позицию (i, j), выполните сканирование окружающих ячеек, охватывая кольца увеличивающегося размера. Для каждой сканируемой ячейки оцените текущую ближайшую ссылку на занятую ячейку и при необходимости замените ее. Процесс заканчивается, когда последнее сканированное кольцо вообще не изменяется. В худшем случае процесс сканирует все ячейки сетки, но в конечном итоге становится лучше, когда сетка становится достаточно плотной.
Это решение легко реализовать, оно может иметь значительные накладные расходы на пространство (в зависимости от того, как ваша сетка организована в памяти), но обеспечивает оптимальное время запроса.
Если у вас есть список объектов
Если бы у вас были все позиции всех объектов в списке, это было бы намного проще, поскольку вам не нужно было бы искать по всем пустые квадраты и могут выполнить 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 раз, вам нужно только зациклить внешние граничные значения, вам не нужно повторно проверять внутренние значения.
Какой метод быстрее?
Все зависит от:
- плотности вашего массива
- метода распределения
- количества объектов
плотности массива
если у вас есть массив 500x500 если в нем 2 объекта, то цикл по списку всегда будет лучше, чем по спирали
Метод распределения
Если есть шаблоны распределения (т.е. объекты имеют тенденцию группироваться друг вокруг друга), то спираль может работать быстрее.
Количество объектов
Спираль, вероятно, будет работать быстрее, если существует миллион объектов, поскольку метод списка требует, чтобы вы проверяли и вычисляли каждое расстояние.
Вы должны быть в состоянии вычислить самое быстрое решение, вычислив вероятность заполнения пространства по сравнению с тем фактом, что решение со списком должно проверять каждый объект каждый раз.
Однако, используя технику списка, вы можете выполнить некоторую интеллектуальную сортировку для повышения производительности. Наверное, стоит посмотреть.