Résultat

Étapes de calcul

Représentation visuelle

À propos du Plus Petit Cercle Englobant

Qu'est-ce que le Plus Petit Cercle Englobant ?

Le plus petit cercle englobant, également connu sous le nom de cercle de couverture minimum, est le plus petit cercle qui contient un ensemble donné de points dans le plan euclidien. C'est un problème fondamental en géométrie computationnelle avec des applications en infographie, localisation d'installations et visualisation de données.

Formule

Il n'existe pas de formule simple pour trouver le plus petit cercle englobant. Au lieu de cela, il est généralement résolu à l'aide d'algorithmes itératifs. Une approche courante est l'algorithme de Welzl, qui a une complexité temporelle linéaire attendue.

Cependant, une fois que nous avons le cercle, nous pouvons le décrire avec les équations suivantes :

• Équation du cercle : \((x - h)^2 + (y - k)^2 = r^2\)
• Où \((h, k)\) est le centre du cercle et \(r\) est son rayon

Étapes de calcul

1. Saisir l'ensemble des points
2. Initialiser le cercle avec les deux premiers points
3. Pour chaque point restant :
   • Si le point est en dehors du cercle actuel, mettre à jour le cercle pour inclure ce point
   • Le nouveau cercle est le plus petit cercle qui inclut le nouveau point et tous les points précédents
4. Le cercle résultant est le plus petit cercle englobant

Exemple

Trouvons le plus petit cercle englobant pour les points (0,0), (1,1), (-1,1) et (0,-1) :

1. Commencer avec (0,0) et (1,1) : centre du cercle (0,5, 0,5), rayon \(\sqrt{0,5}\)
2. Ajouter (-1,1) : nouveau centre du cercle (0, 1), rayon \(\sqrt{2}\)
3. Ajouter (0,-1) : cercle final centre (0, 0), rayon 1