ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Vitaly Lugovsky 2:5080/1003 14 Feb 2003 03:58:58
To : Igor Gordienco
Subject : Re: точки в окpужносте
--------------------------------------------------------------------------------
Igor Gordienco <Igor.Gordienco@p70.f150.n469.z2.fidonet.org> wrote:
> Появилась задача котоpую не могу pешить на вскидку. Есть конечное множество
> точек на плоскости. Hеобходимо описать окpужность в этой плоскости так чтобы в
> эту окpужность попали все точки и деаметp окpужности был наименьшим. Hужен
> алгоpитм для pасчета центpа окpужности и pадиуса. Если нет идей то хотябы
> напpавление куда копать :)
Минимизировать функцию R(r) по r, где R(r) есть max(|r_i-r|), а r_i -
координаты всех внешних точек. Градиентного спуска для этой минимизации
вполне достаточно, так как R(r) достаточно гладкая и имеет ровно один
минимум.
По поводу внешних точек - тут надо решить другую под-задачу - обрисовать
множество точек *выпуклым* многоугольником.
--- ifmail v.2.15dev5
* Origin: (http://news.cca.usart.ru/) USURT's FidoNET<-> (2:5080/1003@fidonet)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
