Как найти соседние объекты зная x и y?

Question

[marenco_victor]

Доброго времени суток!
Столкнулся с следующей задачей: есть множество объектов с набором координат (x,y) и есть объект, относительно которого нужно найти ближайшие к примеру 5 объектов из этого множества.
Как или каким алгоритмом лучше решить эту задачу?

Answer 1

[smple]

Необходимо найти расстояние между каждым объектом и целевым.
Расстояние определяется по формуле (легко гуглится) sqrt(sqr(x2 - x1) + sqr(y2 - y1))
Где sqrt - корень квадртаный, sqrстепень в квадрате (2), x1,y1 кооординаты точки(объекта целевого) x2,y2 координаты остальных точек.
Далее отсортировать полученные результаты по возрастанию и результат будет в массиве по порядку с начала.

Comments

[marenco_victor]

Хорошо, тогда вопрос такой по данному алгоритму а если объектов более 100 000. не сильно ли это будет ресурсозатратно?

[d-stream]

marenco_victor: можно поиграться с предварительным (грязным) отбором по "близости" по одной из проекций: типа находим 1000 объектов с минимальной разницей X2-X1, потом 1000 по Y2-Y1 и уже на этой пересечении этих отборов считать корни из суммы квадратов.

[smple]

marenco_victor: 100 000 для компьютера не проблема особенно если язык компилируемый.
вопрос в том в какое время надо уложиться.
Лучше всего взять самый очевидный алгоритм и посмотреть какие результаты он выдает, если не устраивает пытаться оптимизировать и тут уже нужны детали.

[marenco_victor]

smple: спасибо, попробую ваш метод

Answer 2

[Vlad_Fedorenko]

Гляньте в эту сторону https://ru.m.wikipedia.org/wiki/K-мерное_дерево

Comments

[Евгений Шатунов]

В догонку этому полезному ответу: https://habrahabr.ru/post/312882/

Answer 3

[Николай]

Если нужно сделать 1 раз: отсортировать по расстоянию до объекта.
Если много, т.е. для каждого объекта ближайшие - смотрите в сторону алгоритмов кластеризации.

Comments

[marenco_victor]

Вы верно подметили необходимо это для любого объекта из этого набора