Como encontrar o círculo mínimo raio que abrange todos os pontos dados?

Question

Suponha que eu tenho cerca de 1000 pontos ímpares em um avião.

Então, o que eu acho que poderia ser feito é descartar os pontos que não afetam o raio do círculo de qualquer forma - os pontos através do qual o casco convexo não passa [usando um do vários algoritmos ]. Isso nos deixa com pontos que têm importância.

Agora, a partir de agora, o que pode ser feito para encontrar aquele círculo raio mínimo?

Eu estou olhando para generalizar isso para elipses uma vez eu entendo como isso pode ser feito de círculos.

Qualquer link para algum "código fonte pública" seria útil, para que eu possa modificá-lo para elipses.

Answer 1

Uma opção é o CGAL Computational Geometry Algorithms Biblioteca . É open source, mas também é grande -. O maior problema que você vai ter, eu suspeito, é encontrar a agulha no palheiro

É claro que (e este é, em parte, no pedido de desculpas a Martin), você pode facilmente encontrar opções mais específicos usando o Google. O segundo item listado parecia OK quando eu tentei, se você não se importa Prolog, e havia pelo menos um exemplo C e um Javascript na primeira página de resultados. E você dificilmente pode reivindicar não saber as palavras para o Google para qualquer mais.

Answer 2

Isto é conhecido como o problema Minimal que encerra círculo (Estou perplexo porque a sua pesquisa google não apareceu nada), e discutido aqui , aqui , aqui , e em muitos outros lugares.