Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 4 ] 
Автор Сообщение
 Заголовок сообщения: Построение окружности минимального радиуса
СообщениеДобавлено: 28 май 2015, 08:42 
Не в сети
Начинающий
Зарегистрирован:
26 апр 2015, 10:30
Сообщений: 12
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 0

Добавить очки репутацииУменьшить очки репутации
Добрый день! Очень нужна помощь в решении задачи на построение с помощью циркуля и линейки:

Дано n точек нужно построить окружность минимального радиуса,содержащего все точки.

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Построение окружности минимального радиуса
СообщениеДобавлено: 28 май 2015, 09:50 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
Вы не знаете как циркулем окружность начертить?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Построение окружности минимального радиуса
СообщениеДобавлено: 28 май 2015, 19:15 
Не в сети
Beautiful Mind
Аватара пользователя
Зарегистрирован:
10 дек 2014, 20:21
Сообщений: 1204
Cпасибо сказано: 288
Спасибо получено:
679 раз в 545 сообщениях
Очков репутации: 148

Добавить очки репутацииУменьшить очки репутации
Чтобы построить такую окружность, нужно уметь:
1) определять наиболее удаленную точку из множества точек плоскости от заданной точки этой плоскости (циркуль);
2) строить окружность по двум диаметрально противоположным точкам (циркуль, линейка);
3) строить окружность по трем принадлежащим ей точкам (циркуль, линейка).
С этим есть проблемы?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Построение окружности минимального радиуса
СообщениеДобавлено: 29 май 2015, 21:32 
Не в сети
Beautiful Mind
Аватара пользователя
Зарегистрирован:
10 дек 2014, 20:21
Сообщений: 1204
Cпасибо сказано: 288
Спасибо получено:
679 раз в 545 сообщениях
Очков репутации: 148

Добавить очки репутацииУменьшить очки репутации
Алгоритм построения минимальной охватывающей окружности (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-6 прогонов по шагам 2,3,4.
Важно! Данный алгоритм, а именно шаг 3.2, не годится для поиска окружности MEC, охватывающей множество кругов на плоскости. Пока проблема открыта, на шаге 3.2 можно перебирать три варианта выбора отмеченных кругов, строя для каждого для них окружности Аполлония.

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 4 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Отношение радиуса описанной окружности к радиусу окружности?

в форуме Геометрия

valeron1115

22

1157

14 май 2018, 12:15

Вычисление радиуса окружности

в форуме Геометрия

denispetrov

4

294

01 ноя 2018, 08:38

Задача на нахождение радиуса окружности

в форуме Геометрия

KetiS

1

595

13 мар 2016, 23:00

Определение длины перпендикуляра от радиуса до окружности

в форуме Геометрия

Lysyok

3

398

01 июл 2017, 16:52

Построение окружности

в форуме Геометрия

xbujhm

9

838

01 окт 2015, 02:44

Построение точек пересечения гиперболы и окружности

в форуме Интересные задачи участников форума MHP

Li6-D

6

395

02 фев 2023, 21:55

Поиск минимального пути в графе

в форуме Дискретная математика, Теория множеств и Логика

Ramirobass

6

101

08 сен 2023, 13:53

Нахождение минимального остовного дерева

в форуме Дискретная математика, Теория множеств и Логика

633 50541

0

115

12 дек 2019, 21:12

Метод Минимального Риска(не могу решить(()

в форуме Математическая статистика и Эконометрика

viktoriya shvetsova

0

312

04 ноя 2015, 11:54

Поиск минимального пути в графе алгоритмом Форда Беллмана

в форуме Дискретная математика, Теория множеств и Логика

Berliqz

1

380

27 дек 2018, 10:22


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 35


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved