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

Question

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

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

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

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

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

Answer 1

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

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

Answer 2

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