минимальная окружность

[undefined]

Имеется облако точек x[i],y[i].Требуется найти минимальную окружность,охватывающую все точки.
NB:Сложность алгоритма не должна зависеть от расположения точек.

[Tails]

1. Найти среднее арифметическое (позицию) точек dx и dy.
2. Найти максимальный радиус среди точек до этих dx, dy.
Два прохода по массиву. Вроде, должно работать.

[ZackMercury]

Tails, неверно :3
https://pp.userapi.com/c639723/v639723943/45ac7/t4koAaegyWA.jpg

[ZackMercury]

Среднее арифметическое точек(оранжевый круг)
Test.swf

[undefined]

Tails, неверно :3
Да, окружность выходит неминимальная.

[ZackMercury]

Окружность вообще не выходит, ибо 1) центр не найден 2) радиус не найден.

(если что, если через 5 точек возможно провести окружность, то только одну)

[undefined]

Окружность вообще не выходит, ибо 1) центр не найден 2) радиус не найден.

Алгоритм Tails даст вполне конкретный центр и радиус.Другой вопрос что они неверные будут,кстати, неминимальность хорошо видна если точки раскидать по эллипсу
32807

[undefined]

(если что, если через 5 точек возможно провести окружность, то только одну)
Требование чтоб окружность проходила через все точки не стоит :)

[ZackMercury]

Ну тогда условие задачи некорректно. "Содержащую точки" буквально означает, что все точки должны принадлежать этой окружности.

[undefined]

Думал и так ясно что невозможно провести окружность через произвольные n точек.
ПС:для однозначного задания окружности достаточно 3 точки,а не 5.
ПС2: поправил условие.

[ZackMercury]

решение такое:
ищем minX, minY, maxX, maxY.
центр окружности будет ( (maxX - minX)/2; (maxY - minY)/2 );
затем ищем максимальное расстояние до центра и берём его за радиус.

Ну так в условии не сказано, что точки произвольные)

UPD не минимальная окружность, увы. Надо ещё подумать.

[undefined]

да, не катит.
для минимальности надо чтоб 3 точки лежали на окружности.
circle.swf

[ZackMercury]

Да, я уже понял. Сейчас пытаюсь сделать демку)

[ZackMercury]

После всех стараний, не помогло :)
Бывают ситуации, когда точки можно обхватить меньшей окружностью, чтобы на ней лежали 2 точки.
Test.swf

[ZackMercury]

Готово!
Test.swf

[undefined]

если на окружности 2 точки,а всего точек>2 - значит окружность неминимальна.

[undefined]

неа
32811

[ZackMercury]

Чушь какая ><
https://pp.userapi.com/c639723/v639723943/45cc6/E8UqgOy5Kh4.jpg

[undefined]

да, затупил, если точки лежат на диаметре,достаточно двух

[ZackMercury]

Test.swf
Методом тыка - работает)

[undefined]

а обозначь центр окружности как-нибудь

[ZackMercury]

Test.swf

[undefined]

местами все же промахивается.
32814
явно можно еще чуть уменьшить чтоб третья точка легла на окружность.

[undefined]

да и вообще походу тут всего одна точка на окружности

Добавлено через 4 минуты
а можно увеличить число точек до 20-30 и сделать их крестиками 3х3?

[ZackMercury]

У меня есть идея, как это пофиксить, но нужно ещё время.
Пока что могу увеличить до 25 и сделать крестиками :)
Test.swf

NB:Сложность алгоритма не должна зависеть от расположения точек.
Я думаю, я таки нарушил правило) Как работает алгоритм:
1) Сравнить каждые 2 пары точек и найти максимально удалённые.
2) Найти точку, сумма расстояний к которой от каждой из этих двух точек будет максимальной.
3) Найти центр окружности описанной вокруг треугольника и найти радиус по максимально удалённой точке.
4) Проверить третью точку, попадает ли она в полукруг, образуемый первыми двумя точками, и если она не лежит на краю, то построить круг по двум точкам, иначе - построить круг по трём точкам.
Иначе я просто не представляю, как можно построить окружность вокруг точек вплотную.

[ZackMercury]

Поправил логику, но бывают такие моменты, когда есть точка, которая лежит за пределами описанной окружности вокруг самого большого треугольника :)
https://pp.userapi.com/c639723/v639723943/4617e/NLodwIjkElM.jpg
Test.swf
Есть одна идея.

[undefined]

В сети пишут (https://neerc.ifmo.ru/wiki/index.php?title=%D0%9C%D0%B8%D0%BD%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D0%BE%D1%85%D0%B2%D0%B0%D1%82%D1%8B%D0%B2%D0%B0%D1%8E%D1%89%D0%B0% D1%8F_%D0%BE%D0%BA%D1%80%D1%83%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%B0_%D1%82%D0%BE%D1%87%D0%B5%D0% BA), что существует алгоритм, который строит окружность за O(n),правда я так и не осилил в нем разобраться.

[ZackMercury]

https://chatgpt.com/s/dr_680ea8316ff08191b891f49f47a32a5c