ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Serge Kanilo                         2:5020/400     10 May 2001  07:53:54
 To : All
 Subject : Re: Треугольник  наименьшей   площади
 -------------------------------------------------------------------------------- 
 

 
 Hi Andrey,
 
 "Andrey Paniukov" <Andrey.Paniukov@p13.f64.n5054.z2.fidonet.org> wrote in
 message news:989368114@p13.f64.n5054.z2.FIDOnet.ftn...
 
 >  Тогда не знаю отчего и оттолкнуться:((
 
 Самое лобовое решение которое я вижу - это действительно начинать
 с построения охватывающего выпуклого многоугольника. Делаем
 предположение, что одна из сторон искомого треугольника совпадает
 (или содержит) со стороной многоугольника.
 Теперь перебираем остальные вершины, парами, как опоры для двух
 других сторон и для каждой пары решаем задачу минимизации в пределах
 касания сторон треугольника к сторонам многоугольника.
 Таким образом для многоугольника с N вершинами прийдется сделать
 N*(N-2)*(N-3)/2 задач минимизации. А они (на первый взгляд) не очень сложны
 - одна с двумя параметрами и до четырех однопараметрических (когда одна
 из сторон треугольника прилегает к стороне многоугольника).
 Для скорости можно ввести отсекающие критерии (очень часто можно сразу
 сказать, что предел достигается на границе, или что решение невозможно).
 Так что для нескольких сот и возможно тысяч точек это будет решаться за
 вполне пристойное время.
 
 > Я не рпедставляю, как бы я вообще выполнял эту задачу(и без компьютера),
 
 это
 
 > все равно, что ферзей расставять, чтоб они не бились.
 
 Hа обычной 8х8 доске ферзи расставляются ручками без проблем.
 Hо конечно если надо все варианты перебрать и записать ... :)
 
 > Bue Serge!
 
 Bye,
 
 Serge
 --- ifmail v.2.15dev5
  * Origin: Excite@Home - The Leader in Broadband http://home.com/f (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор