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

Question

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

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

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

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

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

Answer 1

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

Answer 2

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

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