Есть выпуклый четырехугольник произвольной формы.

Добрый день, коллеги!Может быть кто то сможет помочь с такой задачей:

Есть выпуклый четырехугольник произвольной формы, есть прямоугольник с заданными размерами. При каких условиях прямоугольник сможет "войти" в четырехугольник?

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

Редактировалось 1 раз(а). Последний 24.07.2011 22:11.

произвольный выпуклый 4-х угольник можно задать системой 4-х линейных неравенств: $a_ix+b_iy\le c_i$ , $i=1..4;$

Чтобы проверить, впишется ли в него другой выпуклый 4-х угольник, достаточно убедиться, что координаты каждой из его вершин $(x_k,y_k)$ , $k=1..4;$ удовлетворяют этой системе. Итого, для фиксированных координат вершин имеем 16 неравенств, которые нужно проверить.Но тут есть один нюанс: координаты прямоугольника --- плавающие. Т.е. задача стоит так: найдутся ли такие сдвиг и поворот прямоугольника с заданной шириной и высотой, что координаты его вершин удовлетворяют системе неравенств.Дальше - нужно тупо все это выписать и попробовать преобразавать систему условий до какого-нибудь приемлемого вида.

Но сразу скажу: идея с трафаретом лучше.

Редактировалось 1 раз(а). Последний 23.07.2011 21:19.

придумайте механическое приспособление с четырьмя уголками, способное раздвигаться-сдвигаться по двум перпендикулярным направлениям. затем:1 перерисовываете четырехугольник в масштабе на бумагу,2 раздвигаете приспособление на необходимые параметры прямоугольника,3 ручками прикладываете приспособление к чертежу,4 результат фиксируется отметкой четырех точек по уголкам приспособления.

а за прибор можно даже получить патент)

Все получится. Делается это так.Пишется , в общем то не сложная программа, на вход которой подаются, например, 4 длины сторон 4хугольника и 2 длины диагоналей (конечно, достаточно и 5 замеров, одно --- лишнее, но пригодится для контроля точности). Также вводятся ширина и высота прямоугольника. Все. Далее программа1) расчитывает координаты 4хугольника, и строит выпуклое множество его точек в виде 4х лин неравенств;2) проверяет возможность принадлежности прямоугольника этой области;3) выдает ответ с чертежом.

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

Предлагаю решение указанной проблемы с помощью команды FindInstance из пакета Mathematica. Данная команда позволяет найти значения переменных, удовлетворяющих некоторому набору условий. Каждое условие записывается в виде равенства или неравенства и соединяются значками ( && - логическое "и", || - логическое "или"). Результатом работы программы будет либо пустой список $\< \,\>$ - это означает, что решений нет, либо конкретный набор значений переменных (можно получить и несколько наборов), удовлетворяющих заданным условиям.Рассмотрим конкретный пример. Пусть четырёхугольник $ABCD$ задан координатами вершин: $A(0,0)$ , $B(-100,150)$ , $C(200,200)$ и $D(100,0)$ . Задача состоит в том, чтобы выяснить - можно ли в него вписать прямоугольник со сторонами $p=200$ и $q=100$ ? Координаты самой нижней точки прямоугольника (с минимальной ординатой) обозначим через $(x,y)$ . Обозначим также $a=\sin\alpha$ и $b=\cos\alpha$ , где $\alpha$ - минимальный неотрицательный угол, образуемый сторонами прямоугольника с положительным направление оси $x$ . При записи условий использована идея уважаемого vpro задания выпуклого четырёхугольника с помощью линейных неравенств. Код в Mathematica выделен болдом, результат - синим цветом.

p = 200; q = 100;FindInstance[y >= 0 && 3 x + 2 y >= 0 && x - 6 y + 1000 >= 0 &&2 x - y - 200 <=0 && ((y + p a >= 0 &&3 (x + p b) + 2 (y + p a) >=0 && (x + p b) - 6 (y + p a) + 1000 >= 0 &&2 (x + p b) - (y + p a) - 200 <= 0 && y + q b >= 0 &&3 (x - q a) + 2 (y + q b) >=0 && (x - q a) - 6 (y + q b) + 1000 >= 0 &&2 (x - q a) - (y + q b) - 200 <= 0 && y + p a + q b >= 0 &&3 (x + p b - q a) + 2 (y + p a + q b) >=0 && (x + p b - q a) - 6 (y + p a + q b) + 1000 >= 0 &&2 (x + p b - q a) - (y + p a + q b) - 200 <= 0) || (y + q a >=0 && 3 (x + q b) + 2 (y + q a) >=0 && (x + q b) - 6 (y + q a) + 1000 >= 0 &&2 (x + q b) - (y + q a) - 200 <= 0 && y + p b >= 0 &&3 (x - p a) + 2 (y + p b) >=0 && (x - p a) - 6 (y + p b) + 1000 >= 0 &&2 (x - p a) - (y + p b) - 200 <= 0 && y + q a + p b >= 0 &&3 (x + q b - p a) + 2 (y + q a + p b) >=0 && (x + q b - p a) - 6 (y + q a + p b) + 1000 >= 0 &&2 (x + q b - p a) - (y + q a + p b) - 200 <= 0)) &&a^2 + b^2 == 1 && a >= 0 && b > 0, , Reals] $\$

Вывод - вписать невозможно!

Попробуем уменьшить одну из сторон и снова применим ту же команду:

p = 185;FindInstance[y >= 0 && 3 x + 2 y >= 0 && x - 6 y + 1000 >= 0 &&2 x - y - 200 <=0 && ((y + p a >= 0 &&3 (x + p b) + 2 (y + p a) >=0 && (x + p b) - 6 (y + p a) + 1000 >= 0 &&2 (x + p b) - (y + p a) - 200 <= 0 && y + q b >= 0 &&3 (x - q a) + 2 (y + q b) >=0 && (x - q a) - 6 (y + q b) + 1000 >= 0 &&2 (x - q a) - (y + q b) - 200 <= 0 && y + p a + q b >= 0 &&3 (x + p b - q a) + 2 (y + p a + q b) >=0 && (x + p b - q a) - 6 (y + p a + q b) + 1000 >= 0 &&2 (x + p b - q a) - (y + p a + q b) - 200 <= 0) || (y + q a >=0 && 3 (x + q b) + 2 (y + q a) >=0 && (x + q b) - 6 (y + q a) + 1000 >= 0 &&2 (x + q b) - (y + q a) - 200 <= 0 && y + p b >= 0 &&3 (x - p a) + 2 (y + p b) >=0 && (x - p a) - 6 (y + p b) + 1000 >= 0 &&2 (x - p a) - (y + p b) - 200 <= 0 && y + q a + p b >= 0 &&3 (x + q b - p a) + 2 (y + q a + p b) >=0 && (x + q b - p a) - 6 (y + q a + p b) + 1000 >= 0 &&2 (x + q b - p a) - (y + q a + p b) - 200 <= 0)) &&a^2 + b^2 == 1 && a >= 0 && b > 0, , Reals] $\left\$ , $a -> \frac, b -> \frac\right\> $

Решение найдено. Видим, что решение находится точное. Конечно, можно найти и приближённые значения.

Моя задача была показать принципиальную возможность решения. Если доводить "до ума", то следует написать процедуру, в которой в качестве формальных параметров указывать наиболее удобные на практике характеристики исходного четырёхугольника и длины сторон вписываемого прямоугольника. Но это уже совсем не сложно!