Учитывая n точек на двумерной плоскости, какая точка такая, что расстояние от всех точек минимизировано? Эта точка не обязательно должна быть из множества заданных точек. Это центроид или что-то еще?Поиск ближайшей точки из множества точек на плоскости
Как найти все такие точки (если более одного) с помощью алгоритма?
Это известно как «Центр расстояния» и отличается от центра тяжести.
Во-первых, вы должны определить, какую меру расстояния вы используете. Если предположить, что вы используете стандартную метрику d = sqrt ((x1-x2)^2 + (y1-y2)^2), то она не является единственной, и проблема сводит к минимуму эту сумму.
Самый простой пример, чтобы показать этот ответ, не является уникальным примером прямой линии. Любая точка между двумя точками имеет равное полное расстояние от всех точек.
В 1D правильным ответом будет любой ответ с таким же количеством точек справа и слева. Пока это верно, тогда любое перемещение влево и вправо будет увеличиваться и уменьшать левую и правую стороны на одну и ту же величину и, таким образом, оставлять расстояние одинаковым. Это также доказывает, что центроид не обязательно правильный ответ.
Если мы перейдем к 2D, это уже не так, поскольку sqrt делает проблему взвешенной. Удивительно, но, похоже, не стандартный алгоритм! На странице here, похоже, используется метод грубой силы. Я этого никогда не знал!
Если бы я хотел использовать алгоритм, то я бы нашел медианную точку в X и Y в качестве начальной точки, а затем использовал gradient descent algorithm - это получило бы ответ довольно быстро. Все уравнение заканчивается квадратичным, поэтому кажется, что должно быть точное решение.
Не работает ли алгоритм грубой силы в вашей первой ссылке для точек на сфере? –
Нет, я сказал градиентный спуск для n очков. Напишите свою функцию подсчета очков так, чтобы она рассчитала общее расстояние до всех n точек, а затем уменьшила эту функцию спуска. Я не собираюсь добавлять код в случае, если это домашнее задание, его должно быть легко написать. –
@ Matthijs, вполне возможно, я не выглядел слишком тяжело. Спасибо за указание. Это интересный вопрос, не так ли. –
Может быть более одного пункта. Рассмотрим плоскость с двумя точками на ней. Эти точки описывают линейный сегмент. Любая точка этого сегмента линии будет иметь такое же полное расстояние от двух конечных точек.
Итак, как найти все такие точки с помощью алгоритма? – nowonder
На самом деле ответ будет простым полигоном. Причина в том, что сумма выпуклых функций (например, функция расстояния) также выпукла. Вероятно, вы можете найти его точные координаты, начиная с треугольника и добавляя точки. Однако делать это наивно было бы «n^2». –
Грубая сила алго. может дать вам наилучшие результаты. Во-первых, найдите прямоугольник/любой четырехугольник, ограничивающий входные точки. Наконец, для каждой точки внутри прямоугольника вычислите расстояние от других точек. Суммируйте расстояния точки от входного набора. Скажите, что это «стоимость» точки. Повторите для каждой точки и выберите точку с мин. Стоимость.
Интеллект также может быть добавлен в алгоритм. он может устранить области, основанные на средней стоимости и т. д.
Вот как я подойду к проблеме хотя бы ... надеюсь, что это поможет.
Но у него очень высокая сложность. Проверяя каждую точку внутри прямоугольника, как это сделать, координаты точки могут быть любым числом с плавающей запятой. – nowonder
ну, очевидно, вам нужен какой-то размер шага, минимальное расстояние между двумя последовательными точками, простой пример с использованием C может быть: для (int row = minR; row
Это подробно обсуждается здесь http://www.ddj.com/architect/184405252?pgno=1
Это было интересно, но решает другую проблему. Вопроситель задал точку, которая сводит к минимуму расстояние до всех точек. В статье DDJ обнаружены две точки, наиболее близкие друг другу. –
Не закрывайте это, алгоритмы геометрии полностью в пределах переполнения стека –
ли это домашнее задание? Кроме того, на каком языке вы пытаетесь это реализовать? – Piskvor
Нет, это не домашнее задание. Я изучаю алгоритмы вычислительной геометрии. Так что получил сомнение. Я делаю это в C. – nowonder