Preciso encontrar o maior círculo inscrito de um polígono convexo, procurei em muitos sites e acho que isso pode ser feito usando a triangulação de Delaunay. Achei umfio na discussão CGAL com um algoritmo usando CGAL:

Você pode calcular isso facilmente com CGAL:

Primeiro, calcule a triangulação de Delaunay dos pontos.

Em seguida, itere em todas as faces finitas da triangulação. Para cada face finita f

calcular seu circuncentro clocalize c na triangulação (para acelerar as coisas, você pode dar um vértice de f como dica inicial para a localização do ponto)se a face retornada pela localização (c, dica) é finita, o circuncentro c fica no casco convexo dos pontos; portanto, f é um candidatose f for uma face candidata, calcule seu perímetro quadrado ao quadrado, mantenha apenas o rosto com o mínimo perímetro quadrado

O manual da CGAL (capítulo triangulação 2D, juntamente com algumas coisas do kernel) mostra todas as funções básicas para fazer isso.

Fiquei um pouco confuso com a última parte deste algoritmo. Quando o leio, o que entendo é que o perímetro mínimo da face da triangulação é o raio do maior círculo fechado. Mas, a partir de exemplos de polígono com triangulação de Delaunay, parece que até o menor circuncisão às vezes não pode caber dentro do polígono, então como isso pode ter o mesmo raio do maior círculo inscrito?