Как я могу вписать прямоугольник или круг внутри произвольного четырехугольника

Это может быть более сфокусированный на математике вопрос, но я хотел задать его здесь, потому что он находится в контексте CS. Я хочу вписать прямоугольник внутри другого (произвольного) четырехугольника, чтобы вписанный четырехугольник имел максимальную высоту и ширину. Поскольку я думаю, что алгоритм будет похожим, я хочу посмотреть, смогу ли я сделать это и с кругом.

Чтобы быть более ясным, послушайте, что я имею в виду под ограничивающим четырехугольником в качестве примера. enter image description here

Вот 2 примера максимизации, которую я пытаюсь достичь: enter image description here enter image description here

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

Примечания: Для вписанного квадрата предположим, что мы знаем цель w соотношение / час, которое мы ищем (например, 4: 3). Для четырехугольника предположим, что стороны не пересекаются и он будет вогнутым (если это упрощает расчет).

5
задан Scott 7 February 2011 в 17:54
поделиться