Cercle minimal englobant plusieurs boîtes englobantes

Question

J'ai un ensemble de boîtes englobantes (inférieur/supérieur x, y) en 2D. Je voudrais trouver le diamètre du plus petit cercle qui entoure ces boîtes de délimitation.

Je ne suis pas trop familier avec les algorithmes de la géométrie algorithmique, mais une recherche Google relevai ces liens: https://en.wikipedia.org/wiki/Bounding_sphere ou ceci: https://en.wikipedia.org/wiki/Smallest-circle_problem

Questions:

1. Le problème est indiqué au-dessus du même que liens mentionnés ci-dessus (mais en 2D)? Si oui, je peux appliquer/implémenter l'algorithme Ritter ou peut-être la solution Minball https://github.com/hbf/miniball?

2. Existe-t-il déjà un package/une fonction python (peut-être Shapely?) Qui le fait déjà?

Answer 1

Le cercle minimum est toujours défini par les sommets des polygones, et non par les arêtes.

Vous pouvez donc appliquer n'importe quel algorithme de cercle le plus petit à l'ensemble des sommets de la boîte (en haut à gauche, en haut à droite, en bas à gauche, en bas à droite).

(il pourrait y avoir beaucoup de sommets internes, mais préliminaire suppression de points intérieurs apparents ne semble pas plus simple que le cercle algo)