Нахождение самой близкой точки от ряда точек на плоскости
Или Consolas (загрузка) или Andale Mono (загрузка) . Я главным образом использую Andale Mono. Я написал статью о программировании шрифтов давным-давно , я думаю, что Consolas не был, выравниваются все же.
http://www.deadprogrammer.com/photos/fonts.gif
я нахожу, что ввод Illegal1 = O0 является хорошим тестом пригодности.
4 ответа
Это известно как «Центр расстояния» и отличается от центроида.
Во-первых, вы должны определить, какую меру расстояния вы используете. Если предположить, что вы используете стандартную метрику d = sqrt ((x1-x2) ^ 2 + (y1-y2) ^ 2), тогда она не уникальна, и проблема заключается в минимизации этой суммы.
Самый простой пример показать, что этот ответ не является уникальным, - это пример прямой линии. Любая точка между двумя точками имеет одинаковое общее расстояние от всех точек.
В 1D правильным ответом будет любой ответ, который имеет одинаковое количество точек справа и слева. Пока это верно, любое движение влево и вправо будет увеличивать и уменьшать левую и правую стороны на одинаковую величину, и поэтому расстояние остается неизменным. Это также доказывает, что центроид не обязательно является правильным ответом.
Если мы расширим до 2D, это уже не так - sqrt делает проблему взвешенной. На мой взгляд, стандартного алгоритма не существует! Страница здесь , кажется, использует метод грубой силы. Я никогда этого не знал!
Если бы я хотел использовать алгоритм, я бы нашел среднюю точку по X и Y в качестве начальной точки, а затем использовал бы алгоритм градиентного спуска - это даст ответ довольно быстро. Все уравнение оказывается квадратичным, поэтому кажется, что должно быть точное решение.
затем я бы нашел среднюю точку в X и Y как начальную точку, затем использовал бы алгоритм градиентного спуска - это довольно быстро дало бы ответ. Все уравнение оказывается квадратичным, поэтому кажется, что должно быть точное решение. затем я бы нашел среднюю точку в X и Y в качестве начальной точки, затем использовал бы алгоритм градиентного спуска - это довольно быстро дало бы ответ. Все уравнение оказывается квадратичным, поэтому кажется, что должно быть точное решение.Может быть более одной точки. Рассмотрим плоскость, на которой всего две точки. Эти точки описывают отрезок прямой. Любая точка на этом отрезке линии будет иметь одинаковое общее расстояние от двух конечных точек.
Алгоритм перебора. может дать вам лучшие результаты. Во-первых, найдите прямоугольник / любой четырехугольник, ограничивающий входные точки. Наконец, для каждой точки внутри прямоугольника рассчитать расстояние от других точек. Суммируйте расстояния от точки до входного набора. Скажите, что это «стоимость» точки. Повторите для каждой точки и выберите точку с мин. стоимость.
К алгоритму также можно добавить интеллект. он может исключить области, исходя из средней стоимости и т. д.
По крайней мере, так я бы подошел к проблеме ... надеюсь, это поможет.
Это подробно обсуждается здесь http://www.ddj.com/architect/184405252?pgno=1