0 / 0 / 0
Регистрация: 04.09.2015
Сообщений: 4
1

Поиск координат центра окружности описанной около точек

11.09.2015, 15:27. Показов 4065. Ответов 13
Метки нет (Все метки)

Здравствуйте, задача состоит в следующем, даны координаты n точек (x1;y1),(x2;y2)...(xn;yn) в виде массива, надо найти координаты центра и радиус окружности, которая будет их описывать.
В интернете такого алгоритма не нашел, помогите пожалуйста, если можно в виде кода на С#.
А если где-то уже есть подобные решения, то ссылкой. Спасибо.
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
11.09.2015, 15:27
Ответы с готовыми решениями:

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

Поиск центра описанной окружности у треугольника
Дан треугольник заданный тремя точками в пространстве. Нужна функция типа Point centr(Point f,...

По заданным координатам центра окружности и ее радиусу определить координаты точек пересечения окружности с осями координат.
По заданным координатам центра окружности и ее радиусу определить координаты точек пересечения...

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

13
управление сложностью
1687 / 1300 / 259
Регистрация: 22.03.2015
Сообщений: 7,545
Записей в блоге: 5
12.09.2015, 12:55 2
Если количество элементов массива нечетное, тогда что делать ?
Задаче не до конца ясна
0
Заблокирован
12.09.2015, 14:15 3
ДмитрийГ,
однозначно окружность зададут 3 точки (не лежащие на прямой).
Если у вас точек больше, то задача:
найти центр окружности минимального радиуса, описанной так, что все точки оказываются внутри или на окружности.
?
0
0 / 0 / 0
Регистрация: 04.09.2015
Сообщений: 4
12.09.2015, 18:51  [ТС] 4
IrineK, Точек большое количество (примерно 100-1000). Я знаю, что задачу можно решить просто перебором любых 3х точек, взяв самый большой получившийся радиус, который их опишет, но это слишком долго, уже выборка С из 300 по 3 это примерно 4.5 миллиона, надо как-то оптимизировать. Спасибо.

Добавлено через 20 минут
Почтальон, массив двумерный, и количество элементов, т.е. точек, значения не имеет. Задача состоит в нахождении центра окружности минимального радиуса, описанной так, что все точки оказываются внутри или на окружности, как уточнила уже IrineK.
0
Диссидент
Эксперт C
26954 / 16835 / 3699
Регистрация: 24.12.2010
Сообщений: 37,786
13.09.2015, 00:28 5
ДмитрийГ, Можно попытаться пойти таким путем. Нарисовать прямоугольник, включающий в себя все точки (скажем, со сторонами, параллельными осям координат). Описать окружность вокруг этого прямоугольника. Взять точку, наиболее удаленную от центра этой окружности. Вот и новый радиус.
Не факт, что нет лучшей окружности, но уже какая-то прикидка.
Если нужно точное решение, можно воспользоваться методом ветвей и границ (перебор с отсечением явно бесперспективных троек), но как его тут присобачить, так на вскидку - не знаю.

Добавлено через 4 минуты
Если нужно хоть какое-то приемлемое (эвристическое) решение, можно перебрать с некоторым шагом углы наклона сторон прямоугольника к осям. Всетки сложность будет порядка O(n), а не O(n3) как при переборе троек.
0
0 / 0 / 0
Регистрация: 04.09.2015
Сообщений: 4
13.09.2015, 01:30  [ТС] 6
Байт, спасибо за Ваш ответ, но к сожалению приблизительный радиус не подойдет.
А вот что имелось ввиду "можно перебрать с некоторым шагом углы наклона сторон прямоугольника к осям" - можно по подробнее, потому если сложность О(n), я думаю этого будет достаточно.
0
Эксперт С++
3219 / 1746 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
13.09.2015, 08:50 7
Цитата Сообщение от ДмитрийГ Посмотреть сообщение
Задача состоит в нахождении центра окружности минимального радиуса, описанной так, что все точки оказываются внутри или на окружности
Можно сначала вычислить среднее арифметическое центров всех окружностей (т.е. центр масс этого множества точек), затем взять три самые удаленные от центра масс точки и провести через них окружность.

Добавлено через 1 час 28 минут
Не, это ложная гипотеза.
Предлагаю такой алгоритм:
1) Найти выпуклую оболочку заданного множества точек.
2) Стянуть вокруг нее окружность минимального радиуса.

Добавлено через 3 часа 39 минут
Окружность минимального радиуса стягиваем вокруг выпуклого многоугольника следующим образом:
1) Выбираем две самые удаленные друг от друга вершины многоугольника A и B.
2) Из оставшихся вершин многоугольника выбираем ту вершину C, из которой отрезок AB виден под минимальным углом ACB.
3) Через точки A, B и C проводим окружность.
1
Диссидент
Эксперт C
26954 / 16835 / 3699
Регистрация: 24.12.2010
Сообщений: 37,786
13.09.2015, 09:04 8
Цитата Сообщение от ДмитрийГ Посмотреть сообщение
А вот что имелось в виду
В самом начале своего поста я предложил построить прямоугольник, включающий в себя все точки. Для простоты предложил взять его со сторонами, параллельными осям. Это просто. Находим максимальную и минимальную координату точек по каждой оси - вот и прямоугольник. Но выбор осей - дело случайное. И разное направление их даст разный результат. Вот я и предлагаю "повертеть" оси (или прямоугольник, что одно и тоже)
0
Эксперт С++
3219 / 1746 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
13.09.2015, 09:10 9
Уточнение к моему алгоритму. Точку C задействуем только в том случае, если угол ACB не больше прямого. В противном случае строим окружность на отрезке AB как на диаметре.
1
Диссидент
Эксперт C
26954 / 16835 / 3699
Регистрация: 24.12.2010
Сообщений: 37,786
13.09.2015, 09:17 10
Цитата Сообщение от Mr.X Посмотреть сообщение
Уточнение к моему алгоритму. Точку C задействуем только в том случае, если угол ACB не больше прямого. В противном случае строим окружность на отрезке AB как на диаметре.
Только что хотел обратить внимание на этот момент. Но... - вы сами.

Добавлено через 2 минуты
Вообще, окружность минимального радиуса не обязательно проходит через 3 точки (пример - тупоугольный треугольник)
0
Эксперт С++
3219 / 1746 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
13.09.2015, 09:28 11
Цитата Сообщение от Байт Посмотреть сообщение
пример - тупоугольный треугольник
Ну да,
Цитата Сообщение от Mr.X Посмотреть сообщение
Точку C задействуем только в том случае, если угол ACB не больше прямого. В противном случае строим окружность на отрезке AB как на диаметре.
0
0 / 0 / 0
Регистрация: 04.09.2015
Сообщений: 4
13.09.2015, 10:45  [ТС] 12
Mr.X, в случае остроугольного треугольника, одна из его сторон не обязательно самая большая.
Пр: представим вписанный треугольник со сторонами 60гр, в описывающей его окружности может быть кучу отрезков на много больших, чем сторона этого треугольника.
0
Почетный модератор
64253 / 47553 / 32739
Регистрация: 18.05.2008
Сообщений: 115,182
13.09.2015, 10:57 13
del
0
Эксперт С++
3219 / 1746 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
13.09.2015, 11:21 14
Цитата Сообщение от ДмитрийГ Посмотреть сообщение
Mr.X, в случае остроугольного треугольника, одна из его сторон не обязательно самая большая.
Пр: представим вписанный треугольник со сторонами 60гр, в описывающей его окружности может быть кучу отрезков на много больших, чем сторона этого треугольника.
Ваш пример не очень понял.
Я тут нашел случай действительно не охваченный моим решением. Представим себе фигуру, составленную из одинаковых узких равнобедренных треугольников с общей вершиной, веер этакий. Тогда не всякая наибольшая диагональ этого выпуклого многоугольника годится для решения.
Т.е., если максимальных по длине сторон или диагоналей несколько, то выбираем ту, которая из всех равных ей диагоналей для всех вершин имеет наименьший угол ACB.

Добавлено через 13 минут
ДмитрийГ, понял ваш контрпример. Да, скорее всего тут надо выбирать не самую длинную диагональ, а три точки многоугольника, образующие треугольник наибольшей площади.

Добавлено через 1 минуту
Это если есть остроугольные треугольники.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
13.09.2015, 11:21
Помогаю со студенческими работами здесь

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

Определить координаты центра и радиус описанной около треугольника окружности
В плоскости задан треугольник координатами своих вершин. Определить координаты центра и радиус...

Вычисление координат центра описанной окружности
Задан треугольник координатами своих вершин Требуется определить координаты центра описанной...

Диаметр окружности, описанной около треугольника
Такая задача: В треугольнике MNP сторона MN не длиннее 12, сторона NP не длиннее 5, а его площадь...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru