Re: Описывающая контур окружность
От: mab Россия http://shade.msu.ru/~mab
Дата: 28.05.03 14:48
Оценка:
Здравствуйте, LameFox, Вы писали:

LF>Существует множество точек на плоскости, заданных координатами (X,Y).

LF>Подскажите плиз способ нахождения координат центра (CX,CY) и минимального радиуса (R) окружности,
LF>которая включала бы в себя все эти точки.

Все сильно зависит от того, какая сложность вас устроит.

1. Дебильный вариант: перебираем все возможные пары точек как кандидатов
в диаметры, кроме того пробуем около всякой тройки точек описать окружность.
Время работы O(N^4). Никогда так не делайте!

2. Стандартный вариант: ну диаметры можно по-прежнему перебирать, это даст
O(N^3), а перебор троек можно оптимизировать. Именно фиксируем пару точек
A и B. Возможны два случая расположения центра -- в верхней относительно AB
полуплоскости и в нижней. Для каждого, случая рассмотрев оставшиеся точки,
несложно вычислить требования к радиусу окружности: оценки снизу и сверху.
Наконец еще за один проход можно выяснить, есть ли подходящая третья точка.
Получится сложность O(N^3), кроме того тут еще море возможностей для
оптимизаций и вариаций.

3. Если точек очень много.. ну тогда нам поможет диаграма Вороного.
Ссылка из Handbook of Theoretical Computer Science, vol A., p. 363,
sec. 6.3.3 "Smallest enclosing circle".
Smahos and Hoey [200] exhibited the first O(n log n) solution by
ovservising that the smallest enclosing circle is either determined by the diameter
of the set of centered at a vertex of the furthest-point Voronoi diagram
.

Если интересно, что такое [200], то это:
Shamos, M.I. and D. Hoey, Closest-point problems, in: Proc. 16th IEEE Ann.
Symp. Found. Comput. Sci. (1975), 151-162
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.