2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 
Сообщение05.07.2006, 08:48 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение05.07.2006, 08:55 
Экс-модератор
Аватара пользователя


23/12/05
12046
Оффтоп:
harp писал(а):
на самом деле в реальной задаче некоторые рёбра многугольника могут представлять дуги (если его многоугольником после этого можно назвать) я намеренно упростил условие

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

 Профиль  
                  
 
 
Сообщение05.07.2006, 09:15 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение05.07.2006, 09:35 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение05.07.2006, 09:42 
Экс-модератор
Аватара пользователя


23/12/05
12046
Руст писал(а):
Такого рода задачи возникают, когда из куска металла надо вырезать как можно больше фигур определённой формы. Правда в такой постановке задача уже становится совсем другой и минимальный окаймляющий прямоугольник может дать гораздо меньшую экономию металла, чем резка на взгляд мастера, в особенности, когда фигура не выпуклая. Поэтому, возможно мы совсем не то решаем.

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

 Профиль  
                  
 
 
Сообщение05.07.2006, 10:01 


10/08/05
54
Артамонов Ю.Н. писал(а):
По поводу предложения нг и замечания evgeny - невыпуклый четырехугольник существует. Этот контрпример я привел бы, если бы умел здесь рисовать.


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

 Профиль  
                  
 
 
Сообщение05.07.2006, 10:19 


04/07/06
12
незваный гость писал(а):
:evil:
harp писал(а):
...некоторые рёбра многугольника могут представлять дуги...

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

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


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

 Профиль  
                  
 
 
Сообщение05.07.2006, 11:28 
Заслуженный участник
Аватара пользователя


07/03/06
1898
Москва
evgeny писал(а):
Артамонов Ю.Н. писал(а):
По поводу предложения нг и замечания evgeny - невыпуклый четырехугольник существует. Этот контрпример я привел бы, если бы умел здесь рисовать.


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

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

 Профиль  
                  
 
 
Сообщение08.07.2006, 20:21 
Заслуженный участник
Аватара пользователя


07/03/06
1898
Москва
Меня научили рисовать, грех не воспользоваться. :D
В предыдущий раз я имел в виду следующее:
Изображение
Если $\alpha>\pi/2$, то площадь прямоугольника на стороне больше, при $\alpha=\pi/2$ - площади равны.
Цитата:
Если берем заданную вершину многоугольника и фиксируем угол наглона стороны многоугольника из этой вершины к стороне искомого прямоугольника, то остальные три стороны прямоугольника восстанавливаются однозначно. Таким образом, непрерывно изменяя угол - от стороны многоугольника с искомой вершиной на стороне прямоугольника (0 градусов) до смежная сторона с искомой вершиной на стороне прямоугольника - выбираем минимум. Пробегая по всем вершинам - находим минимальную площадь прямоугольника. Если непрерывный поворот и достраивание прямоугольника удается формализовать, то задача решается аналитически.

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 24 ]  На страницу Пред.  1, 2

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Dmitriy40


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group