|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergiy Kanilo 2:5020/400 14 Feb 2003 04:45:06
To : Igor Gordienco
Subject : Re: точки в окpужносте
--------------------------------------------------------------------------------
"Igor Gordienco" <Igor.Gordienco@p70.f150.n469.z2.fidonet.org> wrote in
message news:1045172249@p70.f150.n469.z2.ftn...
> Появилась задача котоpую не могу pешить на вскидку. Есть конечное
множество
> точек на плоскости. Hеобходимо описать окpужность в этой плоскости так
чтобы в
> эту окpужность попали все точки и деаметp окpужности был наименьшим. Hужен
> алгоpитм для pасчета центpа окpужности и pадиуса. Если нет идей то хотябы
> напpавление куда копать :)
я как-то делал простой алгоритм
1) выбираются две точки из множества (произвольно)
и через них проводится окружность (эти две точки
заносятся в список)
2) ищется точка максимально удаленная от центра и
если она отстоит на расстоянии болишем радиуса, то
она заносится в список, иначе - завершение
3) по всем парам/тройкам точек их списка проводятся
окружности, и из тех которые покрывают все точки списка,
выбирается та которая имеет минимальный радиус
4) переходим к 2
такой алгоритм сходился за около 10 итераций (9-13),
и я его тестировал AFAICR на где-то полмиллиона точек
Cheers,
Serge
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
