Кратчайшее растояние до вершин многоугольника

Автор темы elousiren 
ОбъявленияПоследний пост
ОбъявлениеРаботодателям и кадровым агентствам: Размещение вакансий26.03.2008 03:07
ОбъявлениеЗапущен новый раздел «Задачки и головоломки»29.08.2019 00:42
ОбъявлениеГранты для студентов и аспирантов мехмата и физфака МГУ на обучение в магистратуре Кембриджа 2022/202314.10.2021 12:28
10.04.2012 09:31
Вы не поняли
О переборе и речи нет. Я привел рекурсивную формулу вычисления точки $r^{(k+1)}$ по точке $r^{(k)}$. Строиться последовательность точек $r^{(0)}, r^{(1)}, r^{(2)}, r^{(3)}, ... , $ которая сходится к искомой точке.
11.04.2012 20:08
О.о да я не силен в рядах, последовательностях..
а можно пожайлуста пример четырех вершин со случайными координатами?
11.04.2012 20:18
=)
и будет ли иметь тот же смысл если сделать последовательность k(0)r(0),k(1)r(1),k(3)r(2),k(3)r(3),..., где k - вес точки... свободное число, при решении задачи, которое будет известно..
11.04.2012 21:28
...
1) Пример мне приводить лень. И смысла я в этом не вижу. Уже написанного вполне достаточно для любого, кто хоть что-то помнит из математики. А если нет... Как говорится, если при первом прыжке вам не удалось раскрыть парашют, значит парашютный спорт не для вас.
2) Весовые коэффициенты ничего не усложняют, нужно лишь очевидным образом ввести их в схему вычислений.
12.04.2012 03:59
=\ я сомневаюсь..
Просто при решении данной задачи мне кажется у вас получается не точка от которой суммарное растояние меньшее до всех вершин многоугольника... а точка равноудаленная от всех вершин многоугольника...
12.04.2012 13:58
...
Простите меня пожалуйста, но дальнейшее общение с Вами считаю бессмысленным.
12.04.2012 20:43
Проверка
Решил проверить формулу, предложенную господином vpro . Проверял, конечно, не вручную, а с помощью проги, написанной в Maple. Вот её текст:

P:=proc(L, eps) # L - список вершин многоугольника, eps - точность
local n, ro, r, k;
n:=nops(L);
ro:=(a,b)->sqrt((a[1]-b[1])^2+(a[2]-b[2])^2);
r[-1]:=<infinity, infinity>;
r[0]:=add(L, i=1..n)/n;
for k while is(ro(r[k-2],r[k-1])>=eps) do
r[k]:=evalf(add(L/ro(r[k-1],L),i=1..n)/add(1/ro(r[k-1],L),i=1..n));
od;
print(k-1,evalf(add(ro(r[k-1],L),i=1..n)),convert(r[k-1],list));
end proc:


Процедура возвращает последовательность из 3 объектов (число итераций, минимальное значение целевой функции, координаты точки, реализующей минимум.
Простой модельный пример (с заранее известным ответом) показывает, что всё работает прекрасно! Вершины треугольника лежат на трёх лучах под углом в 120 градусов, выходящих из точки $(1,\,\frac{1}{\sqrt{3}})$:

P([<0,0>, <1,4>, <3,-1/sqrt(3)>], 10^(-10));
52, 6.88675134594814, [1.00000000015971, 0.577350269258044]

В Maple этот же пример легко можно решить встроенной функцией Optimization[Minimize]:

Optimization[Minimize](sqrt(x^2+y^2)+sqrt((x-1)^2+(y-4)^2)+sqrt((x-3)^2+(y+1/sqrt(3))^2));
[6.88675134594812910, [x = 0.999999999991446, y = 0.577350269192024]]

Как видно, результаты практически идентичны.

Формула, предложенная господином vpro , может и не работать, если многоугольник не будет выпуклым. Вот пример:

P([<0,0>, <2,0>, <0,2>, <2,2>, <1,1>], 10^(-10));
Error, (in P) numeric exception: division by zero
12.04.2012 21:20
хм
kitonum, видимо, вы не внимаете моим советам не писать тут ваши бессмысленные коды программ. жаль. впрочем, собой гордиться вы вправе - вон какая большая блямба
12.04.2012 21:44
Re
Уважаемый zklb (Дмитрий) ! Если Вам непонятны какие-нибудь коды, это ещё не значит, что они бессмысленные.
12.04.2012 21:48
А мне с детства нравился не столько поп, сколько попадья.
А мне, наоборот, нравится, что господин kitonum приводит в помощь теории расчеты. Сейчас мало кто может не только гонять монстров по экрану, но и использовать компьютер как вычисляющий инструмент в работе.
12.04.2012 21:51
...
Цитата
kitonum
...
Формула, предложенная господином vpro , может и не работать, если многоугольник не будет выпуклым. Вот пример:
...
Конечно может не работать. Но дело здесь не в выпуклости. Во первых, нужно проверять, не попадаем ли мы в одну из заданных точек, чтобы не было деления на 0. Вы как назло придумали именно такой пример, в котором $r^{(0)}=(1,1)$. Эта точка и является ответом. Чтобы избежать этого нужно ввести еще одно условие остановки: ro(r[0],L)<eps.
Во- вторых, я предложил самую простенькую модификацию метода сжимающих отбражений $r^{(k+1)}=\phi(r^{(k)})$. Для того чтобы это работало, как известно, должны выполняться условия на частные производные правой части $\left| \phi'_x \right|<1, $$\left| \phi'_y \right|<1$. Хорошо бы их проверять и при необходимости нормализовать метод.
Но до таких подробностей здесь дело не дошло. TC, судя по всему, учился уже при Фурсенке...



Редактировалось 2 раз(а). Последний 12.04.2012 21:52.
12.04.2012 22:00
...
И я тоже считаю, что примеры расчетов ув. Kitonum'а совсем не лишние и уж точно не "бессмысленные". Наличие компьютера и программ, позволяющих легко проверить любые построения --- это невероятное благо, которое дала нам современная цивилизация. Я, например, всегда использую эту возможность.
12.04.2012 22:05
хм
да я не против расчетов (если они нужные) - я против кодов программ, наличие которых на матфоруме бессмысленно. а потом мы с вами немало уже видели "расчетчиков", которые удивляются, что у них компьютер неточно считает.
12.04.2012 22:13
...
Понимаете в чем дело, ув. Дмитрий: приведение только результатов расчетов, без самой программы, вот это будет действительно бессмысленным. Это как привести ответ задачи, без выкладок его получения. Принцип верификации в науке рулит.
12.04.2012 22:26
хм
без математических выкладок на математическом формуме)
13.04.2012 06:34
Спасибо...
Спасибо за подробное объяснение смысла формулы... и откуда она взялась..) вы мне очень сильно помогли и упростили жизнь)
13.04.2012 12:07
Согласен со всеми
Цитата

Kitonum
Понимаете в чем дело, ув. Дмитрий: приведение только результатов расчетов, без самой программы, вот это будет действительно бессмысленным. Это как привести ответ задачи, без выкладок его получения. Принцип верификации в науке рулит.
Добавлю к этому, что иногда код программы позволяет определить смысл вычислений, например, когда речь идет о вычислении пределов расходящихся последовательностей, сумм расхожящихся рядов или расходящихся интегралов. Уточняется смысл, в котором имеется сходимость.
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти