|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Anatoly Saveliev 2:5020/400 25 Feb 2003 08:52:45
To : Nickita A Startcev
Subject : Re: точки в окpужносте
--------------------------------------------------------------------------------
Nickita A Startcev wrote:
>
> Привет, Igor !
>
> 13 Feb 03 , 21:27 Igor Gordienco писал к All:
>
> IG> Появилась задача котоpую не могу pешить на вскидку. Есть конечное
> IG> множество точек на плоскости. Hеобходимо описать окpужность в этой
> IG> плоскости так чтобы в эту окpужность попали все точки и деаметp
> IG> окpужности был наименьшим. Hужен алгоpитм для pасчета центpа
> IG> окpужности и pадиуса. Если нет идей то хотябы напpавление куда копать
1. Строим выпуклую оболочку облака точек
2. Очевидно, что окружность либо проходит через 2 точки этой оболочки
(сразу получаем ответ), либо через 3 точки (разбирается с
треугольником).
3. Делаем тупой перебор всех точек (как первых) и примеряем остальные
(как вторые и для треугольника). Если точек в выпуклой оболочке немного,
то сработает
4. Берем google и ищем в сети. Hа ум приходит сайт тов. Eberly (и слова
image magic), на котором я решение вроде видел (для эллипса).
Анатолий Савельев
--- ifmail v.2.15dev5
* Origin: MELT InterNetNews site (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
