Сгладьте выпуклую многоугольную форму так, чтобы она стала как можно больше при сохранении диаметра.

Учитывая выпуклый многоугольник, я пытаюсь увеличить его форму (как в «максимальной площади»), сохраняя его диаметр. Диаметр определяется как длина самого длинного сегмента, который может быть помещен в многоугольник. Поскольку многоугольник выпуклый, я предполагаю, что этот диаметр всегда можно найти, просмотрев все пары вершин.

Например, если задан равносторонний треугольник в качестве входного многоугольника, диаметр треугольника равен длине любого ребра; сглаживание этого привело бы к 3 сегментам круга, как показано на изображении

. Для произвольных выпуклых многоугольников очень неэффективным алгоритмом является вычисление пересечения кругов с максимальным радиусом с центром в каждой вершине многоугольника; это то, что я использую сейчас (на Java). есть что-нибудь получше? Любой псевдокод или указатель на алгоритм будут оценены.

Другой пример: сжатый пятиугольник и соответствующая ему максимальная форма, сохраняющая диаметр. Идея состоит в том, что вы не можете увеличить площадь этой формы, не увеличивая диаметр (то есть, делая возможным рисовать прямую линию в границах формы, которая длиннее исходного диаметра). В этом конкретном случае кажется, что один круг с радиусом = polygon_diameter / 2 (розовый) лучше, чем пересечение нескольких больших кругов с радиусом = polygon_diameter (голубой). На втором изображении обе области накладываются друг на друга, чтобы упростить сравнение, но области должны полностью охватывать многоугольник.