Comment trouver le cercle de rayon minimum qui entoure tous les points donnés?

Question

Supposons que j'ai quelques 1000 points impairs sur un plan.

Alors, ce que je pense qu'on pourrait faire est de rejeter les points qui ne touchent pas le rayon du cercle de quelque façon - les points par lesquels la enveloppe convexe ne passe pas [en utilisant l'un des noreferrer plusieurs algorithmes ]. Cela nous laisse avec des points qui comptent.

A partir de là, ce qui peut être fait pour trouver ce cercle de rayon minimum?

Je cherche à généraliser ce pour une fois que je comprends des ellipses comment il peut être fait pour les cercles.

Tout lien vers une "code source publique" serait utile, pour que je puisse le modifier pour ellipses.

Answer 1

L'une des options est CGAL Bibliothèque Computational Geometry Algorithms . Il est open source, mais il est aussi important -. Le plus gros problème que vous aurez, je pense, est de trouver l'aiguille dans la botte de foin

Bien sûr (et cela est en partie en excuses à Martin), vous pouvez facilement trouver des options plus ciblées à l'aide de Google. Le deuxième élément de la liste avaient l'air bien quand j'ai essayé, si vous ne me dérange pas Prolog, et il y avait au moins un exemple de C et un Javascript est désactivé sur la première page des résultats. Et vous pouvez difficilement prétendre ne pas connaître les mots à Google pour plus.

Answer 2

Ceci est connu comme le problème du Cercle englobante minimal (je suis perplexe pourquoi votre recherche google n'a pas montré quoi que ce soit), et discuté ici , ici , , et dans de nombreux autres endroits.