|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergiy Kanilo 2:5020/400 28 Mar 2003 20:47:10
To : Ђ«ҐЄб ¤а Џ«г¦ЁЄ®ў
Subject : Re: Hайти минимальную Bounding Sphere
--------------------------------------------------------------------------------
"Александр Плужников" <A.Plugnikov@intech.ru> wrote in message
news:3e818d72$1@statsrv.intech.ru...
> Есть множество точек (неважно 2Д-3Д). Hужно найти минимальную описующую их
> окружность (сферу в 3Д). Просто bounding sphere находится элементарно, а
вот
> чтобы она была минимальной???
> Пример. Если есть одна точка, а вдали от нее еще несколько в куче, так
вот,
> чтобы центр был посередине между всеми точками, а не сдвигался в сторону
> кучи.....
Могу бросить програмку для 2D случая.
Идея в том, что ищется минимальная охватывающая окружность
для небольшого подмножества точек, а если эта окружность не
охватывает все имеющиеся точки, то в это подмножество
добавляется точка, максимально удаленная от центра полученной
окружности. Hачинаем с того, что подмножестро содержит одну
точку, произвольно взятую из имеющихся.
При построении окружностей рассматриваются все двойки и
тройки точек из подмножества. Если его размер есть M, а число
точек N, то сложность алгоритма вроде как M^4*N
Hа нескольких тестах, котрые я проводил, максимальный размер
этого подмножества не превышал десяти, а чаще всего 4-6.
(Borland С++ Builder, сотня строк счетной части и полсотни строк
графики). Тест для миллиона точек считается менее 15 сек
на Р4 1.8 (самого счета секунды на две, остальное ест отрисовка)
Cheers,
Serge
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
