Как найти окружность минимального радиуса, охватывающую все заданные точки?

Question

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

Тогда, я думаю, можно было бы отбросить точки, которые никак не влияют на радиус круга - точки, через которые выпуклая оболочка не проходит [используя один из несколько алгоритмов].Это оставляет нам вопросы, которые действительно имеют значение.

Что же можно сделать с этого момента, чтобы найти окружность минимального радиуса?

Я хочу обобщить это для эллипсов, как только пойму, как это можно сделать для кругов.

Любая ссылка на некоторый «общедоступный исходный код» была бы полезна, чтобы я мог изменить ее для многоточий.

Answer 1

Одним из вариантов является Библиотека алгоритмов вычислительной геометрии CGAL.Это открытый исходный код, но он также большой - я подозреваю, что самая большая проблема, с которой вы столкнетесь, - это найти иголку в стоге сена.

Конечно (и это отчасти извинение перед Мартином), вы можете легко найти более целенаправленные варианты с помощью Google.Когда я попробовал, второй элемент в списке выглядел нормально, если вы не против Пролога, и на первой странице результатов был по крайней мере один пример C и один Javascript.И вряд ли вы больше можете утверждать, что не знаете слов в Google.

Answer 2

Это известно как проблема минимального охватывающего круга (я озадачен, почему ваш поиск в Google ничего не дал) и обсуждается здесь, здесь, здесь, и во многих других местах.