Мне нужно найти самый большой вписанный круг выпуклого многоугольника, я искал много сайтов и понял, что это можно сделать с помощью триангуляции Делоне. Я нашелнить в обсуждении CGAL с алгоритмом, использующим CGAL:

Вы можете легко вычислить это с помощью CGAL:

Сначала вычислите триангуляцию Делоне для точек.

Затем повторяем все конечные грани триангуляции. Для каждого конечного лица f

вычислить его окружность снайдите c в триангуляции (чтобы ускорить процесс, вы можете дать одну вершину f в качестве начальной подсказки для местоположения точки)если грань, возвращаемая функцией locate (c, hint), конечна, то центр окружности c лежит в выпуклой оболочке точек, поэтому f является кандидатомесли f такое лицо-кандидат, вычислите его квадратный радиус, а оставьте только лицо с минимальным квадратным радиусом.

В руководстве по CGAL (глава 2D триангуляция, вместе с некоторыми подробностями из ядра) показаны все основные функции для этого.

Я был немного смущен с последней частью этого алгоритма. Когда я читаю это, я понимаю, что минимальная окружность триангуляционной грани - это радиус самого большого врезанного круга. Но из примеров многоугольника с триангуляцией Делоне кажется, что даже самая маленькая окружность иногда не может поместиться внутри многоугольника, так как же он может иметь такой же радиус, как и самый большой вписанный круг?