Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 4 ] |
|
Автор | Сообщение | ||
---|---|---|---|
Nadi_B |
|
||
Дано n точек нужно построить окружность минимального радиуса,содержащего все точки. примерный алгоритм решения есть, но как с помощью циркуля построить не представляю, помогите, пожалуйста. |
|||
Вернуться к началу | |||
swan |
|
||
Вы не знаете как циркулем окружность начертить?
|
|||
Вернуться к началу | |||
Li6-D |
|
||
Чтобы построить такую окружность, нужно уметь:
1) определять наиболее удаленную точку из множества точек плоскости от заданной точки этой плоскости (циркуль); 2) строить окружность по двум диаметрально противоположным точкам (циркуль, линейка); 3) строить окружность по трем принадлежащим ей точкам (циркуль, линейка). С этим есть проблемы? |
|||
Вернуться к началу | |||
Li6-D |
|
||
Алгоритм построения минимальной охватывающей окружности (MEC):
Шаг 1. Выбираем любую точку P из множества точек. Это первое приближение к результату - окружность MEC нулевого радиуса с центром P. Если в множестве есть несовпадающие точки, то на следующих шагах радиус окружности MEC увеличивается. Окружность будет определяться двумя точками на диаметре или тремя точками - вершинами вписанного в MEC остроугольного треугольника. Будем отмечать на чертеже такие точки. По мере дальнейших построений отмечаем новые точки и снимаем отметку со старых. При этом отмеченными всегда остаются не более трёх точек текущей окружности MEC. Шаг 2. Находим наиболее удалённую от центра и находящуюся снаружи окружности MEC точку P множества. 2.1. Если такой точки нет – прекращаем построение (окружность MEC найдена). 2.2. Если есть – отмечаем P и находим наиболее от нее удалённую отмеченную точку Pi и построим на точках P и Pi новую окружность MEC как на диаметре. Шаг 3. Проверяем, есть ли среди оставшихся отмеченных точек старой окружности, точки находящиеся снаружи новой окружности MEC. 3.1. Если таких точек нет – отметку с внутренних точек снимаем, при этом имеем вариант, когда окружность MEC определяется двумя точками P и Pi. 3.2. Если снаружи MEC есть одна или две точки старой окружности, среди них выбирается и отмечается самая удаленная от центра окружности MEC точка Pj. Снимаем отметку с не попавшей в выбор отмеченной точки старой окружности (если такая точка была). Через отмеченные точки P,Pi,Pj проводим окружность MEC. Точки образуют остроугольный треугольник. Последнее утверждение не очевидно. Доказательство результативности и корректности алгоритма приведено по ссылке [1]. Шаг 4. Возвращаемся на шаг 2. Ссылки: [1] Доказательство на форуме dwg.ru (файл Minimum_Enclosing_Circle.pdf): http://forum.dwg.ru/showpost.php?p=857572&postcount=74. В этой же теме есть и программные реализации на языке AutoLisp. [2] Описания других алгоритмов: http://www.personal.kent.edu/~rmuhamma/ ... tercli.htm, http://en.wikipedia.org/wiki/Smallest-c ... Nickel1995 ▼ P.S.
|
|||
Вернуться к началу | |||
[ Сообщений: 4 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Отношение радиуса описанной окружности к радиусу окружности?
в форуме Геометрия |
22 |
1157 |
14 май 2018, 12:15 |
|
Вычисление радиуса окружности
в форуме Геометрия |
4 |
294 |
01 ноя 2018, 08:38 |
|
Задача на нахождение радиуса окружности
в форуме Геометрия |
1 |
595 |
13 мар 2016, 23:00 |
|
Определение длины перпендикуляра от радиуса до окружности
в форуме Геометрия |
3 |
398 |
01 июл 2017, 16:52 |
|
Построение окружности
в форуме Геометрия |
9 |
838 |
01 окт 2015, 02:44 |
|
Построение точек пересечения гиперболы и окружности | 6 |
395 |
02 фев 2023, 21:55 |
|
Поиск минимального пути в графе | 6 |
101 |
08 сен 2023, 13:53 |
|
Нахождение минимального остовного дерева | 0 |
115 |
12 дек 2019, 21:12 |
|
Метод Минимального Риска(не могу решить(() | 0 |
312 |
04 ноя 2015, 11:54 |
|
Поиск минимального пути в графе алгоритмом Форда Беллмана | 1 |
380 |
27 дек 2018, 10:22 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 35 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |