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

[harp]

Есть многоугольник, заданный вершинами, необходимо найти минимальной площади прямоугольник, в который можно "засунуть" заданный многоугольник.

[cepesh]

речь о $\mathbb{R}^2$? Если да, то в чем проблема? ищем верхнюю, нижнюю, левую и правую точки...

[Руст]

Сам многоугольник и есть многоугольник минимальной площади, куда его можно втиснуть без деформаций (при разрешении только поворотов, которые сохраняют площадь).

[photon]

cepesh писал(а):

ищем верхнюю, нижнюю, левую и правую точки...

А как найти, где право, где низ?

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

Сам многоугольник и есть многоугольник минимальной площади, куда его можно втиснуть без деформаций (при разрешении только поворотов, которые сохраняют площадь).

Ищут не произвольный многоугольник, а прямоугольник.

[harp]

хм, не знаю что такое $\mathbb{R}^2$
Найти верхнюю, нижнюю, левую и правую точки как я понимаю многоугольника, и что с ними делать?

[Руст]

Многоугольник разбиваете на треугольники и считаете площадь каждого теугольника ABC по формуле $S_{ABC}=\frac 12 |AB*AC|$ т.е. через половины длины векторного произведения.

[harp]

Руст
а как мне носле этого прямоугольник то найти?

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

вот нашёл обсуждение
http://forum.vingrad.ru/index.php?showtopic=21917&hl=

[Руст]

Я по невнимательности упустил, что надо искать минимальной площади прямоугольник.
Эту задачу можно решить так. Вначале берём выпуклую оболочку (если невыпуклый вписан в прямоугольник то и выпуклая оболочка вписана туда). Далее строим разные прямоугольники с углом наклона к горизантали. При задании эого угла, размеры определяются однозначно.
Несколько длиннее, берём каждую вершину $A_i$ как пробную, через которую проходит прямоугольник и рассматриваем все прямоугольники содержащие треугольник $A_{i-1}A_iA_{i+1}$ заданного выпуклого многоугольника.

[harp]

спасибо, буду разбираться

[незваный гость]

Может быть, повторю что либо сказанное ранее -- не плагиатор, заранеее всех цитирую

Прямоугольник задает единичный вектор $\bar{e} = (e_x, e_y)$, паралельный стороне. Пусть координаты точки $A_i = (x_i, y_i)$. Тогда развернув на угол $(e_x,-e_y)$ имем $A'_i = (x_i e_x + y_i e_y, \, y_i e_x - x_i e_y)$, зато прямоугольник паралелен осям координат, и его площадь равна $S =\left( \max(x_i e_x + y_i e_y) - \min(x_i e_x + y_i e_y) \right) \times $ $ \left( \max(y_i e_x - x_i e_y) - \min(y_i e_x - x_i e_y) \right)$.

Далее я рискну высказать
Предположение: одна из сторон выпуклой оболочки лежит на границе прямоугольника.

Если так, то после построения выпуклой оболочки достаточно пройтись вдоль ее границы.

[Руст]

Похоже это предположение не всегда верно. Возможно контрпример найдётся начиная с пятиугольника.

[незваный гость]

Хотелось бы контр-пример. Я и сам над ним думаю.

[harp]

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

[evgeny]

А почему контр-пример начиная с 5-ти угольника?
Ведь если гипотеза (о совпадении стороны с одной из прямых) неверна, то есть $\le4$ точки (ровно по одной на каждой стороне прямоугольника), такие что при малых поворотах площадь возрастает, т.е. если конт-пример есть, что в нем не более 4 точек.

Очевидно, что с 3-мя точками все в порядке.
Если точек 4, то можно считать, что они расположены на сторонах квадрата $A_1A_2A_3A_4$ на расстояниях $a_i$ от соответствующих вершин.
Тогда площадь прямоугольника при небольших сдвигах будет

$$ \begin{array}{ccl} S & = & \left(\phantom{\displaystyle\frac 12}\cos{\alpha} +(a_1+a_3-1) \sin{\alpha}\phantom{\displaystyle\frac 12}\right) \left(\phantom{\displaystyle\frac 12}\cos{\alpha} +(a_2+a_4-1) \sin{\alpha}\phantom{\displaystyle\frac 12}\right) \\ &&\\ & = & 1 + (t_1+t_2)\alpha+ (t_1t_2-1)\alpha^2 + O(\alpha^3)\\ \end{array} $$

где $t_1 = a_1+a_3 - 1$, $t_2 = a_2+a_4-1$, т.е. очевидно не может быть локальным минимумом

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

$$ S = \left(\phantom{\displaystyle\frac 12}R_1+R_3 + D_{1,3}\cos(\alpha + \varphi_{1,3})\phantom{\displaystyle\frac 12}\right) \left(\phantom{\displaystyle\frac 12}R_2+R_4 + D_{2,4}\cos(\alpha + \varphi_{2,4})\phantom{\displaystyle\frac 12}\right) $$

т.е. необходимо проверять помимо всех "критических" направлений (когда происходит перестройка с одной дуги на другую, т.е. точка касания с опорной прямой совпадает с одной из вершин) но еще и на каждом интервале между критическими искать минимум (многочлена второй степени от $\sin x$ и $\cos x$) проверять его.

[незваный гость]

harp писал(а):

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

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

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