Necesito encontrar el círculo inscrito más grande de un polígono convexo, he buscado en muchos sitios y entiendo que esto se puede hacer utilizando la triangulación de Delaunay. Encontre unhilo en discusión CGAL con un algoritmo usando CGAL:

Puede calcular esto fácilmente con CGAL:

Primero, calcule la triangulación de Delaunay de los puntos.

Luego, itera en todas las caras finitas de la triangulación. Para cada cara finita f

calcular su circuncentro cubique c en la triangulación (para acelerar las cosas, puede dar un vértice de f como pista inicial para la ubicación del punto)si la cara devuelta por localizar (c, pista) es finita, entonces el circuncentro c se encuentra en el casco convexo de los puntos, entonces, f es un candidatosi f es una cara tan candidata, calcule su circunradio cuadrado mantenga solo la cara con circunradio cuadrado mínimo

El manual CGAL (capítulo triangulación 2D, junto con algunas cosas del núcleo) muestra todas las funciones básicas para hacer esto.

Estaba un poco confundido con la última parte de este algoritmo. Cuando lo leo, lo que entiendo es que el circunradio mínimo de la cara de triangulación es el radio para el círculo más grande inscrito. Pero a partir de ejemplos de polígonos con triangulación de Delaunay, parece que incluso el círculo más pequeño a veces no puede caber dentro del polígono, entonces, ¿cómo puede tener el mismo radio que el círculo inscrito más grande?