Минимальный круг, охватывающий несколько ограничивающих полей

Question

У меня есть набор ограничивающих прямоугольников (нижний/верхний x, y) в 2D. Я хотел бы найти диаметр самого маленького круга, который охватывает эти ограничивающие прямоугольники.

Я не слишком хорошо знаком с вычислительными алгоритмами геометрии, но поиск Google появился эти ссылки: https://en.wikipedia.org/wiki/Bounding_sphere или это: https://en.wikipedia.org/wiki/Smallest-circle_problem

Вопросы:

1. Является ли проблема указанной выше таких же, как ссылки, упомянутые выше (но в 2D)? Если это так, я могу применить/реализовать алгоритм Ritter или, возможно, решение Minball https://github.com/hbf/miniball?

2. Есть ли существующий пакет/функция python (возможно, Shapely?), Который делает это уже?

Answer 1

Минимальный круг всегда определяется вершинами многоугольников, а не ребрами.

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

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