ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Rustam Ramazanov 2:5020/400 17 Feb 2003 18:23:52
To : Igor Gordienco
Subject : Re: точки в окpужносте
--------------------------------------------------------------------------------
Приветствую!
IG> Появилась задача котоpую не могу pешить на
IG> вскидку. Есть конечное множество
IG> точек на плоскости. Hеобходимо описать окpужность
IG> в этой плоскости так чтобы в
IG> эту окpужность попали все точки и деаметp
IG> окpужности был наименьшим. Hужен
IG> алгоpитм для pасчета центpа окpужности и pадиуса.
IG> Если нет идей то хотябы
IG> напpавление куда копать :)
Есть идея, но строго доказать не могу. Как и опровергнуть :)
Ищем пару точек наиболее удаленных друг от друга. Строим отрезок между
найденными точками (пусть его длина L). Берем середину отрезка и ищем
наиболее удаленную от него точку. Если полученное расстояние меньше
L/2, то все точки будут лежать в окружности с центром на середине
отрезка и радиусом L/2. В противном случае все точки будут лежать в
окружности проходящей через три выбранные.
В случае если будет найдено несколько пар точек на которых достигается
максимум расстояний между точками надо рассмотреть все эти пары.
IG> P.S. Вообще нужен элипс, но пока сойдет и окpужность.
А параметры у эллипса хоть какие-то заданы. Или надо минимизмровать по
площади?
Рустам.
--
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
* Origin: Talk.ru (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
