2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Прямоугольник вписанный в кривую
Сообщение05.04.2008, 13:04 
Привет всем !!! :lol:

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

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

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

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

 
 
 
 
Сообщение05.04.2008, 14:12 
Аватара пользователя
Стороны прямоугольника параллельны осям координат?

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

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

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

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

Спасибо. :lol:

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

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

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

 
 
 
 
Сообщение05.04.2008, 17:28 
Ну, и если она выпуклая, то, поскольку нужен алгоритм, я бы его составил простым перебором, а именно, перебирая точки кривой с некоторым шажком $\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}$, в зависимости от направления обхода), и, наконец, определяем --- попали ли эти две точки внутрь фигуры.
Повторяем цикл до первой удачи.

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

 
 
 
 
Сообщение05.04.2008, 17:32 
Кривая не везде выпуклая, исходная фигура неправильной формы с вогнутостями. Спасибо за ответ.
8-)

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

 
 
 
 
Сообщение05.04.2008, 17:45 
Аватара пользователя
Алексей К. писал(а):
В каждую точку $P_0(t)$ помещаем вершину $A$ прямоугольника $ABCD$, вычисляем точку $P_1(t)$, куда встанет вершина $B$...

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

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

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

 
 
 
 
Сообщение05.04.2008, 17:59 
Бодигрим писал(а):
Алексей К. писал(а):
В каждую точку $P_0(t)$ помещаем вершину $A$ прямоугольника $ABCD$, вычисляем точку $P_1(t)$, куда встанет вершина $B$...

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


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

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

 
 
 
 
Сообщение05.04.2008, 18:05 
berechnung писал(а):
Решение, предложенное Алексеем, может не самое элегантное.

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

 
 
 
 
Сообщение05.04.2008, 21:36 
Аватара пользователя
Переезжаем из "Помогите решить" в CS

 
 
 [ Сообщений: 14 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group