Прямоугольник вписанный в кривую

[berechnung]

Привет всем !!!

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

Не хватает теоретической подготовки чтоб найти подходящий математический метод.

Помогите, кто знает

Заранее спасибо.

[Бодигрим]

Стороны прямоугольника параллельны осям координат?

АФАИК, если

Цитата:

Кривая задана множеством точек координатной плоскости,

то ничего лучше перебора этих точек предложить нельзя.

[Алексей К.]

Ежели Ваша фигура выпукла, то достаточно проверить 4 вершинки прямоугольника.

[berechnung]

Для начала благодарю за быстрые ответы. Мне кажется, я не совсем понятно изложил суть проблемы. Есть кривая, образующая фигуру неправильной формы, скажем, напоминающая овал. Есть прямоугольник. Множество точек кривой заданы на координатной плоскости, прямоугольник же размерами, без каких-либо координат. Так вот задача найти алгоритм, находящий, умещается ли прямоугольник целиком на площади, описаной кривой.
Другими словами, чтобы вырезать из куска материи произвольной формы прямоугольник, заданых размеров надо:
1. найти есть ли такое расположение прямоугольника, при котором он помещается в этот кусок
2. найти это расположение

Спасибо.

[Алексей К.]

Так понятнее. В частности тому, кто прочитав задачку, увидит что-то знакомое и предложит подход к решению. Однако --- я почти уверен --- ему тоже захочется узнать, выпуклая фигура, или о выпуклости ничего неизвестно. Этот фактор на простоту или сложность решения может сильно повлиять.
Вот у Вас проскочило --- "напоминающая овал". Не стоит ли за этим условие выпуклости? Поясните ещё этот момент и тогда --- ждите ответа... ждите ответа... ждите ответа...

[Профессор Снэйп]

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

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

[Алексей К.]

Ну, и если она выпуклая, то, поскольку нужен алгоритм, я бы его составил простым перебором, а именно, перебирая точки кривой с некоторым шажком $\Delta s$.
Кривая задана, например, параметрическим уравнением $P(t)=(x(t), y(t)), \quad 0\le t\le T$ (или пусть даже дискретно-точечной тобличкой). В каждую точку $P_0(t)$ помещаем вершину $A$ прямоугольника $ABCD$, вычисляем точку $P_1(t)$, куда встанет вершина $B$, определяем положения точек $C$ и $D$ (справа или слева от отрезка $\vec{AB}$, в зависимости от направления обхода), и, наконец, определяем --- попали ли эти две точки внутрь фигуры.
Повторяем цикл до первой удачи.

Это тупое решение на скорую руку, солнце и суббота мешают и гонят подальше от ЭВМ...

[berechnung]

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

[Алексей К.]

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

[Бодигрим]

Алексей К. писал(а):

В каждую точку $P_0(t)$ помещаем вершину $A$ прямоугольника $ABCD$, вычисляем точку $P_1(t)$, куда встанет вершина $B$...

Каким образом мы выбираем наилучшую из точек $B$? Насколько я понял из условия, стороны не обязательно параллельны осям.

[Алексей К.]

Точку $P_1$ мы выбираем на расстоянии $AB$ от $P_0$ на кривой (ну, с соотв. вычислениями, которые я обозвал тупыми и скучными). Т.е. точку $A$ тащим по границе фигуры, точку $B$ заставляем по ней же, по границе, бежать. Остальное, $BCDA$, либо всунется вовнутрь, либо не всунется. Если выпукло, конечно.
А будем ли мы тащить $AB$ или $BC$ (короткую или длинную сторону) ---- неважно, просто в другом случае решение найдётся в другом месте. Оптимальнее, конечно, длинную сторону тащить.

Да, Бодигрим, я неясно выразился.

[berechnung]

Бодигрим писал(а):

Алексей К. писал(а):

В каждую точку $P_0(t)$ помещаем вершину $A$ прямоугольника $ABCD$, вычисляем точку $P_1(t)$, куда встанет вершина $B$...

Каким образом мы выбираем наилучшую из точек $B$? Насколько я понял из условия, стороны не обязательно параллельны осям.

Решение, предложенное Алексеем, может не самое элегантное, но выполнимое. Пройти по кривой, сравнивая диагональ прямоугольника, и расстояние до соседних вершин, легко превращается в исходный код.

Если не придумаю чего-нибудь более простого, думаю воспользуюсь им.

[Алексей К.]

berechnung писал(а):

Решение, предложенное Алексеем, может не самое элегантное.

Да это конкретно тупое решение, я же сам сказал.

[PAV]

Переезжаем из "Помогите решить" в CS