Алгоритм

← →
777 (2003-08-13 22:27) [0]

Доброго времени суток,
у меня след. проблема: есть группа точек
(например [2,2],[4,4],[8,8],[10,10],[15,15]), вопрос : как можно найти точку, отдаленную от всех этих на одинаковое
(минимально различное) расстояние?
может есть где-то стандартное решение?
Подскажите пожалуйста.

← →
Романов Р.В. (2003-08-13 22:45) [1]

Ищи минимум суммы всех расстояний до неизвестной точки. В точке минимума функции ее производная изменяет знак.
Простейший способ: Проходи по оси х в цикле от мин(X) до макс(Х).
Или поищи алгоритмы нахождения минимума функции

← →
777 (2003-08-13 22:56) [2]

> Романов Р.В. © (13.08.03 22:45) [1]

Спасибо, попробую...

← →
Dionys (2003-08-13 23:29) [3]

а по моему нужно искать решение задачи вида:
F(x,y) = Summ{i=1,n}((n-1)Sqrt((x-x[i])^2+(y-y[i])^2)-Summ{j=1,n;j<>i}(Sqrt((x- x[j])^2+(y-y[j])^2))) -> min
довольно непростая задача из методов оптимизации...

← →
3APA3A (2003-08-13 23:58) [4]

Попробуй найти координаты центра масс этой системы.

x-координата = (x1+x2+...+xn)/n;
y-координата - соответственно....

← →
3APA3A (2003-08-14 00:01) [5]

Правильнее всего найти функцию F(x,y) - сумма расстояний от точки с координатами (x,y) до известных точек и найти ее минимум... Это несложно... Скорее всего и получится то что я сказал выше... Но сам не проверял...

← →
Marser (2003-08-14 01:26) [6]

На самом деле все проще. Из личного опыта, проверенное:
type
tvert=array[1..20] of tpoint;
procedure center(v:tvert;n:byte;var c:tpoint);
var i:byte;x,y:real;
begin
x:=0;y:=0;
for i:=1 to n do
begin
x:=x+v[i].x/n;
y:=y+v[i].y/n
end;
c.x:=x;
c.y:=y
end;

← →
3APA3A (2003-08-14 02:22) [7]

И чем [6] отличается от [4]???

← →
SergP (2003-08-14 04:13) [8]

1. как можно найти точку, отдаленную от всех этих на одинаковое
(минимально различное) расстояние?

2. Ищи минимум суммы всех расстояний до неизвестной точки.

ИМХО это разные вещи.

Насчет первого то получается что искомая точка должна быть удалена подальше от заданных (в бесконечность) в данном примере.
Ведь вопрос ставится чтобы расстояния наименее отличались друг от друга а не чтобы сумма расстояний была минимальной.

← →
Dionys (2003-08-14 07:12) [9]

задача не имеет решения если хотя бы три точки расположены на одной прямой... так как тогда (как заметил SergP) искомая точка будет находиться в бесконечности...

← →
Bel (2003-08-14 09:41) [10]

> Dionys (14.08.03 07:12) [9]

Более того, задача имеет решение только в случае, когда все точки расположены на одной окружности.
Или я чего-то не понял в условии задачи?

← →
HolACost! (2003-08-14 10:04) [11]

Я бы сказал не на окружности, а на дуге окружности, ктотторая может быть до 2-х пи!

← →
Jeer (2003-08-14 10:32) [12]

Надо уточнить: это новая точка или точка из существующих.

← →
777 (2003-08-14 10:42) [13]

> Jeer © (14.08.03 10:32) [12]

Это новая точка.

> HolACost! © (14.08.03 10:04) [11]

Точки расположены на дуге,
просто я пример привел такой.....

← →
Jeer (2003-08-14 10:51) [14]

Тогда это РАДИУС:))
Достаточно трех точек

← →
HolACost! (2003-08-14 11:02) [15]

Но возможен вариант, что эти точки не на дуге? то придётся пробивать все тройки - вернее тройки. чтобы каждая (.) была хоть один раз в какой-нить тройке!

← →
Jeer (2003-08-14 11:10) [16]

Не вполне понятна задача, поэтому и гадание.
Если теоретически д.б. дана дуга, а практически наблюдаются
ошибки (отклонения) - тогда решение методом наименьших квадратов
для Гауссового распределения.

← →
777 (2003-08-14 11:44) [17]

← →
Jeer (2003-08-14 12:00) [18]

Это меня уже спрашивают ?:)
Вам виднее, что - надо.

Алгоритм Найти похожие ветки