Как найти ближайшие точки на координатной плоскости?

Question

[dyrtage]

Есть координатная плоскость 10 на 10. На ней расположены рандомным образом точки. Их координаты могут быть: (1, 3); (4, 2) и т.п. Допустим есть точка с координатами (4, 5). Как найти ближайшее к нему 3 точки?

Comments

[Lynn «Кофеман»]

Перебрать все точки. Посчитать расстояние. Выбрать три с минимальным расстоянием.

В чём проблема?

[dyrtage]

Lynn «Кофеман», думаю есть алгоритмы, которые будут работать быстрее, т.к. мне в данной ситуации важна скорость

Answer 1

[Vindicar]

Координаты строго целочисленные?
Тогда обходи точки с помощью алгоритма floodfill, с центром в исходной точке.
Например, для небольшого участка порядок будет таким:

5 4 3 4 5
4 2 1 2 4
3 1 X 1 3
4 2 1 2 4
5 4 3 4 5

Цифра - на какой итерации проверяются эти позиции.
Т.е. сначала проверяешь соседние с исходной, потом соседние с ними, потом соседние с теми, и так далее.
Если в позиции есть точка, добавляешь её в список найденных. Когда в списке найденных набралось 3 точки, останавливаешься.

Comments

[dyrtage]

хм, интересное решение. Попробую сделать через нее

[Alexandroppolus]

Флудфил эффективнее построчным способом (делал когда-то, сначала так, потом построчно, скорость заметно разная).
А то что здесь - это "волновой алгоритм" (искать по такому названию). Для задачи подходит, в самый раз - при условии, что у автора действительно двумерный булевский массив, а не список всех точек отдельным массивом.

[dyrtage]

Alexandroppolus, нашел куча статей по этому запросу. Полностью все не читал, но по скринам вижу, что схожая задача. Спасибо вам)

Answer 2

[dmshar]

Не понимаю, зачем обходить точки для решения задачи?
Предположим, у вас поле не 10х10, а 100х100. А точек - 5. Вопрос: Сколько клеток вам надо обойти, что-бы найти оптимальную точку? Правильный ответ - 100х100-1.
А теперь вспоминаем школьную математику. Расстояние между двумя точками "a" и "b" в двумерном пространстве определяется как sqrt(Xa-Xb)**2 +(Ya-Yb)**2).
Все. Есть пять точек. Для каждой из них вычисляем расстояние до нашей точки и отбираем три (или сколько надо) для которых эти расстояния наименьшие.
Даже на небольшой доске 10х10 и - предположим - 10 точках выигрыш прямого решения против последовательного обхода всех 99 точек очевиден.
P.S. Ни к Python, ни к JavaScript эта задача не имеет отношения от слова совсем.