¿Cómo encontrar el círculo de radio mínimo que encierra todos los puntos dados?

Question

Supongamos que tengo algunos 1.000 puntos impares en un avión.

Entonces, lo que yo creo que se podría hacer es descartar los puntos que no afectan el radio del círculo de ninguna manera - los puntos por los que la casco convexo no pasa [usando uno de los noreferrer varios algoritmos ]. Esto nos deja con puntos que son importantes.

Ahora de aquí en adelante, qué se puede hacer para encontrar ese círculo de radio mínimo?

Busco generalizar esto para elipses vez entiendo cómo se puede hacer para los círculos.

Cualquier enlace a algún "código fuente público" sería de gran ayuda, para que pueda modificarlo para elipses.

Answer 1

Una de las opciones es la CGAL Geometría Computacional Algoritmos Biblioteca . Es de código abierto, pero también es grande -. El mayor problema que tendrá, sospecho, es encontrar la aguja en el pajar

Por supuesto (y esto se debe en parte a modo de disculpa a Martin), se puede encontrar fácilmente las opciones más específicos a través de Google. El segundo elemento de la lista se veía bien cuando he intentado, si no le importa Prolog, y había por lo menos un ejemplo C y uno Javascript en la primera página de resultados. Y difícilmente se puede afirmar que no le sabe las letras de Google para más.

Answer 2

Esto se conoce como el problema Encerrando Círculo Mínimo (estoy desconcertado por las que su búsqueda en Google no se presentó nada), y discutió aquí , aquí , aquí , y en muchos otros lugares.