габариты многоугольника

[Руст]

Задача с дугами усложняется, тем не менее задача в пределах аналитического решения. Найти касательные к дугам окружностей несложно. Поэтому задача сводится к минимизации некоторой функции от синусов и косинусов типа $Asinx+Bcosx+Csinxcosx$. Единственное ещё присутствует перебор вершин касания и дуг. Тем не менее, можно написать программу, которая вычисляет по заданным вершинам и дугам окружностей окаймляющий прямоугольник минимальной площади.

[photon]

Оффтоп:

harp писал(а):

на самом деле в реальной задаче некоторые рёбра многугольника могут представлять дуги (если его многоугольником после этого можно назвать) я намеренно упростил условие

У нас на Инженерной графике преподаватель дал название "многоугольнику", образованному дугами - "многокривульник".

[Руст]

Такого рода задачи возникают, когда из куска металла надо вырезать как можно больше фигур определённой формы. Правда в такой постановке задача уже становится совсем другой и минимальный окаймляющий прямоугольник может дать гораздо меньшую экономию металла, чем резка на взгляд мастера, в особенности, когда фигура не выпуклая. Поэтому, возможно мы совсем не то решаем.

[juna]

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

[photon]

Руст писал(а):

Такого рода задачи возникают, когда из куска металла надо вырезать как можно больше фигур определённой формы. Правда в такой постановке задача уже становится совсем другой и минимальный окаймляющий прямоугольник может дать гораздо меньшую экономию металла, чем резка на взгляд мастера, в особенности, когда фигура не выпуклая. Поэтому, возможно мы совсем не то решаем.

Это точно. Например, порезать лист на правильные шестиугольники можно без потерь (кроме небольших на краях листа), а если сначала поделить на прямоугольники, то будет далеко не оптимум.

[evgeny]

Артамонов Ю.Н. писал(а):

По поводу предложения нг и замечания evgeny - невыпуклый четырехугольник существует. Этот контрпример я привел бы, если бы умел здесь рисовать.

А смысл рассматривать невыпуклые мноноугольники?
Понятно, что играет роль только их выпуклая оболочка. Именно ее стороны и имелись ввиду.

[harp]

незваный гость писал(а):

:evil:

harp писал(а):

...некоторые рёбра многугольника могут представлять дуги...

А дуги, простите, чего? Окружности? Кривые Безье?

дуги окружности


Делаю вывод, что задача решается только перебором. Правильно?

[juna]

evgeny писал(а):

Артамонов Ю.Н. писал(а):

По поводу предложения нг и замечания evgeny - невыпуклый четырехугольник существует. Этот контрпример я привел бы, если бы умел здесь рисовать.

А смысл рассматривать невыпуклые мноноугольники?
Понятно, что играет роль только их выпуклая оболочка. Именно ее стороны и имелись ввиду.

Да, я был невнимателен.

[juna]

Меня научили рисовать, грех не воспользоваться.
В предыдущий раз я имел в виду следующее:

Если $\alpha>\pi/2$, то площадь прямоугольника на стороне больше, при $\alpha=\pi/2$ - площади равны.

Цитата:

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

Алгоритм, который здесь описан можно образно представить как выпуклый многоугольник скатывается по наклонной плоскости и в каждом положении достраивается до прямоугольника:

Цитата:

Такого рода задачи возникают, когда из куска металла надо вырезать как можно больше фигур определённой формы. Правда в такой постановке задача уже становится совсем другой и минимальный окаймляющий прямоугольник может дать гораздо меньшую экономию металла, чем резка на взгляд мастера, в особенности, когда фигура не выпуклая. Поэтому, возможно мы совсем не то решаем.

Наверное здесь идет речь о динамическом программировании: сначала для заданных фигур ищут прямоугольники наименьшей площади, а затем оптимальным образом распределяют эти прямоугольники по куску металла. При больших объемах производства такой подход себя оправдывает.