Доброго времени суток!
Столкнулся с следующей задачей: есть множество объектов с набором координат (x,y) и есть объект, относительно которого нужно найти ближайшие к примеру 5 объектов из этого множества.
Как или каким алгоритмом лучше решить эту задачу?
Необходимо найти расстояние между каждым объектом и целевым.
Расстояние определяется по формуле (легко гуглится) sqrt(sqr(x2 - x1) + sqr(y2 - y1))
Где sqrt - корень квадртаный, sqrстепень в квадрате (2), x1,y1 кооординаты точки(объекта целевого) x2,y2 координаты остальных точек.
Далее отсортировать полученные результаты по возрастанию и результат будет в массиве по порядку с начала.
marenco_victor: можно поиграться с предварительным (грязным) отбором по "близости" по одной из проекций: типа находим 1000 объектов с минимальной разницей X2-X1, потом 1000 по Y2-Y1 и уже на этой пересечении этих отборов считать корни из суммы квадратов.
marenco_victor: 100 000 для компьютера не проблема особенно если язык компилируемый.
вопрос в том в какое время надо уложиться.
Лучше всего взять самый очевидный алгоритм и посмотреть какие результаты он выдает, если не устраивает пытаться оптимизировать и тут уже нужны детали.
Если нужно сделать 1 раз: отсортировать по расстоянию до объекта.
Если много, т.е. для каждого объекта ближайшие - смотрите в сторону алгоритмов кластеризации.
Средний