Окружность минимального радиуса содержащую точки (2 видео)

Содержание

Окружность минимального радиуса содержащую точки
Окружность минимального радиуса содержащую точки
Минимальная окружность, покрывающая множество точек
💡 Видео

Видео:Отрезки касательных из одной точки до точек касания окружности равны | Окружность | ГеометрияСкачать

Окружность минимального радиуса содержащую точки

Дано конечное множество точек на плоскости. Нужно найти окружность минимального радиуса такую, чтобы данные точки были внутри неё. Следующая функция находит такую окружность: Здесь data — это массив входных точек, а index — указатель на массив, в который будут записаны индексы точек по которым была построена окружность ( в том случае, если указатель не равен 0 ).

Описание алгоритма:
1. Если к-во входных точек равно 0, то возвращаем неопределённую окружность.
2. Если к-во входных точек равно 1, то возвращаем окружность с центром в этой точке и нулевым радиусом.
3. Если к-во входных точек равно 2, то возвращаем окружность с центром в середине между этими точками и соответсвующим радиусом.
4. Находим самую удалённую точку от первой. Если это расстояние будет равно 0, то возвращаем окружность с центром в первой точке и нулевым радиусом. Иначе считаем эти точки опорными и строим по ним окружность, как в пункте 3.
5. Начало цикла.
6. Находим самую удаленную точку от центра текущей окружности. Если это расстояние не больше, чем радиус текущей окружности или индекс самой удалённой точки равен одному из индексов опорных точек, то выходим из цикла. Иначе будем включать эту точку в число опорных, а пока назовём её новой.
7. Найдём среди опорных точек самую удаленную от новой точки и построим текущую окружность по двум точкам ( новой и найденной ).
8. Если к-во опорных точек текущей окружности было равным 3, то переходим к пункту 9. Иначе проверим выходит ли неиспользованная опорная точка за пределы текущей окружности. Если не выходит, то заменяем её на новую точку ( к-во опорных точек останется равным 2 ). Иначе добавляем новую точку в опорные и строим окружность по трём точкам. Переходим к пункту 10.
9. Находим из двух неиспользованных точек самую удаленную от центра текущей окружности. Если эта точка лежит вне круга, то она будет третьей опорной и тогда строим окружность по трём новым опорным точкам. Иначе опорных точек останется две.
10. Если радиус окружности не вырос за время цикла, то конец алгоритма, иначе идём на начало цикла.

Дано конечное множество окружностей на плоскости. Нужно найти окружность минимального радиуса такую, чтобы все данные окружности были внутри неё. Следующая функция находит такую окружность: Описание этого алгоритма аналогично описанию алгоритма для точек.

Дано конечное множество прямых на плоскости. Нужно найти окружность минимального радиуса такую, чтобы она пересекала все данные прямые. Следующая функция находит такую окружность:

Описание шаблонов классов CArrRef и DynArrRef находится здесь.
Описание шаблона классов Def находится здесь.
Описание класса Vector2d находится здесь.
Описание классов Line2d и Circle2d находится здесь.

Видео:Всё про углы в окружности. Геометрия | МатематикаСкачать

Окружность минимального радиуса содержащую точки

Везде в дальнейшем будем обозначать через C(P,Z) окружность с центром в точке (P,O) и проходящую через точку Z=(Z x ,Z y ).

Очевидно, что на искомой окружности лежит по меньшей мере одна точка. Действительно, в противном случае мы можем, не меняя центра окружности, уменьшить ее радиус, а это противоречит предположению о том, что нами была построена окружность минимального радиуса.

Докажем следующее простое утверждение: Если на искомой окружности лежит единственная точка, то центр окружности есть проекция этой точки на ось абсцисс.

Предположим противное — на минимальной окружности лежит единственная точка Z(Z x ,Z y ), а центр ее не совпадает с (Z x ,0). Если мы начнем понемножку двигать центр окружности, проходящей через точку Z, в направлении (Z x ,0), то, так как все точки, кроме Z, лежат внутри окружности, до какого-то момента они и будут оставаться внутри нее. Таким образом мы можем хоть чуть-чуть, но сдвинуть центр, уменьшив при этом радиус окружности, содержащей все точки. Получаем противоречие с предположением о минимальности радиуса.

Следствие. Если на искомой окружности лежит только одна точка, то это точка с максимальной по модулю ординатой.

Отметим далее, что окружность с центром на оси абсцисс

единственным образом определяется двумя лежащими на ней точками (центр этой окружности — это точка пересечения оси абсцисс и срединного перпендикуляра к отрезку, соединяющего эти две точки).

Таким образом мы получаем следующий

Шаг 1. Ищем точку (x i ,y i ) с максимальной по модулю ординатой y i (если таких точек несколько, и у них разные абсциссы, то перейти на Шаг 2), и для окружности C(x i ,(x i ,y i )) проверяем, содержит ли она все N точек. Если да, то задача решена, если нет, то

Шаг 2. Среди окружностей, определяемых всевозможными парами точек (P i , P j ), находим те, которые содержат все точки, а затем выбираем из них окружность минимального радиуса.

Пар точек, которые могут определять окружности, всего N(N-1)/2, т.е. порядка N*N, следовательно, и возможных окружностей тоже порядка N*N. Для проверки принадлежности N точек каждой окружности требуется порядка N операций. Получаем, что сложность этого алгоритма порядка N 3 . (Когда мы говорим о сложности алгоритма, то мы рассматриваем только зависимость роста числа требуемых операций от числа N, игнорируя все константные множители и медленно растущие слагаемые).

Рассмотрим другой способ решения этой задачи, основанный

на более глубоком ее анализе.

Проверка по Шагу 1 ранее изложенного алгоритма остается без изменения. Пусть искомая окружность не найдена.

Для обоснования Шага 2 докажем следующее утверждение: Пусть окружность с центром (P ij ,0) определяется точками

P i (x i ,y i ) и P j (x j ,y j ). Она только тогда может быть содержащей все точки окружностью C минимального радиуса, когда (P ij ,0) лежит на ортогональной проекции отрезка [(x i ,y i ),(x j ,y j )] на ось абсцисс, т.е. должны выполняться неравенства x i ij j .

Окружность C с центром ( Pij0 ) должна проходить не менее чем через 2 точки заданного множества из N точек, и при этом из этих точек всегда можно выбрать две такие (обозначим их P i (x i ,y i ) и P j (x j ,y j )), что x i

ij j . Действительно, если бы абсциссы всех лежащих на окружности точек были, например, меньше P ij , то (P ij ,0) можно было бы сместить влево по оси абсцисс на некоторую величину с уменьшением радиуса охватывающей все точки окружности, что противоречит минимальности найденной ранее окружности.

Ни одна из точек, лежащих на окружности не может иметь абсциссы P ij вследствие невыполнения условия Шага 1.

Итак: всегда можно найти две лежащие на окружности точки P i и P j с абсциссами, соответственно, меньше и больше абсциссы центра окружности. Эти точки определяют центр окружности (P ij ,0) — точку пересечение серединного перпендикуляра к отрезку [P i ,P j ] с осью абсцисс. При этом точка (P ij ,0), естественно, будет лежать на проекции отрезка [P i ,P j ] на ось абсцисс.

Рассматривая все пары точек (P i ,P j ) таких, что точка пересечения (P ij ,0) серединного перпендикуляра к отрезку [P i ,P j ] с осью абсцисс лежит на проекции отрезка [P i ,P j ] на ось абсцисс, получаем, что центр искомой окружности минимального радиуса совпадает с одной из таким образом полученных точек. Каждая из рассматриваемых пар точек (P i ,P j ) определяет окружность минимального радиуса R ij , содержащую эти две точки.

Из всего вышесказанного получаем, что интересующая нас окружность минимального радиуса, содержащая N точек, должна

иметь максимальный из всех полученных радиусов R ij .

Всего пар точек (P i ,P j ) не более (N 2 -N)/2, и, следовательно, сложность алгоритма

O((N 2 -N)/2) = O(N 2 -N) = O(N 2 ).

Тут мы, как и обычно, избавляемся от констант и медленно растущих слагаемых.

Все вычисления на машине проводятся с ограниченной точностью, с определенным числом знаков после запятой. Поэтому нам бывает достаточно только указать, что интересующая нас точка лежит внутри отрезка заранее заданной длины epsilon. Epsilon задается пользователем. Например, если мы хотим найти координату точки с точностью 5 знаков после запятой, то epsilon = 10 -6 .

В отличие от варианта #2 мы не будем брать все перпендикуляры, попадающие на проекции отрезков и искать среди получаемых окружностей окружность с максимальным радиусом. Наоборот, описанным ниже способом будем выбирать точку на оси абсцисс и проверять, является ли она искомой или нет.

Из варианта решения #2 можно сделать вывод, что искомая точка лежит на отрезке [A 0 ,B 0 ]=[min,max]. Пусть C 0 =(A 0 +B 0 )/2 — середина этого отрезка, а L=B 0 -A 0 его длина.

D 1 (C 0 )=максимальное из расстояний от точки (C 0 ,0) до точек (x i ,y i ) с абсциссами x i 0 ;

D r (C 0 )=максимальное из расстояний от точки (C 0 ,0) до точек (x i ,y i ) с абсциссами x i >=C 0 .

i-ый итеративный (повторяющийся) шаг алгоритма, i=0, 1, 2, 3, . :

Если B i -A i i ,B i ] и желаемая точность достигнута. Стоп.

Вычисляем C i =(A i +B i )/2.

Находим D l (C i ) и D r (C i ).

Если D l (C i ) r (C i ), то искомая точка не может лежать на промежутке [A i ,C i ), так как радиус любой содержащей N точек окружности с центром на этом промежутке больше D r (C i ) (проверьте сами!), а окружность с центром C i имеет радиус D r (C i ). Поэтому центр искомой окружности лежит на [C i ,B i ], который мы обозначим [A i+1 ,B i+1 ],

иначе, если D r (C i ) l (C i ), то, аналогично, получаем, что центр искомой окружности лежит на [A i ,C i ], которой мы обозначим [A i+1 ,B i+1 ]

иначе, если D r (C i )=D l (C i ),

то C i — центр искомой окружности. Стоп.

Конец i-го итеративного шага. Выполнить шаг i+1.

Мы видим, что длина L начального отрезка на каждом шаге уменьшается вдвое. Алгоритм, вообще говоря, заканчивает работу при выполнении условия

L/(2 S ) 2 (L/epsilon)]+1 шагов, где log 2 — это логарифм по основанию 2.

Так как на каждом шаге (для вычисления D l и D r ) выполняется не более O(N) операций, то всего их потребуется порядка O(N log 2 (L/epsilon)).

Видео:10 класс, 11 урок, Числовая окружностьСкачать

Минимальная окружность, покрывающая множество точек

Дано множество точек
Необходимо найти окружность минимального радиуса такую, чтобы все точки находились в ней (либо точка лежит на границе, либо находится внутри)

1. Пусть наша окружность обязательно должна проходить через заданные три точки, тогда мы строим описывающую окружность около этого заданного треугольника.
2. Пусть наша окружность обязательно должна проходить через две заданные точки, тогда мы перебираем все точки, берём одну из точек за третью и строим окружность согласно пункту 1. На каждом шаге перебора мы храним найденную окружность. Если текущая точка не принадлежит найденной, то найденная окружность будет равна текущей окружности, которую мы построили.
3. Пусть наша окружность обязательно должна проходить через одну заданную точку, тогда мы аналогично пункту 2 перебираем все точки, строим текущую окружность согласно пункту 2 и, если текущая точка не принадлежит найденной окружности, приравниваем найденной текущую окружность.
4. Пусть нам надо найти минимальную окружность, покрывающую множество точек, тогда мы перебираем все точки, строим окружности согласно пункту 3, и аналогично пунктам 2 и 3 находим искомую окружность.

const double inf = 1e17;
const double eps = 1e-7;

circ = part (p1, p2, 1, 1);
r = 0.5 * dist (p1, p2);

point mab = part (a, b, 1, 1);
point mac = part (a, c, 1, 1);
double a1 = a.x — b.x;
double b1 = a.y — b.y;
double c1 = — a1 * mab.x — b1 * mab.y;
double a2 = a.x — c.x;
double b2 = a.y — c.y;
double c2 = — a2 * mac.x — b2 * mac.y;

double x, y;
x = (b2 * c1 — b1 * c2) / (a2 * b1 — a1 * b2);
if (!equald (b1, eps))
y = — (a1 * x + c1) / b1;
else
y = — (a2 * x + c2) / b2;

circ = point (x, y);
r = dist (circ, a);
>

void min_disk2 (point p[], int n, point a, point b, point &circ, double &r)
<
circ = part (a, b, 1, 1);
r = dist (circ, a);
for ( int i = 0; i if (lessd (r, dist (p[i], circ)))
min_disk3 (p[i], a, b, circ, r);
>
void min_disk1 (point p[], int n, point a, point &circ, double &r)
<
circ = part (p[0], a, 1, 1);
r = dist (circ, a);
for ( int i = 1; i if (lessd (r, dist (p[i], circ)))
min_disk2 (p, i, a, p[i], circ, r);
>
void min_disk (point p[], int n, point &circ, double &r)
<
circ = part (p[0], p[1], 1, 1);
r = dist (circ, p[0]);
for ( int i = 2; i if (lessd (r, dist (p[i], circ)))
min_disk1 (p, i, p[i], circ, r);
>