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

@ДмитрийГ · Регистрация: 04.09.2015

Студворк — интернет-сервис помощи студентам

Здравствуйте, задача состоит в следующем, даны координаты n точек (x1;y1),(x2;y2)...(xn;yn) в виде массива, надо найти координаты центра и радиус окружности, которая будет их описывать.
В интернете такого алгоритма не нашел, помогите пожалуйста, если можно в виде кода на С#.
А если где-то уже есть подобные решения, то ссылкой. Спасибо.

@Почтальон · 12.09.2015, 12:55

Если количество элементов массива нечетное, тогда что делать ?
Задаче не до конца ясна

@IrineK · 12.09.2015, 14:15

ДмитрийГ,
однозначно окружность зададут 3 точки (не лежащие на прямой).
Если у вас точек больше, то задача:

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

?

@ДмитрийГ · 12.09.2015, 18:51 **[ТС]**

IrineK, Точек большое количество (примерно 100-1000). Я знаю, что задачу можно решить просто перебором любых 3х точек, взяв самый большой получившийся радиус, который их опишет, но это слишком долго, уже выборка С из 300 по 3 это примерно 4.5 миллиона, надо как-то оптимизировать. Спасибо.

Добавлено через 20 минут
Почтальон, массив двумерный, и количество элементов, т.е. точек, значения не имеет. Задача состоит в нахождении центра окружности минимального радиуса, описанной так, что все точки оказываются внутри или на окружности, как уточнила уже IrineK.

Байт · 13.09.2015, 00:28

ДмитрийГ, Можно попытаться пойти таким путем. Нарисовать прямоугольник, включающий в себя все точки (скажем, со сторонами, параллельными осям координат). Описать окружность вокруг этого прямоугольника. Взять точку, наиболее удаленную от центра этой окружности. Вот и новый радиус.
Не факт, что нет лучшей окружности, но уже какая-то прикидка.
Если нужно точное решение, можно воспользоваться методом ветвей и границ (перебор с отсечением явно бесперспективных троек), но как его тут присобачить, так на вскидку - не знаю.

Добавлено через 4 минуты
Если нужно хоть какое-то приемлемое (эвристическое) решение, можно перебрать с некоторым шагом углы наклона сторон прямоугольника к осям. Всетки сложность будет порядка O(n), а не O(n³) как при переборе троек.

@ДмитрийГ · 13.09.2015, 01:30 **[ТС]**

Байт, спасибо за Ваш ответ, но к сожалению приблизительный радиус не подойдет.
А вот что имелось ввиду "можно перебрать с некоторым шагом углы наклона сторон прямоугольника к осям" - можно по подробнее, потому если сложность О(n), я думаю этого будет достаточно.

@Mr.X · 13.09.2015, 08:50

Сообщение от ДмитрийГ

Задача состоит в нахождении центра окружности минимального радиуса, описанной так, что все точки оказываются внутри или на окружности

Можно сначала вычислить среднее арифметическое центров всех окружностей (т.е. центр масс этого множества точек), затем взять три самые удаленные от центра масс точки и провести через них окружность.

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

Добавлено через 3 часа 39 минут
Окружность минимального радиуса стягиваем вокруг выпуклого многоугольника следующим образом:
1) Выбираем две самые удаленные друг от друга вершины многоугольника A и B.
2) Из оставшихся вершин многоугольника выбираем ту вершину C, из которой отрезок AB виден под минимальным углом ACB.
3) Через точки A, B и C проводим окружность.

Байт · 13.09.2015, 09:04

Сообщение от ДмитрийГ

А вот что имелось в виду

В самом начале своего поста я предложил построить прямоугольник, включающий в себя все точки. Для простоты предложил взять его со сторонами, параллельными осям. Это просто. Находим максимальную и минимальную координату точек по каждой оси - вот и прямоугольник. Но выбор осей - дело случайное. И разное направление их даст разный результат. Вот я и предлагаю "повертеть" оси (или прямоугольник, что одно и тоже)

@Mr.X · 13.09.2015, 09:10

Уточнение к моему алгоритму. Точку C задействуем только в том случае, если угол ACB не больше прямого. В противном случае строим окружность на отрезке AB как на диаметре.

Байт · 13.09.2015, 09:17

Сообщение от Mr.X

Уточнение к моему алгоритму. Точку C задействуем только в том случае, если угол ACB не больше прямого. В противном случае строим окружность на отрезке AB как на диаметре.

Только что хотел обратить внимание на этот момент. Но... - вы сами.

Добавлено через 2 минуты
Вообще, окружность минимального радиуса не обязательно проходит через 3 точки (пример - тупоугольный треугольник)

@Mr.X · 13.09.2015, 09:28

Сообщение от Байт

пример - тупоугольный треугольник

Ну да,

Сообщение от Mr.X

Точку C задействуем только в том случае, если угол ACB не больше прямого. В противном случае строим окружность на отрезке AB как на диаметре.

@ДмитрийГ · 13.09.2015, 10:45 **[ТС]**

Mr.X, в случае остроугольного треугольника, одна из его сторон не обязательно самая большая.
Пр: представим вписанный треугольник со сторонами 60гр, в описывающей его окружности может быть кучу отрезков на много больших, чем сторона этого треугольника.

@Puporev · 13.09.2015, 10:57

del

@Mr.X · 13.09.2015, 11:21

Сообщение от ДмитрийГ

Mr.X, в случае остроугольного треугольника, одна из его сторон не обязательно самая большая.
Пр: представим вписанный треугольник со сторонами 60гр, в описывающей его окружности может быть кучу отрезков на много больших, чем сторона этого треугольника.

Ваш пример не очень понял.
Я тут нашел случай действительно не охваченный моим решением. Представим себе фигуру, составленную из одинаковых узких равнобедренных треугольников с общей вершиной, веер этакий. Тогда не всякая наибольшая диагональ этого выпуклого многоугольника годится для решения.
Т.е., если максимальных по длине сторон или диагоналей несколько, то выбираем ту, которая из всех равных ей диагоналей для всех вершин имеет наименьший угол ACB.

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

Добавлено через 1 минуту
Это если есть остроугольные треугольники.

Новые блоги и статьи Все статьи Все блоги /
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .

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

	Поиск координат центра окружности описанной около точек 11.09.2015, 15:27. Показов 5379. Ответов 13 Метки нет (Все метки) Здравствуйте, задача состоит в следующем, даны координаты n точек (x1;y1),(x2;y2)...(xn;yn) в виде массива, надо найти координаты центра и радиус окружности, которая будет их описывать. В интернете такого алгоритма не нашел, помогите пожалуйста, если можно в виде кода на С#. А если где-то уже есть подобные решения, то ссылкой. Спасибо. 0

@Почтальон управление сложностью 1693 / 1306 / 259 Регистрация: 22.03.2015 Сообщений: 7,545 Записей в блоге: 5
	12.09.2015, 12:55
	Если количество элементов массива нечетное, тогда что делать ? Задаче не до конца ясна 0

@ДмитрийГ 0 / 0 / 0 Регистрация: 04.09.2015 Сообщений: 4
	12.09.2015, 18:51 [ТС]
	IrineK, Точек большое количество (примерно 100-1000). Я знаю, что задачу можно решить просто перебором любых 3х точек, взяв самый большой получившийся радиус, который их опишет, но это слишком долго, уже выборка С из 300 по 3 это примерно 4.5 миллиона, надо как-то оптимизировать. Спасибо. Добавлено через 20 минут Почтальон, массив двумерный, и количество элементов, т.е. точек, значения не имеет. Задача состоит в нахождении центра окружности минимального радиуса, описанной так, что все точки оказываются внутри или на окружности, как уточнила уже IrineK. 0

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	13.09.2015, 00:28
	ДмитрийГ, Можно попытаться пойти таким путем. Нарисовать прямоугольник, включающий в себя все точки (скажем, со сторонами, параллельными осям координат). Описать окружность вокруг этого прямоугольника. Взять точку, наиболее удаленную от центра этой окружности. Вот и новый радиус. Не факт, что нет лучшей окружности, но уже какая-то прикидка. Если нужно точное решение, можно воспользоваться методом ветвей и границ (перебор с отсечением явно бесперспективных троек), но как его тут присобачить, так на вскидку - не знаю. Добавлено через 4 минуты Если нужно хоть какое-то приемлемое (эвристическое) решение, можно перебрать с некоторым шагом углы наклона сторон прямоугольника к осям. Всетки сложность будет порядка O(n), а не O(n³) как при переборе троек. 0

@ДмитрийГ 0 / 0 / 0 Регистрация: 04.09.2015 Сообщений: 4
	13.09.2015, 01:30 [ТС]
	Байт, спасибо за Ваш ответ, но к сожалению приблизительный радиус не подойдет. А вот что имелось ввиду "можно перебрать с некоторым шагом углы наклона сторон прямоугольника к осям" - можно по подробнее, потому если сложность О(n), я думаю этого будет достаточно. 0

@Mr.X 3225 / 1752 / 436 Регистрация: 03.05.2010 Сообщений: 3,867
	13.09.2015, 09:10
	Уточнение к моему алгоритму. Точку C задействуем только в том случае, если угол ACB не больше прямого. В противном случае строим окружность на отрезке AB как на диаметре. 1

@ДмитрийГ 0 / 0 / 0 Регистрация: 04.09.2015 Сообщений: 4
	13.09.2015, 10:45 [ТС]
	Mr.X, в случае остроугольного треугольника, одна из его сторон не обязательно самая большая. Пр: представим вписанный треугольник со сторонами 60гр, в описывающей его окружности может быть кучу отрезков на много больших, чем сторона этого треугольника. 0

@Puporev Почетный модератор 64314 / 47610 / 32743 Регистрация: 18.05.2008 Сообщений: 115,168
	13.09.2015, 10:57
	del 0